二叉树的四种遍历方式(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());
}