写在前面

• 数据结构全文

树结构

• 集合底层用数组扩容实现的
• 节点，一个对象，树的一个单位
• 叶子节点，没有子节点的节点
• 节点的权，节点值
• 路径，从根节点找到该节点的路线
• 层，同一个级别
• 树的高度，层数
• 森林，多颗子树
• 二叉树，每个节点，最多只能有两个子节点
• 如果二叉树的所有叶子节点都在最后一层，且节点总数为2^n-1，n为层数，则为满二叉树
• 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点叶在右连续，则为完全二叉树，满二叉树一定是完全二叉树

遍历

• 前序遍历，先输出父节点，再遍历左子树和右子树
• 中序遍历，先遍历左子树，再输出父节点，再遍历右子树
• 后序遍历，先遍历左子树，在遍历右子树，最后输出父节点
• 创建树

 class BinaryTree {
    private Node root;
    public void setRoot(Node root) {
        this.root = root;
    }
    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("empty");
        }
    }
    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("empty");
        }
    }
    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("empty");
        }
    }
}
复制代码  

• 创建节点

 class Node {
    private int id;
    private String name;
    private Node left; //左节点
    private Node right; //右节点
    
    //setter getter toString constructor...
    
    //前序遍历 父左右
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //向右子树前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    //中序遍历 左父右
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    //后序编列 左右父
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }

        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
}
复制代码  

查找

• 查找顺序与遍历一致
• 前序查找

 public Node preOrderSearch(int id) {
    if (this.id == id) {
        return this;
    }
    Node res = null;
    if (this.left != null) {
        res = this.left.preOrderSearch(id);
    }
    if (res != null) {
        //左子树找到
        return res;
    }
    if (this.right != null) {
        res = this.right.preOrderSearch(id);
    }
    if (res != null) {
        //左子树找到
        return res;
    }
    return res;
}
复制代码  

• 中序查找

 public Node infixOrderSearch(int id) {
    Node res = null;
    if (this.left != null) {
        res = this.left.preOrderSearch(id);
    }
    if (res != null) {
        //左子树找到
        return res;
    }
    if (this.id == id) {
        return this;
    }

    if (this.right != null) {
        res = this.right.preOrderSearch(id);
    }
    if (res != null) {
        //左子树找到
        return res;
    }
    return res;
}
复制代码  

• 后序查找

 public Node postOrderSearch(int id) {
    Node res = null;
    if (this.right != null) {
        res = this.right.preOrderSearch(id);
    }
    if (res != null) {
        //左子树找到
        return res;
    }
    if (this.left != null) {
        res = this.left.preOrderSearch(id);
    }
    if (res != null) {
        //左子树找到
        return res;
    }
    if (this.id == id) {
        return this;
    }
    return res;
}
复制代码  

• 树中调用

 public Node preOrderSearch(int id) {
    if (this.root != null) {
        return this.root.preOrderSearch(id);
    } else {
        System.out.println("empty");
        return null;
    }
}
public Node infixOrderSearch(int id) {
    if (this.root != null) {
        return this.root.infixOrderSearch(id);
    } else {
        System.out.println("empty");
        return null;
    }
}
public Node postOrderSearch(int id) {
    if (this.root != null) {
        return this.root.postOrderSearch(id);
    } else {
        System.out.println("empty");
        return null;
    }
}
复制代码  

删除

• 删除的节点是叶子节点，删除该节点；删除的非叶子节点，删除该子树
• 找的是，删除节点的父节点，才能干掉删除节点
• 判断是不是root，树中判断root后，再进行子节点的判断

 public void delNode(int id) {
    if (root != null) {
        //判断root是不是要删除的
        if (root.getId() == id) {
            root = null;
        } else {
            root.delNode(id);
        }
    } else {
        System.out.println("empty");
    }
}
复制代码  

• 节点，先判断当前节点的左右子节点是不是，如果不是，继续递归进入，判断左右子节点的子节点

 public void delNode (int id) {
    if (this.left != null && this.left.id == id) {
        this.left = null;
        return;
    }
    if (this.right != null && this.right.id == id) {
        this.right = null;
        return;
    }
    if (this.left != null) {
        this.left.delNode(id);
    }
    if (this.right != null) {
        this.right.delNode(id);
    }
}
复制代码  

