二叉树先序、中序、后序三种遍历的非递归算法,此三个算法可视为标准

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

1、#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidPreOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null

2、

3、!StackEmpty(s)){while(p!=null)//±éÀú×ó×ÓÊ÷{visite(p->data);push(s,p);p=p->lchild;}//endwhileif(!StackEmpty(s))//ͨ¹ıÏÂÒ»´ÎÑ»·ÖеÄÄÚǶwhileʵÏÖÓÒ×ÓÊ÷±éÀú{

4、p=pop(s);p=p->rchild;}//endif}//endwhile}//PreOrderUnrec2.ÖĞĞò±éÀú·Çµİ¹éËã·¨#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidInOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null

5、

6、!StackEmpty(s)){while(p!=null)//±éÀú×ó×ÓÊ÷{push(s,p);p=p->lchild;}//endwhileif

7、(!StackEmpty(s)){p=pop(s);visite(p->data);//·ÃÎʸù½áµãp=p->rchild;//ͨ¹ıÏÂÒ»´ÎÑ»·ÊµÏÖÓÒ×ÓÊ÷±éÀú}//endif}//endwhile}//InOrderUnrec3.ºóĞò±éÀú·Çµİ¹éËã·¨#definemaxsize100typedefenum{L,R}tagtype;typedefstruct{Bitreeptr;tagtypetag;}stacknode;typedefstruct{stacknodeElem[maxsize];inttop;}SqStack

8、;voidPostOrderUnrec(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->data);//tagΪR£¬±íʾÓÒ×ÓÊ÷·ÃÎÊÍê±Ï£¬¹Ê·ÃÎʸù½áµã}if(!StackEmpty(s)){

9、s.Elem[s.top].tag=R;//±éÀúÓÒ×ÓÊ÷p=s.Elem[s.top].ptr->rchild;}}while(!StackEmpty(s));}//PostOrderUnrec