二叉树的四种遍历方式（Java 实现）

发表于

二叉树的遍历是面试经常会被考察的知识点，有些甚至要求当场手写实现过程。

遍历方式常见的分为两大类共四种：

  • 广度优先遍历

    • 层序遍历

  • 深度优先遍历

    • 前序遍历（先序遍历）

    • 中序遍历

    • 后序遍历

数据结构

在开始遍历之前，我们需要先构建一棵树，这里用 JSON 方式定义一棵树，然后用 FastJson 读取到 Java 的数据结构中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
{
    "value": 1,
    "left": {
        "value": 2,
        "left": {
            "value": 4,
            "left": null,
            "right": null
        },
        "right": {
            "value": 5,
            "left": null,
            "right": null
        }
    },
    "right": {
        "value": 3,
        "left": {
            "value": 6,
            "left": null,
            "right": null
        },
        "right": null
    }
}

Java 类：

1
2
3
4
5
6
7
8
9
10
@Getter
@Setter
class Node {
    /** 当前节点值 */
    private int value;
    /** 左节点 */
    private Node left;
    /** 右节点 */
    private Node right;
}

初始化构建树：

1
2
3
4
5
/** 初始化构建树 */
    private Node init() {
        String strTree = "{\"value\":1,\"left\":{\"value\":2,\"left\":{\"value\":4,\"left\":null,\"right\":null},\"right\":{\"value\":5,\"left\":null,\"right\":null}},\"right\":{\"value\":3,\"left\":{\"value\":6,\"left\":null,\"right\":null},\"right\":null}}";
        return JSON.parseObject(strTree, Node.class);
    }

层序遍历

层序遍历是比较接近人的思维方式的一种遍历方法，将二叉树的每一层分别遍历，直到最后的叶子节点被全部遍历完。

1575445665606

为了简化遍历过程，我们需要引入队列（Queue），队列的特性是：先进先出，从队头出列，从队尾入列。Java 中 LinkedList 就是一种 Queue。

思路（递归方式）：先出列一个节点，输出该节点，并判断该节点下有误左右子树，如果有的话，把左右子树入列，然后递归执行，直到队列为空。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void testLevelOrder() {
    Node node = init();
    
    System.out.print("层序遍历：");
    Queue<Node> queue = new LinkedList<>();
    queue.offer(node); // 根入列
    levelOrder(queue);
}

/** 层序遍历 */
private void levelOrder(Queue<Node> queue) {
    if (queue.isEmpty()) { // 队列为空，退出循环
        return;
    }
    // 出列，并输出
    Node head = queue.poll();
    System.out.print(head.getValue());
    // 左右子树不为空入列
    if (head.getLeft() != null) {
        queue.offer(head.getLeft());
    }
    if (head.getRight() != null) {
        queue.offer(head.getRight());
    }
    // 循环
    levelOrder(queue);
}

前序遍历，中序遍历，后序遍历

这三种深度优先的遍历方式用递归很方便实现。它们的区别只是对根和左右子树的遍历先后顺序不同而已。

前序遍历（NLR）：先访问根节点，再访问左子树，最后访问右子树。

1575445707773

中序遍历（LNR）：先左子树，再根节点，最后右子树。

1575445746314

后序遍历（LRN）：先左子树，再右子树，最后根节点。

1575445790074

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public void test() {
    Node node = init();
    
    System.out.print("前序遍历：");
    preOrder(node);
    System.out.println();

    System.out.print("中序遍历：");
    inOrder(node);
    System.out.println();

    System.out.print("后序遍历：");
    pastOrder(node);
    System.out.println();
}
    
/** 前序遍历 */
private void preOrder(Node node) {
    System.out.print(node.getValue());
    if (node.getLeft() != null) {
        preOrder(node.getLeft());
    }
    if (node.getRight() != null) {
        preOrder(node.getRight());
    }
}

/** 中序遍历 */
private void inOrder(Node node) {
    if (node.getLeft() != null) {
        inOrder(node.getLeft());
    }
    System.out.print(node.getValue());
    if (node.getRight() != null) {
        inOrder(node.getRight());
    }
}

/** 后序遍历 */
private void pastOrder(Node node) {
    if (node.getLeft() != null) {
        pastOrder(node.getLeft());
    }
    if (node.getRight() != null) {
        pastOrder(node.getRight());
    }
    System.out.print(node.getValue());
}