修改删除规则

• 如果非叶子节点只有一个节点，那么就用该子节点替代；如果非叶子节点有两个子节点，左子节点替代，右子节点作为左子节点的右子节点
• 但是没有实现，如果左右子节点均有子节点怎么办

 public void delNode (int id) {
    if (this.left != null && this.left.id == id) {
        if (this.left.left == null && this.left.right == null) {
            this.left = null;
        } else if (this.left.left != null && this.left.right == null) {
            //删除的节点只有左节点
            this.left = this.left.left;
        } else if (this.left.left == null && this.left.right != null) {
            //删除的节点只有右节点
            this.left = this.left.right;
        } else {
            //右节点作为左节点的子节点
            this.left.left.right = this.left.right;
            this.left.right = null;
            //左节点替代删除的节点
            this.left = this.left.left;
        }
        return;
    }
    if (this.right != null && this.right.id == id) {
        if (this.right.left == null && this.right.right == null) {
            this.right = null;
        } else if (this.right.left != null && this.right.right == null) {
            //删除的节点只有左节点
            this.right = this.right.left;
        } else if (this.right.left == null && this.right.right != null) {
            //删除的节点只有右节点
            this.right = this.right.right;
        } else {
            //右节点作为左节点的子节点
            this.right.left.right = this.right.right;
            this.right.right = null;
            //左节点替代删除的节点
            this.right = this.right.left;
        }
        return;
    }
    if (this.left != null) {
        this.left.delNode(id);
    }
    if (this.right != null) {
        this.right.delNode(id);
    }
}
复制代码  

顺序存储二叉树

• 数组转换为树
• 第n个元素的左子节点数组中下标为2*n+1，右子节点数组中下标为2*n+2，父节点数组中下标为(n-1)/2，n为在数组中的下标

 class  ArrBinaryTree {
    private int[] arr;
    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }
    public void preOrder() {
        this.preOrder(0);
    }
    //顺序存储二叉的前序遍历
    public void preOrder(int index) {
        //数组为空
        if (arr == null || arr.length == 0) {
            System.out.println("empty");
            return;
        }
        System.out.println(arr[index]);
        //左遍历
        if ((index * 2 + 1) < arr.length) {
            preOrder(index * 2 + 1);
        }
        //右遍历
        if ((index * 2 + 2) < arr.length) {
            preOrder(index * 2 + 2);
        }
    }
}
复制代码  

线索化二叉树

• 对于n个节点的二叉树，含有n+1个指针域，2n-(n-1)一个节点有两个指针，n个节点连接只需要n-1个指针
• 利用二叉链表的空指针域存放指向该节点在某种遍历次序下的前驱和后继节点，按照这个次序遍历的前后节点
• 前序线索化二叉树

 public void threadedNodes(ThreadedNode node) {
    if (node == null) {
        return;
    }
    //先处理当前节点的前驱节点
    if (node.getLeft() == null) {
        node.setLeft(preNode);
        //修改类型，如果是0才能进入递归判断子树
        node.setLeftType(1);
    }
    //处理后继节点
    if (preNode != null && preNode.getRight() == null) {
        //让前驱节点的右指针指向当前节点
        preNode.setRight( node );
        preNode.setRightType(1);
    }
    //每处理一个节点后，让当前节点是下一个节点的前驱节点
    preNode = node;
    if (node.getLeftType() == 0) {
        threadedNodes(node.getLeft());
    }
    if (node.getRightType() == 0) {
        threadedNodes(node.getRight());
    }
}
复制代码  

• 中序线索化二叉树

 public void threadedNodes(ThreadedNode node) {
    if (node == null) {
        return;
    }
    //线索 左父右
    threadedNodes(node.getLeft());
    //先处理当前节点的前驱节点
    if (node.getLeft() == null) {
        node.setLeft(preNode);
        //修改类型
        node.setLeftType(1);
    }
    //处理后继节点，用当前节点来处理前一个节点的后继节点
    if (preNode != null && preNode.getRight() == null) {
        //让前驱节点的右指针指向当前节点
        preNode.setRight(node);
        preNode.setRightType(1);
    }
    //每处理一个节点后，让当前节点是下一个节点的前驱节点
    //按照中序顺序进行排列
    preNode = node;
    threadedNodes(node.getRight());
}
复制代码  

