在coolshell上看了看了二叉树迭代器算法的文章，想到先将二叉树的多种遍历算法一一总结一次，s顺便让自己更加熟练。 二叉树的遍历最为熟悉的也是最容易理解的便是递归方式，简单易懂，然而递归效率不高，需要一个函数递归调用的函数栈，简单的非递归方式使用stack来模拟递归的方式实现，这样每个节点需要进栈和出栈一次,并且需要使用到O(N)的空间，还有另外一种更加神奇的方式，使用Morris算法来遍历。
递归的方式很简单，直接看代码。 假设二叉树的定义如下:
typedef struct tree{
int value;
struct tree* left;
struct tree* right;
}BinaryTree;
递归的中序遍历如下：
void inorder(BinaryTree *tree){
if(tree == NULL)
return;
if(tree->left != NULL)
inorder(tree->left);
cout << setw(4) << tree->value;
if(tree->right != NULL)
inorder(tree->right);
}
使用Stack来模拟函数递归调用的栈，下面的代码是先序遍历的Stack实现。
void stackPreOrderV1(BinaryTree *tree){
if(tree == NULL)
return;
std::stack<BinaryTree*> s;
while(tree != NULL || !s.empty()){
if(tree != NULL){
cout << tree->value << " ";
s.push(tree);
tree = tree->left;
}else{
tree = s.top();
s.pop();
tree = tree->right;
}
}
}
void stackPreOrderV2(BinaryTree *tree){
if(tree == NULL)
return;
std::stack<BinaryTree *> s;
s.push(tree);
while(!s.empty()){
while((tree = s.top()) != NULL){
cout << tree->value << " ";
s.push(tree->left);
}
s.pop();
if(!s.empty()){
tree = s.top();
s.pop();
tree = tree->right;
}
}
}
上面给出了前序遍历的两个非递归版本，本质上是一样的,两个之间的区别在于是否把空指针压入栈，所以第二个版本中间多了一次将空指针pop出栈的操作。基本的思路是将节点压入栈，然后将其左节点压入栈，依次往复直到叶子节点，然后弹出栈，可以访问其右节点。
由于前序和中序只是打印的语句放在不同的地方，故中序在此省略。
后序遍历是其中最复杂的，因为在访问跟节点前，不仅需要左子树全都访问完，还必须保证右子树也要全都访问完成，所以判断情况要复杂于前序遍历和中序遍历。很显然的思路是增加对节点的访问标记，标记节点是否被访问完了。还有一种更加巧妙的方法，因为我们首先访问的是左子树，然后是右子树，最后才是根节点，若节点是叶子则可以访问，若节点的左右子树都被访问完，则节点可以访问，对于前面一种情况我们很好判断，对于后一种情况，我们可以引入一个指针，标记上一个被访问的节点，如果上一个被访问的节点是当前节点的子节点，则表明左右子树都被访问完了。
void stackPostOrder(BinaryTree *tree){
if(tree == NULL)
return;
BinaryTree *pre = NULL;
std::stack<BinaryTree *> s;
s.push(tree);
while(!s.empty()){
tree = s.top();
if((tree->left == NULL && tree->right == NULL) ||
(pre != NULL && (pre == tree->left || pre == tree->right))){
cout << tree->value << " ";
s.pop();
pre = tree;
}else{
if(tree->right != NULL)
s.push(tree->right);
if(tree->left != NULL)
s.push(tree->left);
}
}
}
注意其中将左右子树添加到栈中的顺序，因为我们要先访问左子树，故需要将左子树放在栈顶，所以后入栈。
前面提到的非递归遍历使用了O(N)的栈空间，空间效率不高，还有一种更加神奇的遍历方式，利用叶子节点空着的两个指针，因为我们在遍历到叶子节点之后需要再找到下一个节点访问，那么就可以利用叶子节点空着的指针指到下一个要访问的节点，这么遇到另一个问题，如何将叶子节点的两个指针还原了。我们脑中模拟这个过程，假定为中序遍历，三个节点的二叉树，根节点A，字节点B，C。首先从A出发，查找到B节点，B的右子树为空，可以将其指到下一个要访问的节点A，下次从A出发的时候，又找到B了，B的右子树已经连接到A，就可以发现，B是一个叶子节点，就消除右子树。我们可以从下面的代码中感受这段话。
void morrisInOrder(BinaryTree *tree){
if(tree == NULL)
return;
BinaryTree *tmp = NULL;
while(tree != NULL){
if(tree->left == NULL){
cout << tree->value << " ";
tree = tree->right;
}else{
tmp = tree->left;
while(tmp->right != NULL && tmp->right != tree){
tmp = tmp->right;
}
if(tmp->right == NULL){
tmp->right = tree;
tree = tree->left;
}else{
cout << tree->value << " ";
tmp->right = NULL;
tree = tree->right;
}
}
}
cout << endl;
}
观察这个Morris中序遍历，对每一个节点，如果其左子树为空，那么就访问这个节点，如果左子树不为空，就寻找左儿子的最右节点，将他们连接起来，下一次再回到此节点时，查找其左儿子的最右节点就会回到它本身，故知道这有个叶节点需要将其右子树置空。
void morrisPreOrder(BinaryTree *tree){
if(tree == NULL)
return;
BinaryTree *tmp = NULL;
while(tree != NULL){
if(tree->left == NULL){
cout << tree->value << " ";
tree = tree->right;
}else{
tmp = tree->left;
while(tmp->right != NULL && tmp->right != tree){
tmp = tmp->right;
}
if(tmp->right == NULL){
tmp->right = tree;
cout << tree->value << " ";
tree = tree->left;
}else{
tmp->right = NULL;
tree = tree->right;
}
}
}
cout << endl;
}
Morris前序遍历和中序遍历代码几乎一模一样，除了打印语句至于不同的地方。
Morris后序遍历同样比较复杂，总是需要将左右子树均访问完成之后才能在访问根节点，我们发现前面使用morris遍历时，在第一次出现tmp->right == tree时，此时tree节点的左儿子节点是没有左子树的，可能存在右子树，并且可以看到一个单向链表，那么我们可以将tree的左子树遍历一遍，由于是后续遍历，所以需要从tree节点左儿子的最右节点往上遍历，所以可以使用一个stack来辅助当然这就违背了Morris只使用O(1)空间的原则,那么可以将左子树看成单向链表反转，然后遍历，再反转回来，使用stack则方便很多了。现在问题来了，我们无法访问tree节点了，因为tree节点还能有右子树，最棒的方式是构造一个伪根节点pesudo node,其左子树为根节点，右子树为空。那么现在所有的节点都成为了一个节点的左儿子，我们就可以通过刚才的方法统一遍历了。
void morrisPostOrder(BinaryTree *tree){
if(tree == NULL)
return;
BinaryTree *tmp = NULL;
BinaryTree *pesudo = new BinaryTree(0,tree,NULL);
tree = pesudo;
std::stack<BinaryTree *> s;
while(tree != NULL){
if(tree->left == NULL)
tree = tree->right;
else{
tmp = tree->left;
while(tmp->right != NULL && tmp->right != tree)
tmp = tmp->right;
if(tmp->right == NULL){
tmp->right = tree;
tree = tree->left;
}else{
if(tree->left == tmp){
cout << tmp->value <<" ";
}else{
BinaryTree *node = tree->left;
while(node != tree){
s.push(node);
node = node->right;
}
while(!s.empty()){
cout << s.top()->value<< " ";
s.pop();
}
}
tmp->right = NULL;
tree = tree->right;
}
}
}
cout << endl;
delete pesudo;
}
二叉树存在三种不同的遍历方式，每种都各有其特点：
查看这三种方式的实现代码，发现不管哪种方式，前序和中序都是差不多的，唯有后续复杂很多，需要仔细观察，建立更多的判断条件。 CoolShell上提到了如何使用迭代器来遍历二叉树，思想和非递归遍历一样，使用stack来存储节点，方便调用next()来获取下一个需要访问的节点，对树的遍历方式没有改变，只是提供了统一的接口来对多种不同的数据结构进行同样的操作。