二叉树先序、中序、后序遍历非递归算法

《二叉树先序、中序、后序遍历非递归算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.先序遍历非递归算法voidPreOrderUnrec(Bitree*t){   Stacks;StackInit(s);Bitree*p=t;while(p!=NULL

2、

3、!StackEmpty(s)){     while(p!=NULL)      //遍历左子树     {      visite(p->data);      push(s,p);      p=p->lchild;        }                if(!StackEmpty(s))    //通过下一次循环中的内嵌while实现右子树遍历     { 

4、     p=pop(s);      p=p->rchild;          }//endif        }//endwhile}2.中序遍历非递归算法voidInOrderUnrec(Bitree*t){   Stacks;StackInit(s);Bitree*p=t;   while(p!=NULL

5、

6、!StackEmpty(s)){     while(p!=NULL)      //遍历左子树     {      push(s,p);      p=p->lchild;     }                if(!St

7、ackEmpty(s))     {      p=pop(s);      visite(p->data);     //访问根结点      p=p->rchild;      //通过下一次循环实现右子树遍历     }//endif}//endwhile}3.后序遍历非递归算法typedefenum{L,R}tagtype;typedefstruct{Bitreeptr;tagtypetag;}stacknode;typedefstruct{stacknodeElem[maxsize];inttop;}SqStack;voidPostOr

8、derUnrec(Bitreet){SqStacks;stacknodex;StackInit(s);p=t;do{     while(p!=null)     //遍历左子树     {      x.ptr=p;      x.tag=L;    //标记为左子树      push(s,x);      p=p->lchild;     }     while(!StackEmpty(s)&&s.Elem[s.top].tag==R)       {      x=pop(s);      p=x.ptr;      visite(p->

9、data);//tag为R，表示右子树访问完毕，故访问根结点       }          if(!StackEmpty(s))     {      s.Elem[s.top].tag=R;   //遍历右子树      p=s.Elem[s.top].ptr->rchild;          }}while(!StackEmpty(s));}//PostOrderUnrec