二叉树遍历算法总结

关于先序遍历、中序遍历、后序遍历的递归和非递归版本以及层序遍历的总结。

二叉树节点的定义

1
2
3
4
5
6
7
8
9
public static class Node {
public int value;
public Node left;
public Node right;

public Node(int value) {
this.value = value;
}
}

先序中序后序中的“序”指的是打印根的顺序。

先序遍历

根->左子树->右子树

递归版先序遍历

思路:先打印自己,再对左子树进行先序遍历,再对右子树进行先序遍历

1
2
3
4
5
6
public static void preOrderRecur(Node root) {
if (root == null) return;
System.out.print(root.value + " ");
preOrderRecur(root.left);
preOrderRecur(root.right);
}

非递归版先序遍历

思路:用栈实现,弹出一个节点作为当前节点,打印当前节点,然后对于当前节点有右先压右,有左后压左。先压右后压左,弹出为先弹左后弹右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void preOrderUnrecur(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
stack.push(root);
Node cur;
while (!stack.empty()) {
cur = stack.pop();
// 先打印自己
System.out.print(cur.value + " ");
// 有右先压右
if (cur.right != null)
stack.push(cur.right);
// 有左后压左
if (cur.left != null)
stack.push(cur.left);
}
}

中序遍历

左子树->根->右子树

递归版中序遍历

思路:对左子树进行中序遍历,打印自己,对右子树进行中序遍历

1
2
3
4
5
6
public static void inOrderRecur(Node root) {
if (root == null) return;
inOrderRecur(root.left);
System.out.print(root.value + " ");
inOrderRecur(root.right);
}

非递归版中序遍历

思路:用栈实现,当前节点不为空或者栈不为空继续while(只有当前节点为空,栈也为空才退出循环):当前节点不为空,当前节点压入栈,当前节点往左跑(左边界一压压一溜);当前节点为空,从栈中拿一个打印,当前节点向右跑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void inOrderUnrecur(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
Node cur = root;
while (cur != null || !stack.empty()) { // 当前节点不为空或者栈不为空
if (cur != null) { // 当前节点不为空
stack.push(cur); // 压栈
cur = cur.left; // 向左走
} else { // 当前节点为空但是栈不为空
cur = stack.pop(); // 弹出一个节点
System.out.print(cur.value + " "); // 打印
cur = cur.right; // 当前节点向右走
}
}
}

后序遍历

左子树->右子树->根

递归版后序遍历

思路:先对左子树进行后序遍历,再对右子树进行后序遍历,再打印自己

1
2
3
4
5
6
public static void posOrderRecur(Node root) {
if (root == null) return;
posOrderRecur(root.left);
posOrderRecur(root.right);
System.out.print(root.value + " ");
}

非递归版后序遍历

思路:后序:左-右-中,通过 中-左-右(先序:用栈实现,弹出一个节点作为当前节点,打印当前节点,然后对于当前节点有右先压右,有左后压左。先压右后压左,弹出为先弹左后弹右) 左右互换得到中-右-左,打印的时候不打印,存到栈里去,存完把所有栈中的元素打印 -> 左-右-中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void posOrderUnrecur(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
Stack<Node> storeStack = new Stack<>();
stack.push(root);
Node cur;
while (!stack.empty()) {
cur = stack.pop();
storeStack.push(cur);
if (cur.left != null)
stack.push(cur.left);
if (cur.right != null)
stack.push(cur.right);
}
while (!storeStack.empty()) {
System.out.print(storeStack.pop().value + " ");
}
}

优化:其实storeStack栈只需要存数就可以了,不需要存left,right指针,所以只需要用一个Stack<Integer>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void posOrderUnrecur(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
Stack<Integer> storeStack = new Stack<>();
stack.push(root);
Node cur;
while (!stack.empty()) {
cur = stack.pop();
storeStack.push(cur.value);
if (cur.left != null)
stack.push(cur.left);
if (cur.right != null)
stack.push(cur.right);
}
while (!storeStack.empty()) {
System.out.print(storeStack.pop() + " ");
}
}

层序遍历

