二叉树基础知识

1、什么是二叉树

二叉树是最多只有两个子孩子的树

二叉树示意图

2、什么是满二叉树

满二叉树就是除了最大层有叶子节点之外，其它层都没有叶子节点，且最大层之外的每个节点都有两个子节点

满二叉树示意图

3、什么是完全二叉树

完全二叉树就是除了最大层和导数第二层之外，其它层都没叶子节点，且其它层的每个节点都有两个子孩子。最大层的叶子节点，从左到右依次排列，不间断。也就是在一颗满二叉树的基础上，如果要缺失节点的话，只能在最大层的最右边。

完全二叉树示意图

4、什么是二叉查找树

二叉查找树任意节点上的左孩子的值都比根节点小，右孩子的值都比根节点大

二叉查找树示意图

5、什么是平衡二叉树

平衡二叉树任意节点上的两颗子树之间的高度差不会超过1。有时候平衡二叉树也只平衡二叉查找树，那就这棵树还要有二叉查找树的特性

平衡二叉树示意图

6、遍历二叉树

遍历二叉树有三种方式

1. 先序遍历：先遍历根节点，再遍历左节点，然后再遍历右节点
2. 中序遍历：先遍历左节点，再遍历根节点，然后再遍历右节点
3. 后序遍历：先遍历左节点，再遍历右节点，然后在遍历根节点

6.1 先序遍历

图6.1

先序遍历图6.1得到的结果是：1000,500,400,300,450,2000,1500,2100

递归实现

private static void traversePre(StringBuilder builder, Node root) {
        if (root == null) {
            return;
        }
        builder.append(root.value + ",");
        traversePre(builder, root.left);
        traversePre(builder, root.right);
    }

非递归实现

算法思路1：

1. 将当前节点指向根节点
2. 开始遍历当前节点，先输出节点值，然后将当前节点入栈，移动指针到其左孩子
3. 如果左孩子不为空，重复第一步
4. 如果左孩子为空，则开始遍历栈顶元素的右孩子
5. 栈顶元素出栈，辅助给当前节点，判断其右孩子是否为空
6. 如果其右孩子为空，继续回退栈中元素
7. 如果其右孩子不为空，将当前节点指向其右孩子，重复从第2步开始的步骤

private static void traversePre3(StringBuilder builder, Node root) {
    Stack<Node> stack = new Stack<>();
    Node temp = root;
    while (!stack.isEmpty() || temp != null) {
        while (temp != null) {
            builder.append(temp.value + ",");
            stack.push(temp);
            temp = temp.left;
        }
        if (!stack.isEmpty()) {
            temp = stack.pop();
            if (temp.right == null) {
                temp = null;
            } else {
                temp = temp.right;
            }
        }
    }
}

算法思路2：

1. 将当前节点指向根节点，将更节点入栈
2. 栈顶元素出栈，打印其值
3. 判断其右孩子是否为空，不为空，则将其入栈；然后判断其左孩子是否为空，不为空则入栈
4. 重复第二步开始的步骤

private static void traversePre2(StringBuilder builder, Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node temp = stack.pop();
        builder.append(temp.value + ",");
        if (temp.right != null) {
            stack.push(temp.right);
        }
        if (temp.left != null) {
            stack.push(temp.left);
        }
    }
}

6.2 中序遍历

图6.2

中序遍历图6.2得到的结果是：300,400,450,500,1000,1500,2000,2100

递归实现

private static void traverseMide(StringBuilder builder, Node root) {
        if (root == null) {
            return;
        }
        traverseMide(builder, root.left);//遍历左孩子
        builder.append(root.value + ",");//打印更节点
        traverseMide(builder, root.right);//遍历有孩子
    }

非递归实现

算法思路

1. 将当前节点指向根节点
2. 判断当前节点是否为空，不为空则将当前节点入栈，并将当前节点指向其左孩子
3. 如果当前节点为空，则开始回溯栈中元素
4. 栈顶元素出栈，并赋值给当前节点，判断其右孩子是否为空
5. 如果其右孩子不为空，将当前节点指向其右孩子，重复从第二步开始的步骤
6. 如果其右孩子为空，则继续回溯栈顶元素

private static void traverseMide2(StringBuilder builder, Node root) {
    Stack<Node> stack = new Stack<>();//缓存要回溯的节点
    Node temp = root;
    while (temp != null || !stack.isEmpty()) {
        while (temp != null) {
            stack.push(temp);
            temp = temp.left;
        }
        if (!stack.isEmpty()) {
            temp = stack.pop();
            builder.append(temp.value + ",");//打印节点
            if (temp.right != null) {
                temp = temp.right;
            } else {
                temp = null;
            }
        }
    }
}

6.3 后序遍历

图6.3

后续遍历图6.3的结果是：300,450,400,500,1500,2100,2000,1000

递归实现

private static void traverseBehind(StringBuilder builder, Node root) {
        if (root == null) {
            return;
        }
        traverseBehind(builder, root.left);
        traverseBehind(builder, root.right);
        builder.append(root.value + ",");
    }

非递归实现

算法思路

1. 将当前节点指向根节点
2. 如果当前节点不为空，则将当前节点入栈，并将当前节点指向其左孩子
3. 如果当前节点为空，则开始回溯栈中节点
4. 获取栈顶元素，并赋值给当前节点，判断当前节点的右子树是否为空，右子树是否遍历过
5. 如果其右子树为空，或者右子树已经遍历过了，则栈顶元素出栈，打印当前节点的值，并记录当前遍历的节点，继续回溯栈中元素（重复第4步开始的步骤）

6. 如果其右孩子不为空且其右子树没有遍历过，则将当前节点指向其右孩子，重复第2步开始的步骤
   示意图

   
   后续遍历非递归示意图

private static void traverseBehind2(StringBuilder builder, Node root) {
    Stack<Node> stack = new Stack<>();//存放要回溯的节点
    Node temp = root;
    Node pre = null;
    while (temp != null || !stack.isEmpty()) {
        while (temp != null) {
            stack.push(temp);
            temp = temp.left;
        }
        if (!stack.isEmpty()) {
            temp = stack.peek();
            if (temp.right == null || temp.right == pre) {
                temp = stack.pop();
                builder.append(temp.value + ",");
                pre = temp;
                temp = null;
            } else {
                temp = temp.right;
            }
        }
    }
}