- 受到《算法导论》10.4习题的启发，决定整理一下遍历二叉树的算法，分别用递归和非递归形式实现前序、中序、后序深度优先遍历，以及非递归方式实现层次优先遍历。总结一下从递归向非递归转化的一些规律。
- 深度优先遍历
递归实现的前序遍历 ：preorder_tree_walk_recursive
递归实现的中序遍历 ：inorder_tree_walk_recursive
递归实现的后序遍历 ：postorder_tree_walk_recursive
非递归，借助一个栈实现的前序遍历 ：preorder_tree_walk_by_stack 和 preorder_tree_walk_by_stack1（简化版）
非递归，借助一个栈实现的中序遍历 ：inorder_tree_walk_by_stack
非递归，借助一个栈实现的后序遍历 ：postorder_tree_walk_by_stack
非递归，仅使用固定长度存储空间的前序遍历 ： preorder_tree_walk
非递归，仅使用固定长度存储空间的中序遍历 ： inorder_tree_walk
非递归，仅使用固定长度存储空间的后序遍历 ： postorder_tree_walk
- 层次优先遍历
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
using Index = int;
struct Node
{
int key;
Index parent;
Index left;
Index right;
};
Index root;
Node nodes[11];
//首先我们构建一棵二叉树，借用习题10.4-1的数据，每个节点通过数组下标进行寻址。
void BuildBinaryTree()
{
//data from 10.4-1, it looks like
/*
18
12 10
7 4 2 21
5
*/
root = 6;
nodes[1] = Node{12,6,7,3};
nodes[3] = Node{4,1,10,-1};
nodes[4] = Node{10,6,5,9};
nodes[5] = Node{2,4,-1,-1};
nodes[6] = Node{18,-1,1,4};
nodes[7] = Node{7,1,-1,-1};
nodes[9] = Node{21,4,-1,-1};
nodes[10] = Node{5,3,-1,-1};
}
//先实现三种顺序的递归算法，我们可以看到，前序、中序、后序的唯一区别就是`cout << node.key`步骤的位置。
//O(n)-time recursive procedure
void inorder_tree_walk_recursive(Index index)
{
if(index == -1) //step 1
return;
Node& node = nodes[index];
inorder_tree_walk_recursive(node.left);//step 2
cout << node.key << "\t"; //step 3
inorder_tree_walk_recursive(node.right);//step 4
}
void preorder_tree_walk_recursive(Index index)
{
if(index == -1)
return;
Node& node = nodes[index];
cout << node.key << "\t";
preorder_tree_walk_recursive(node.left);
preorder_tree_walk_recursive(node.right);
}
void postorder_tree_walk_recursive(Index index)
{
if(index == -1)
return;
Node& node = nodes[index];
postorder_tree_walk_recursive(node.left);
postorder_tree_walk_recursive(node.right);
cout << node.key << "\t";
}
//再来看，借助栈实现的非递归算法
//O(n)-time nonrecursive procedure,Use a stack as an auxiliary data structure
/*
递归算法包括“自顶向下的递归调用”和“自底向上的触底反弹”，要想借助一个栈将遍历二叉树算法的递归形式改写为非递归的形式，一种可行的做法是模仿递归过程，“入栈”操作对应着“递归调用”过程，将等待被处理的节点按次序记录下来；“出栈”操作对应着“触底反弹”过程，完成对当前节点的处理工作后清除该节点的记录。
例如中序遍历二叉树，要实现非递归算法，
思考，每个节点需要被访问几次才能完成自己的工作（包括给出左右孩子和打印自身），
答案是两次，第一次找左孩子，第二次打印自身给出右孩子。
我们应该在某节点被第一次访问时将其入栈以备后续访问，在最后一次访问时将其出栈，整个过程就应该是：
根入栈，进入循环，访问栈顶元素，非空则进行第一次访问，将其左孩子入栈，空则将空的先出栈，对当前栈顶做第二次访问：打印栈顶，找到其右孩子，然后出栈，将刚刚拿到的右孩子入栈。
*/
void inorder_tree_walk_by_stack()
{
stack<Index> stk;
stk.push(root);
while(true)
{
//if语句做“递归”or“返回”的判断，对应`inorder_tree_walk_recursive`算法中的"step 1"
if(stk.top() != -1)
{
//这是当前节点第一次被访问时，让可能存在的左孩子入栈，优先于自己被处理。对应"step 2"
stk.push(nodes[stk.top()].left);
}
else
{
//这是当前节点第二次被访问时，此时左子树已经遍历结束，应该打印自身并出栈，将自己的右孩子入栈，相当于将以当前节点为根的树退化为当前节点的右子树，等待处理，对应"step 3 4"
stk.pop();
if(stk.empty())
break;
auto node_index = stk.top();
stk.pop();
cout << nodes[node_index].key << "\t";
stk.push(nodes[node_index].right);
}
}
}
//这个前序遍历和inorder_tree_walk_by_stack的唯一区别还是`cout << nodes[node_index].key `执行步骤的位置。
void preorder_tree_walk_by_stack()
{
stack<Index> stk;
stk.push(root);
while(true)
{
if(stk.top() != -1)
{
cout << nodes[stk.top()].key << "\t";
stk.push(nodes[stk.top()].left);
}
else
{
stk.pop();
if(stk.empty())
break;
auto node_index = stk.top();
stk.pop();
stk.push(nodes[node_index].right);
}
}
}
//其实前序遍历算法还可以简化，因为每个节点可以在第一次被访问时就完成所有任务，包括打印自身以及将两个孩子入栈。所以其实可以简化成对每个节点只访问一次。
void preorder_tree_walk_by_stack1()
{
stack<Index> stk;
stk.push(root);
while(!stk.empty())
{
auto node_index = stk.top();
stk.pop();
if(-1 == node_index)
continue;
cout << nodes[node_index].key << "\t";
stk.push(nodes[node_index].right);
stk.push(nodes[node_index].left);
}
}
//后序遍历稍有不同，因为每个非空节点需要被访问3次，第一次刚入栈，找左孩子，第二次刚从左孩子返回，找右孩子，第三次刚从右孩子返回，打印自身并出栈。与前序和中序比较，相同点是过程中都需要维护栈顶元素，用空指针表示下一步应该“触底反弹”，用非空指针表示下一步应该“递归调用”。不同的是，还需额外维护一个枚举量which_child,用来标识当前栈顶第一个元素是栈顶第二个元素的哪个孩子。
void postorder_tree_walk_by_stack()
{
stack<Index> stk;
stk.push(root);
enum {LEFT, RIGHT}which_child;
while(true)
{
if(-1 == stk.top())
{
stk.pop();
if(LEFT == which_child) //第二次访问，记录右孩子
{
stk.push(nodes[stk.top()].right);
which_child = RIGHT;
}
else //第三次访问，打印自身，出栈
{
auto node_index = stk.top();
cout << nodes[node_index].key << "\t" << flush;
stk.pop();
if(stk.empty())
break;
if(nodes[stk.top()].left == node_index)
which_child = LEFT;
else
which_child = RIGHT;
stk.push(-1);
}
}
else //第一次访问，记录左孩子
{
stk.push(nodes[stk.top()].left);
which_child = LEFT;
}
}
}
//最后看一下，使用固定长度的额外存储空间实现的非递归算法
//O(n)-time nonrecursive procedure,use no more than constant extra space outside of the tree itself and do not modify the tree
/*
除了二叉树本身外，还需要三个固定长度的变量来完成遍历，分别是
current_node表示当前走到哪个节点，值-1表示已“触底”，下一步应该“反弹”。
last_node表示当前节点的父亲节点，作用是即使当前节点为空，也能顺利找到其父亲节点
which_chid表示当前空节点是其父亲节点的哪个孩子。
整个流程和postorder_tree_walk_by_stack类似，每个节点都需要访问三次，不同的是父亲节点不再保留在栈中，而是通过当前节点获取。
*/
void inorder_tree_walk()
{
Index current_node = root, last_node;
enum{LEFT, RIGHT} which_child;
while(true)
{
if(-1 == current_node)
{
if(LEFT == which_child)//第二次访问
{
//handle last_node
cout << nodes[last_node].key << "\t";
current_node = nodes[last_node].right;
which_child = RIGHT;
}
else //第三次访问
{
//handle last_node
if(last_node == root)
break;
current_node = last_node;
last_node = nodes[current_node].parent;
if(current_node == nodes[last_node].left)
which_child = LEFT;
else
which_child = RIGHT;
current_node = -1;
}
}
else //第一次访问
{
//handle current_node
last_node = current_node;
current_node = nodes[current_node].left;
which_child = LEFT;
}
}
}
//下面的前序、后序遍历和 inorder_tree_walk()的唯一区别就是 打印自身那一步的执行位置。
void preorder_tree_walk()
{
Index current_node = root, last_node;
enum{LEFT, RIGHT} which_child;
while(true)
{
if(-1 == current_node)
{
if(LEFT == which_child)
{
current_node = nodes[last_node].right;
which_child = RIGHT;
}
else
{
if(last_node == root)
break;
current_node = last_node;
last_node = nodes[current_node].parent;
if(current_node == nodes[last_node].left)
which_child = LEFT;
else
which_child = RIGHT;
current_node = -1;
}
}
else
{
cout << nodes[current_node].key << "\t";
last_node = current_node;
current_node = nodes[current_node].left;
which_child = LEFT;
}
}
}
void postorder_tree_walk()
{
Index current_node = root, last_node;
enum{LEFT, RIGHT} which_child;
while(true)
{
if(-1 == current_node)
{
if(LEFT == which_child)
{
current_node = nodes[last_node].right;
which_child = RIGHT;
}
else
{
cout << nodes[last_node].key << "\t";
if(last_node == root)
break;
current_node = last_node;
last_node = nodes[current_node].parent;
if(current_node == nodes[last_node].left)
which_child = LEFT;
else
which_child = RIGHT;
current_node = -1;
}
}
else
{
last_node = current_node;
current_node = nodes[current_node].left;
which_child = LEFT;
}
}
}
//层次优先遍历，借助一个队列实现，每个节点被访问一次，需要完成的任务是打印自身并出队，孩子入队等待处理。
//这样一来，可以保证，当第n行的所有节点出队后，第n+1行的所有节点已全部入队。
//O(n)-time nonrecursive procedure, use a queue
void level_tree_walk()
{
std::queue<Index> q;
q.push(root);
while(!q.empty())
{
auto node_index = q.front();
q.pop();
if(-1 == node_index)
continue;
cout << nodes[node_index].key << "\t";
q.push(nodes[node_index].left);
q.push(nodes[node_index].right);
}
}
void TestWalker()
{
BuildBinaryTree();
inorder_tree_walk_recursive(root);
cout << endl;
inorder_tree_walk_by_stack();
cout << endl;
inorder_tree_walk();
cout << endl;
preorder_tree_walk_recursive(root);
cout << endl;
preorder_tree_walk_by_stack();
cout << endl;
preorder_tree_walk_by_stack1();
cout << endl;
preorder_tree_walk();
cout << endl;
postorder_tree_walk_recursive(root);
cout << endl;
postorder_tree_walk_by_stack();
cout << endl;
postorder_tree_walk();
cout << endl;
level_tree_walk();
}
//output:
/*
7 12 5 4 18 2 10 21
7 12 5 4 18 2 10 21
7 12 5 4 18 2 10 21
18 12 7 4 5 10 2 21
18 12 7 4 5 10 2 21
18 12 7 4 5 10 2 21
18 12 7 4 5 10 2 21
7 5 4 12 2 21 10 18
7 5 4 12 2 21 10 18
7 5 4 12 2 21 10 18
18 12 10 7 4 2 21 5
*/