思路:先进先出,用队列实现。弹一个出来并打印,然后把分别左儿子右儿子加进去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void layerTraversal(Node root) {
if (root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
Node cur;
while (!queue.isEmpty()) {
cur = queue.poll();
System.out.print(cur.value + " ");
if (cur.left != null)
queue.add(cur.left);
if (cur.right != null)
queue.add(cur.right);
}
}

完整的程序:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
package tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class PreInPosLayerTraversal {
public static class Node {
public int value;
public Node left;
public Node right;

public Node(int value) {
this.value = value;
}
}

/*=====================================================================================*/
// 对左子树进行中序遍历,打印自己,对右子树进行中序遍历
public static void preOrderRecur(Node root) {
if (root == null) return;
System.out.print(root.value + " ");
preOrderRecur(root.left);
preOrderRecur(root.right);
}

// 用栈实现,弹出一个节点作为当前节点,打印当前节点,
// 然后对于当前节点有右先压右,有左后压左。
// 先压右后压左,弹出为先弹左后弹右
public static void preOrderUnrecur(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
stack.push(root);
Node cur;
while (!stack.empty()) {
cur = stack.pop();
// 先打印自己
System.out.print(cur.value + " ");
// 有右先压右
if (cur.right != null)
stack.push(cur.right);
// 有左后压左
if (cur.left != null)
stack.push(cur.left);
}
}

/*=====================================================================================*/
// 对左子树进行中序遍历,打印自己,对右子树进行中序遍历
public static void inOrderRecur(Node root) {
if (root == null) return;
inOrderRecur(root.left);
System.out.print(root.value + " ");
inOrderRecur(root.right);
}

// 用栈实现,当前节点不为空或者栈不为空继续while(只有当前节点为空,栈也为空才退出循环):
// 当前节点不为空,当前节点压入栈,当前节点往左跑(左边界一压压一溜);
// 当前节点为空,从栈中拿一个打印,当前节点向右跑
public static void inOrderUnrecur(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
Node cur = root;
while (cur != null || !stack.empty()) {
if (cur != null) { // 当前节点不为空
stack.push(cur);
cur = cur.left;
} else { // 当前节点为空,栈不为空
cur = stack.pop();
System.out.print(cur.value + " ");
cur = cur.right;
}
}
}

/*=====================================================================================*/
// 先对左子树进行后序遍历,再对右子树进行后序遍历,再打印自己
public static void posOrderRecur(Node root) {
if (root == null) return;
posOrderRecur(root.left);
posOrderRecur(root.right);
System.out.print(root.value + " ");
}

// 后序:左-右-中,通过 中-左-右
// (回顾先序:用栈实现,弹出一个节点作为当前节点,打印当前节点,
// 然后对于当前节点有右先压右,有左后压左。
// 先压右后压左,弹出为先弹左后弹右)
// 对于先序左右互换得到中-右-左,
// 打印的时候不打印,存到栈里去,
// 存完把所有栈中的元素打印 -> 左-右-中
public static void posOrderUnrecur(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
Stack<Integer> storeStack = new Stack<>();
stack.push(root);
Node cur;
while (!stack.empty()) {
cur = stack.pop();
storeStack.push(cur.value);
if (cur.left != null)
stack.push(cur.left);
if (cur.right != null)
stack.push(cur.right);
}
while (!storeStack.empty()) {
System.out.print(storeStack.pop() + " ");
}
}

/*=====================================================================================*/
// 先进先出,用队列实现。弹一个出来,把左边右边加进去
public static void layerTraversal(Node root) {
if (root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
Node cur;
while (!queue.isEmpty()) {
cur = queue.poll();
System.out.print(cur.value + " ");
if (cur.left != null)
queue.add(cur.left);
if (cur.right != null)
queue.add(cur.right);
}
}

/*=====================================================================================*/
// print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}

public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}

public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}

/*=====================================================================================*/
public static void main(String[] args) {
Node head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
printTree(head);

// recursive
System.out.println("==============recursive==============");
System.out.print("pre-order: ");
preOrderRecur(head);
System.out.println();
System.out.print("in-order: ");
inOrderRecur(head);
System.out.println();
System.out.print("pos-order: ");
posOrderRecur(head);
System.out.println();

// unrecursive
System.out.println("============unrecursive=============");
System.out.print("pre-order: ");
preOrderUnrecur(head);
System.out.println();
System.out.print("in-order: ");
inOrderUnrecur(head);
System.out.println();
System.out.print("pos-order: ");
posOrderUnrecur(head);
System.out.println();

// layer
System.out.println("============layer=============");
layerTraversal(head);
}
}
谢谢小天使请我吃糖果
0%