二叉树遍历算法总结

三类:

    • 系统栈
    • 自己实现的栈
  • 线索:Morris preorder/inorder/postorder traversal
  • 其他edge-crawling方式:Schorr-Waite graph marking algorithm、Lindstrom-Dwyer algorithm
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
#include <algorithm>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
struct Node {
int key;
int s; // only used by Schorr-Waite
Node *l, *r;
Node(int key, Node *l, Node *r) : key(key), l(l), r(r), s(0) {}
void visit() const {
printf("%d\n", key);
}
};
enum Type { PREORDER, INORDER, POSTORDER };
/*
preorder模拟栈版:栈中存放的节点`x`表示之后待遍历`x`的子树。
*/
void preorder(Node *p)
{
if (p) {
p->visit();
preorder(p->l);
preorder(p->r);
}
}
/*
inorder模拟栈版:栈中存放的节点`x`表示`x`待访问,且之后遍历`x`的右子树。
*/
void inorder(Node *p)
{
if (p) {
inorder(p->l);
p->visit();
inorder(p->r);
}
}
void postorder(Node *p)
{
if (p) {
postorder(p->l);
postorder(p->r);
p->visit();
}
}
void preorder_stack(Node *p)
{
stack<Node *> s;
for(;;) {
while (p) {
p->visit();
if (p->r)
s.push(p->r);
p = p->l;
}
if (s.empty()) break;
p = s.top();
s.pop();
}
}
void inorder_stack(Node *p)
{
stack<Node *> s;
for(;;) {
while (p) {
s.push(p);
p = p->l;
}
if (s.empty()) break;
p = s.top();
s.pop();
p->visit();
p = p->r;
}
}
/*
栈中存放的节点`x`表示两种阶段之一:
1. 当前在访问`x`左子树,之后待遍历`x`的右子树,然后访问`x`。
2. 当前在访问`x`的右子树,之后待访问`x`。
祖先节点进入阶段2的时刻晚于后裔节点。
外层循环开始处即`while (p) {`行,以下两个条件之一满足:
1. `p`非NULL,需要遍历`p`子树,栈上存放`p`的所有祖先。
2. `p`为NULL,栈上是栈顶及栈顶的所有祖先,下一个访问的是栈顶。
遍历一棵子树的方式是沿着左孩子链接下溯并把沿途节点都压栈,直到遇到NULL。
若遇到的最后一个节点`x`有右孩子`y`,则当前指针置为`y`,`x`及`x`的一些连续的祖先进入阶段2;
否则(第二个while循环实现这一复杂逻辑)说明`x`已在阶段2,访问`x`,
同时`x`一些连续的祖先也进入阶段2了,也需要访问并从栈中弹出。
*/
void postorder_stack(Node *p)
{
stack<Node *> s;
for(;;) {
while (p) {
s.push(p);
p = p->l;
}
while (! s.empty() && s.top()->r == p) {
p = s.top();
s.pop();
p->visit();
}
if (s.empty()) break;
p = s.top()->r;
}
}
void postorder2_stack(Node *p)
{
stack<Node *> s;
for(;;) {
while (p) {
if (p->r)
s.push(p->r);
s.push(p);
p = p->l;
}
if (s.empty()) break;
p = s.top();
s.pop();
if (! s.empty() && p->r == s.top()) {
s.pop();
s.push(p);
p = p->r;
} else {
p->visit();
p = NULL;
}
}
}
/*
按层级顺序访问,使用队列进行BFS
*/
void level_order(Node *p)
{
queue<Node *> q;
if (p) {
q.push(p);
while (! q.empty()) {
p = q.front();
q.pop();
p->visit();
if (p->l)
q.push(p->l);
if (p->r)
q.push(p->r);
}
}
}
/*
preorder或inorder可以实现O(1)额外空间的遍历,
方法是把右孩子为空的节点的右孩子改造成中序后继的线索指针。
*/
void morris_traversal(Node *p, Type t)
{
while (p) {
Node *q = p->l;
if (q) {
while (q->r && q->r != p) q = q->r;
if (q->r == p)
q->r = NULL;
else {
if (t == PREORDER)
p->visit();
q->r = p;
p = p->l;
continue;
}
} else if (t == PREORDER)
p->visit();
if (t == INORDER)
p->visit();
p = p->r;
}
}
// morris_postorder_traversal的辅助函数
void reverse_right_chain(Node *x, Node *y)
{
Node *p = x, *q = x->r, *r;
while (p != y) {
r = q->r;
q->r = p;
p = q;
q = r;
}
}
/*
增量构造线索进行post-order遍历比较复杂
*/
void morris_postorder_traversal(Node *p)
{
Node aux;
aux.l = p;
aux.r = NULL;
p = &aux;
while (p) {
Node *q = p->l;
if (q) {
while (q->r && q->r != p) q = q->r;
if (q->r == p) {
reverse_right_chain(p->l, q);
for (Node *r = q; ; r = r->r) {
r->visit();
if (r == p->l) break;
}
reverse_right_chain(q, p->l);
q->r = NULL;
} else {
q->r = p;
p = p->l;
continue;
}
}
p = p->r;
}
}
/* Schorr-Waite graph marking algorithm
*
* 该算法需要在节点信息里额外维护一个域 s,表示遍历过程中的访问次数,有如下几种取值:
* 0: 尚未访问
* 1: 访问过1次(preorder),尚未遍历其左右子树
* 2: 访问过2次(inorder),已遍历其左子树,尚未遍历其右子树
* 3: 访问过3次(postorder),已遍历其左右子树
*
* 访问到 x 时,其祖先节点及它们的子树遍历进度(在遍历左子树还是右子树)是通过栈维护的。
* 该算法把祖先节点下溯的指针翻转,再通过设置一个父节点指针 p 以把祖先节点组织为一个链。
* 通过 s 可以知道各祖先节点当前在遍历左子树还是右子树。
*
* 若注释掉代码中的 x->s = 0; 则在算法执行完后遍历到的节点的 s 值为3,可以判断节点是否被访问过。
*
* 该算法可用于遍历一般的有向图,也需要注释掉 x->s = 0。带有 q 个指针域的节点将被访问 q+1 次。
*/
void schorr_waite(Node *x, Type t)
{
if (! x) return;
Node *y, *p = NULL;
for(;;) {
if ((int)t == (int)x->s)
x->visit();
if (x->s < 2) {
x->s++;
y = x->s == 1 ? x->l : x->r;
if (y && y->s == 0) {
(x->s == 1 ? x->l : x->r) = p;
p = x;
x = y;
}
} else {
x->s = 0; // reset to 0
if (! p) return;
y = x;
x = p;
if (x->s == 1)
p = x->l, x->l = y;
else
p = x->r, x->r = y;
}
}
}
// http://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf
// 下面是一种变体,也可用于一般有向图,每个节点都有两个指针域
// 原始的Schorr-Waite在下溯时把指针和 p 交换,上溯时再交换回来
// 该方法使用四指针置换和三指针置换来统一几种逻辑判断
void schorr_waite_alternative(Node *p, Type t)
{
Node *q = (Node *)-1;
while (p != (Node *)-1) {
if ((int)t == (int)p->s)
p->visit();
p->s++;
if (p->s == 3 || p->l && p->l->s == 0) {
Node *r = p->l;
p->l = p->r;
p->r = q;
q = p;
p = r;
} else {
Node *r = p->l;
p->l = p->r;
p->r = q;
q = r;
}
}
}
// Lindstrom-Dwyer algorithm
// Schorr-Waite的变体,对于二叉树,上面 schorr_waite_alternative 的代码可以进一步简化
// 考察条件 p->s == 3 || p->l && p->l->s == 0
// 若 p->s != 3 则有 1 <= p->s && p->s <= 2
// 此时 p->l 为原节点的左子树或右子树,因为是树,不存在其他节点的指向它们
// 因此 p->l 若非 NULL 则必有 p->l->s != 0
// 该条件只有在 p->l == NULL 时不成立。即使不成立,我们依然可以套用四指针置换
// 但需要把 p(此时为NULL) 设为 q,把 q 设为 NULL
// 之后 s 仅用于判断节点访问次数,不再参与逻辑控制
// 如果不在乎一个节点调用 visit 三次的话,可以省去 s
void lindstrom_dwyer(Node *p)
{
Node *q = (Node *)-1;
while (p != (Node *)-1) {
p->visit();
Node *r = p->l;
p->l = p->r;
p->r = q;
q = p;
p = r;
if (! p) p = q, q = NULL;
}
}
int main()
{
Node *a[7];
for (int i = 7; i--; )
a[i] = new Node(i, i*2+1 < 7 ? a[i*2+1] : NULL, i*2+2 < 7 ? a[i*2+2] : NULL);
preorder(a[0]);
inorder(a[0]);
postorder(a[0]);
level_order(a[0]);
morris_traversal(a[0], PREORDER);
morris_traversal(a[0], INORDER);
preorder_stack(a[0]);
inorder_stack(a[0]);
postorder_stack(a[0]);
postorder2_stack(a[0]);
schorr_waite(a[0], PREORDER);
schorr_waite(a[0], INORDER);
schorr_waite(a[0], POSTORDER);
schorr_waite_alternative(a[0], PREORDER);
schorr_waite_alternative(a[0], INORDER);
schorr_waite_alternative(a[0], POSTORDER);
lindstrom_dwyer(a[0]);
}