• 后续线索化二叉树

 public void threadedNodes(ThreadedNode node) {
    if (node == null) {
        return;
    }
    threadedNodes(node.getLeft());
    threadedNodes(node.getRight());
    //先处理当前节点的前驱节点
    if (node.getLeft() == null) {
        node.setLeft(preNode);
        //修改类型
        node.setLeftType(1);
    }
    //处理后继节点
    if (preNode != null && preNode.getRight() == null) {
        //让前驱节点的右指针指向当前节点
        preNode.setRight(node);
        preNode.setRightType(1);
    }
    //每处理一个节点后，让当前节点是下一个节点的前驱节点
    preNode = node;
}
复制代码  

遍历线索化二叉树

• 前序遍历线索化二叉树

 public void threadedList() {
    ThreadedNode node = root;
    while (node != null) {
        //一直向左输出，直到找到 LeftType = 1的节点，表明向左到底了
        while (node.getLeftType() == 0) {
            System.out.println(node);
            node = node.getLeft();
        }
        System.out.println(node);
        node = node.getRight();
    }
}
复制代码  

• 中序遍历线索化二叉树

 public void threadedList() {
    ThreadedNode node = root;
    while (node != null) {
        //找到第一个leftType=1的节点
        while (node.getLeftType() == 0) {
            node = node.getLeft();
        }
        System.out.println(node);
        //如果当前节点的右指针是后继节点，就一直输出
        while (node.getRightType() == 1) {
            node = node.getRight();
            System.out.println(node);
        }
        node = node.getRight();
    }
}
复制代码  

• 因为后序遍历顺序为左右父，会出现，左子树输出完毕，回到当前子树的父节点，该父节点有作为右子树左子节点的前驱节点，但是由于该父节点的两个节点左右都有子节点，那么就会导致该父节点通过正常方式无法找到下一个节点，就有了两种处理方式逆序入栈，从右开始入栈和在节点中记录双亲节点，在遍历中记录前一个节点，在遍历完左子树后，如果继续遍历时，节点的右子节点为上一个节点，则要找到节点的双亲节点，遍历右节点，也就是双亲节点
• 后序遍历线索化二叉树（逆序）

 public void threadedList() {
    ThreadedNode node = root;
    Stack<ThreadedNode> stack = new Stack<>();
    while (node != null) {
        //跳出循环说明右边没有了，要往左边找
        while (node.getRightType() == 0) {
            stack.push(node);
            node = node.getRight();
        }
        stack.push(node);
        node = node.getLeft();
    }
    while (!stack.isEmpty()) {
        System.out.println(stack.pop());
    }
}
复制代码  

• 后序遍历线索化二叉树（正序）

 public void threadedList() {
    ThreadedNode node = root;
    ThreadedNode pre = null;
    while (node != null) {
        //找到第一个leftType=1的节点
        while (node.getLeftType() == 0) {
            node = node.getLeft();
        }
        System.out.println(node);
        //该起始左结点的后继节点全部找到，并往回指向了一次
        while (node.getRightType() == 1) {
            //记录上一个节点，为了进行判断；如果上一个节点为某个父节点的右子节点
            //说明，这右半边已经处理完成，要找到双亲节点，进行处理
            pre = node;
            node = node.getRight();
            System.out.println(node);
        }
        //往回指向了根节点，置空，准备跳出循环
        if (node == root) {
            node = null;
        }
        //上一个节点为该节点的右子节点，说明这个节点的树结构已经走完，找到该节点的双亲节点
        while (node != null && node.getRight() == pre) {
            pre = node;
            node = node.getParent();
        }
        //处理右子树，并从下面一层开始，与上一轮完毕的左子节点是兄弟节点
        if (node != null && node.getRightType() == 0) {
            node = node.getRight();
        }
    }
}