二叉树的非递归遍历2013年3月20日

二叉树的递归遍历算法非常漂亮和易读，但是非递归算法就没那么容易懂了，尤其是后序遍历的非递归算法。

一. 前序遍历

 1 void PreOrderTraverse(Node *root)
 2 {
 3     stack<Node *> ns;
 4     Node *n=root;
 5     while(n!=NULL || !ns.empty())
 6     {
 7         if(n!=NULL) 
 8         {
 9             print(n); 
10             ns.push(n);
11             n=n->pLeft;
12         }
13         else
14         {
15             ns.pop(n); 
16             n=n->pRight;
17         }
18     }
19 }

二.中序遍历

 1 void InOrderTraverse(Node *root)
 2 {
 3     stack<Node *> ns;
 4     Node *n=root;
 5     while(n!=NULL || !ns.empty())
 6     {
 7         if(T!=NULL) 
 8         {
 9             ns.push(n); 
10             n=n->pLeft;
11         }
12         else
13         {
14             ns.pop(n); 
15             print(n);
16             n=n->pRight;
17         }
18     }
19 }

三. 后序遍历

后序遍历就比较麻烦了，有两种算法。后序遍历的关键是保证儿子结点先于父结点打印。

第一种:还是跟先序和中序一样，一路往左走，找到最左的一个结点A。A不可能再有左儿子了，但可能有右儿子。而这是A第一次为stack的top结点，但是这时还不能打印它。将A的右儿子入栈后，再次执行，待到A第二次成为top时，这说明A右儿子结点已经处理了，因为A结点在栈中的位置必然是在右儿子之下的。用一个变量来表示这个二次的关系。代码如下:

 1 void PostOrderTraverse(Node *root)
 2 {
 3     stack<Node *> ns;
 4     Node *n=root;
 5     while(n!=NULL || !ns.empty())
 6     {
 7         if(n!=NULL)        
 8         {
 9             n->IsFirst=true;//The first time to be the top of ns stack.
10             ns.push(n);
11             n=n->pLeft;
12         }
13         else
14         {
15             if(!ns.empty()) 
16             {
17                 ns.pop(n); 
18                 if(n->IsFirst==true)//The first time to be the top of ns stack.Don't print.
19                 {
20                     n->IsFirst=false;
21                     ns.push(n); 
22                     n=n->pRight;
23                 }
24                 else  //The second time.Print it.
25                     print(n); 
26             }
27         }
28     }
29 }

第二种思路:后序遍历的顺序是:左儿子->右儿子->父结点。那么，入栈的顺序就应该倒过来，即:父结点->右儿子->左儿子。当前top位置的结点如果没有左右儿子结点或者是左右儿子结点都已经访问过了，那么就可以打印出来；如果不是这样，就将右儿子和左儿子依次入栈。注意，这里需要保存当前top位置之前的那次访问的结点，而且root结点需要在while循环之前入栈。代码如下:

 1 void PostOrderTraverse2(Node *root)
 2 {
 3     stack<Node *> ns;
 4     Node *n=root;
 5     Node *previous=NULL;//It is NULL at first.
 6     ns.push(n);
 7     while(n!=NULL || !ns.empty())
 8     {
 9         n=ns.top(); 
10         if( (n->pLeft==NULL && n->pRight==NULL) || (previous==n->pLeft || previous==n->pRight))
11         {
12             print(n); 
13             ns.pop();
14             previous=n;
15         }
16         else
17         {
18             if(n->pRight!=NULL)
19                 ns.push(n->pRight);   
20             if(n->pLeft!=NULL)
21                 ns.push(n->pLeft);   
22         }
23     }
24 }

参考资料：http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

如果你觉得我的文章对你有帮助，请推荐一下，非常感谢!