本文是2016年3月16日写的，记录当时学习二叉树三种深度优先遍历的笔记。时隔两年，准备面试阶段重新复习二叉树，翻到之前写的这个笔记，读起来甚至觉得还不错，因此整理放在这里，原文为$\LaTeX$文件，放在GitHub上：bintree-traversal
本文中的二叉树的深度优先遍历，特指非递归形式的二叉树遍历。因为递归形式的很好理解，没必要在这里赘述。本文记录三种非递归形式的深度优先遍历，方法都来源于Adam Drozdek的C++数据结构与算法（第四版），主要是加入了我自己的理解与注释。三种方法分别为栈方法、线索树、Morris算法。
首先定义树的基本结构，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class BSTNode {
int val;
BSTNode *left, *right;
BSTNode() {
val = 0;
left = nullptr;
right = nullptr;
}
BSTNode(int v, BSTNode* l = nullptr, BSTNode* r = nullptr):
val(v), left(l), right(r) {}
}
void visit(BSTNode* p) {
std::cout << p->val << " ";
}
|
1. 前序遍历
前序遍历的递归形式属于尾递归，很容易改为非递归形式。首先将根节点入栈，之后进入循环。循环过程为：
- 从栈中弹出一个节点并访问；
- 如果该节点有右子节点，那么右子节点入栈；
- 如果该节点有左子节点，那么左子节点入栈。
循环条件为栈不为空。那么很容易转化为代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void iterativePreorder(BSTNode* root) {
stack<BSTNode*> travStack;
BSTNode* p =root;
if (p != nullptr) {
travStack.push(p);
}
while (! travStack.empty()) {
p = travStack.top();
travStack.pop();
visit(p);
if (p->right != nullptr) {
travStack.push(p->right);
}
if (p->left != nullptr) {
travStack.push(p->left);
}
}
}
|
2. 后序遍历
从左到右的后序遍历产生的序列（LRV）与从右到左的前序遍历（VRL）得到的逆序列相同，这样就很容易将前序遍历的算法改为后序遍历。只要再多加一个栈即可，将前序遍历访问节点的操作改为将该节点压栈，等遍历结束后，将栈的内容依次输出即可。
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
| void iterativePostorder(BSTNode* root) {
stack<BSTNode*> travStack;
stack<BSTNode*> postTravNode;
BSTNode* p =root;
if (p != nullptr) {
travStack.push(p);
}
while (! travStack.empty()) {
p = travStack.top();
travStack.pop();
postTravNode.push(p);
if (p->left != nullptr) {
travStack.push(p->right);
}
if (p->right != nullptr) {
travStack.push(p->left);
}
}
while(! postTravNode.empty()) {
p = postTravNode.top();
postTravNode.pop();
visit(p);
}
}
|
上面的方法多少有点投机取巧的意思，本质上还是前序遍历。因此下面一个方法是从后序的角度来考虑的。一个节点如果有左子节点，那么就应该继续深入它的左子树，把沿途经过的节点都入栈，直到达到没有左子节点的节点，这个节点不入栈，接下来直接考察这个节点。访问过一个节点的左子树后（也包括左子树为空的情况），要看它有没有右子树（即首先查看有没有右子节点），如果有，那么首先访问右子树。如果没有右子树，或者右子树已经访问过了，就访问当前节点。判断是否访问过右子树的方法是用一个辅助指针，指向当前节点的前一个访问节点，如果在访问当前节点时已经访问过它的右子节点了，那么这个辅助指针就指向它的右子节点，因此只要将辅助指针与当前节点的右子节点进行判等比对即可。
总结如下：
- 有两个子节点的节点入栈两次，一次入栈发生在访问左子树之前，一次入栈发生在访问右子树之前；有两次入栈，那么这两次入栈之间显然要有一次出栈，出栈的情况就是在左子树访问完成后，要把当前节点弹出，如果有右子树并且右子树没有被访问过，就又要把该节点入栈；
- 有一个子节点的节点入栈一次；
- 没有子节点的节点不入栈。
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
| void ietrativaPostorder(BSTNode* root) {
stack<BSTNode*> travStack;
BSTNode *p = root, *q = root;
while (p != nullptr) {
for (; p->left != nullptr; p = p->left) {
travStack.push(p);
}
while (p->right == nullptr || p->right == q) {
visit(p);
q = p;
if (travStack.empty()) {
return;
}
p = travStack.top();
travStack.pop();
}
travStack.push(p);
p = p->right;
}
}
|
3. 中序遍历
关于中序遍历，这本书上有这样的话：
iterativeInorder()只能在一种情况下使用：非递归实现的执行时间更短，同时函数在程序中经常调用。否则，就应使用递归版本的中序遍历而不是迭代版本。
这是因为作者认为中序遍历的迭代版本不易理解。我看了这本书的方法后，觉得比邓俊辉那本书好理解多了。思路如下：首先向左深入，直到节点没有左子节点了。沿途把每个节点的右子节点和节点本身入栈（顺序不能反）。然后从这个没有左子节点的节点开始，向上访问每一个没有右子节点的节点，直到到达第一有右子节点的节点。这时先访问这个节点，再转到它的右子树。
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
| void iterativeInorder(BSTNode* root) {
stack<BSTNode*> travStack;
BSTNode* p = root;
while (p != nullptr) {
while (p != nullptr) {
if (p->right != nullptr) {
travStack.push(p->right);
}
travStack.push(p);
p = p->left;
}
p = travStack.top();
travStack.pop();
while (!travStack.empty() && p->right == nullptr) {
visit(p);
p = travStack.top();
travStack.pop();
}
visit(p);
if (! travStack.empty()) {
p = travStack.top();
travStack.pop();
}
else {
p = nullptr;
}
}
}
|