• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

数据结构后序遍历二叉树非递归算法

开发技术 开发技术 5小时前 2次浏览

代码如下:

 1 void postorder(BiTree T)
 2 {
 3     InitStack(S);          //初始化栈
 4     p=T;
 5     r=null;      //辅助指针,指向最近访问过的结点
 6     while(p||!IsEmpty(s))
 7     {
 8         if(p)
 9         {
10             push(S,p);
11             p=p->lchid;        //走到最左边
12         }
13         else         //向右查找
14         {
15             GetTop(S,p);     //获取栈顶元素,不出栈
16             if(p->rchild!=null&&p->rchild!=r)         //如果右孩子非空并且没有访问过
17                 p=p->rchild;     //转向右孩子
18             else         //否则弹出节点并访问
19             {
20                 pop(S,p);
21                 visit(p->data);
22                 r=p;         //记录最近访问过的结点
23                 p=null;      //结点访问完,重置p指针
24             }
25         }
26     }
27 }

 


程序员灯塔
转载请注明原文链接:数据结构后序遍历二叉树非递归算法
喜欢 (0)