二叉树的三种遍历算法

1.先序遍历非递归算法#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidPreOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null||!StackEmpty(s)){while(p!=null)//遍历左子树{visite(p-data);push(s,p);p=p-lchild;}//endwhileif(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p-rchild;}//endif}//endwhile}//PreOrderUnrec2.中序遍历非递归算法#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidInOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null||!StackEmpty(s)){while(p!=null)//遍历左子树{push(s,p);p=p-lchild;}//endwhileif(!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;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)){s.Elem[s.top].tag=R;//遍历右子树p=s.Elem[s.top].ptr-rchild;}}while(!StackEmpty(s));}//PostOrderUnrec