算法-二叉树

1. 二叉树的遍历

说明：假设给定二叉树的树形结构以及对应节点的数据结构如下：

1
2
3
4
5
6
7
8

class Node {
    int val;
    Node left;
    Node right;
    Node(int val) {
        this.val = val;
    }
}

1.1 前序遍历

前序遍历（父 - 左 - 右）指：对每一个节点，都优先遍历父节点；然后是左子节点；最后是右子节点。对应图例的二叉树，则遍历顺序为：

• 从根结点 A 出发，遍历 A
• A 具有左子节点 B，遍历 B
• B 具有左子节点 D，遍历 D
• D 不具有左子节点，但具有右子节点 H，遍历 H
• H 不具有左子节点，但具有右子节点 K，遍历 K
• K 不具有左子节点，也不具有右子节点，返回 H
• H 遍历完毕，返回 D
• D 遍历完毕，返回 B
• B 具有右子节点 E，遍历 E
• E 不具有左子节点，也不具有右子节点，返回 B
• B 遍历完毕，返回 A
• A 具有右子节点 C，遍历 C
• ......

1

A -> B -> D -> H -> K -> E -> C -> F -> I -> L -> G -> J

1
2
3
4
5
6
7
8
9
10
11
12
13

class BinaryTreeErgodic {
    public void preOrder(Node parent) {
        if (parent == null) {
            return;
        }
        // 优先遍历父节点，用 println 表示遍历到。
        System.out.println("Val: " + parent.val);
        // 然后遍历左子节点。
        preOrder(parent.left);
        // 最后遍历右子节点。
        preOrder(parent.right);
    }
}

1.2 中序遍历

中序遍历（左 - 父 - 右）指：对每一个节点，都优先深度遍历左子节点，直到某个节点没有左子节点；然后遍历父节点；最后遍历右子节点。对应图例的二叉树，则遍历顺序为：

• 从根结点 A 出发，A 具有左子节点 B
• B 具有左子节点 D
• D 不具有左子节点，遍历 D 自己
• D 具有右子节点 H
• H 不具有左子节点，遍历 H 自己
• H 具有右子节点 K
• K 不具有左子节点，遍历 K 自己
• K 不具有右子节点，遍历完毕返回 H
• H 遍历完毕，返回 D
• D 遍历完毕，返回 B
• B 左子节点遍历完毕，遍历 B 自己
• B 具有右子节点 E
• E 不具有左子节点，遍历 E 自己
• E 不具有右子节点，遍历完毕返回 B
• B 遍历完毕，返回 A
• A 左子节点遍历完毕，遍历 A 自己
• A 具有右子节点 C
• ......

1

D -> H -> K -> B -> E -> A -> F -> L -> I -> C -> G -> J

1
2
3
4
5
6
7
8
9
10
11
12
13

class BinaryTreeErgodic {
    public void midOrder(node parent) {
        if (parent == null) {
            return;
        }
        // 优先深度遍历左子节点。
        preOrder(parent.left);
        // 直到左子节点遍历完毕，则遍历自己，用 println 表示遍历到。
        System.out.println("Val: " + parent.val);
        // 最后遍历右子节点。
        preOrder(parent.right);
    }
}

1.3 后序遍历

后序遍历（左 - 右 - 父）指：对每一个节点，都优先深度遍历左子节点，直到某个节点没有左子节点；然后深度遍历右子节点；最后遍历父节点。对应图例的二叉树，则遍历顺序为：

• 从根结点 A 出发，A 具有左子节点 B
• B 具有左子节点 D
• D 不具有左子节点，但具有右子节点 H
• H 不具有左子节点，但具有右子节点 K
• K 不具有左子节点，也不具有右子节点，遍历 K 自己
• K 遍历完毕，返回 H
• H 左子节点遍历完毕，右子节点遍历完毕，遍历 H 自己
• H 遍历完毕，返回 D
• D 左子节点遍历完毕，右子节点遍历完毕，遍历 D 自己
• D 遍历完毕，返回 B
• B 左子节点遍历完毕，具有右子节点 E
• E 不具有左子节点，也不具有右子节点，遍历 E 自己
• E 遍历完毕，返回 B
• B 左子节点遍历完毕，右子节点遍历完毕，遍历 B 自己
• B 遍历完毕，返回 A
• A 左子节点遍历完毕，具有右子节点 C
• C 具有左子节点 F
• F 不具有左子节点，但具有右子节点 I
• I 具有左子节点 L
• L 不具有左子节点，也不具有右子节点，遍历 L 自己
• ......

1

K -> H -> D -> E -> B -> L -> I -> F -> J -> G -> C -> A

1
2
3
4
5
6
7
8
9
10
11
12
13

class BinaryTreeErgodic {
    public void midOrder(node parent) {
        if (parent == null) {
            return;
        }
        // 优先深度遍历左子节点。
        preOrder(parent.left);
        // 然后遍历右子节点。
        preOrder(parent.right);
        // 直到左右子节点都遍历完毕，最后遍历自己，用 println 表示遍历到。
        System.out.println("Val: " + parent.val);
    }
}