二叉树的非递归遍历—–2013年3月20日
二叉树的递归遍历算法非常漂亮和易读，香港虚拟主机，但是非递归算法就没那么容易懂了，尤其是后序遍历的非递归算法。
一. 前序遍历
1 void PreOrderTraverse(Node *root) 2 { 3stack<Node *> ns; 4Node *n=root; 5while(n!=NULL || !ns.empty()) 6 { 7if(n!=NULL) 8 { 9 print(n); 10 ns.push(n);11n=n->pLeft;12 }{15 ns.pop(n); 16n=n->pRight;17 }18 }19 }
二.中序遍历
1 void InOrderTraverse(Node *root) 2 { 3stack<Node *> ns; 4Node *n=root; 5while(n!=NULL || !ns.empty()) 6 { 7if(T!=NULL) 8 { 9 ns.push(n); 10n=n->pLeft;11 }{14 ns.pop(n); 15 print(n);16n=n->pRight;17 }18 }19 }
三. 后序遍历
后序遍历就比较麻烦了，有两种算法。后序遍历的关键是保证儿子结点先于父结点打印。
第一种:还是跟先序和中序一样，一路往左走，找到最左的一个结点A。A不可能再有左儿子了，但可能有右儿子。而这是A第一次为stack的top结点，但是这时还不能打印它。将A的右儿子入栈后，再次执行，美国服务器，待到A第二次成为top时，这说明A右儿子结点已经处理了，因为A结点在栈中的位置必然是在右儿子之下的。用一个变量来表示这个二次的关系。代码如下:
1 void PostOrderTraverse(Node *root) 2 { 3stack<Node *> ns; 4Node *n=root; 5while(n!=NULL || !ns.empty()) 6 { 7if(n!=NULL) 8 {ns.push(n);11n=n->pLeft;12 }{15if(!ns.empty()) 16 {17 ns.pop(n); {20n->IsFirst=false;21 ns.push(n); 22n=n->pRight;23 }print(n); 26 }27 }28 }29 }
第二种思路:后序遍历的顺序是:左儿子->右儿子->父结点。那么，入栈的顺序就应该倒过来，即:父结点->右儿子->左儿子。当前top位置的结点如果没有左右儿子结点或者是左右儿子结点都已经访问过了，那么就可以打印出来；如果不是这样，就将右儿子和左儿子依次入栈。注意，这里需要保存当前top位置之前的那次访问的结点，而且root结点需要在while循环之前入栈。代码如下:
1 void PostOrderTraverse2(Node *root) 2 { 3stack<Node *> ns; 4Node *n=root; ns.push(n); 7while(n!=NULL || !ns.empty()) 8 { 9n=ns.top(); 10if( (n->pLeft==NULL && n->pRight==NULL) || (previous==n->pLeft || previous==n->pRight))11 {12 print(n); 13 ns.pop();14previous=n;15 }{18if(n->pRight!=NULL)19ns.push(n->pRight);20if(n->pLeft!=NULL)21ns.push(n->pLeft);22 }23 }24 }
参考资料：
如果你觉得我的文章对你有帮助，请推荐一下，非常感谢!
posted on
，美国服务器他们比任何人都分毫较量，又比任何人都口是心非。他们比任何人都依赖彼此，
