搜索
二叉树三种遍历算法的源码二叉树三种遍历算法的源码背诵版本文给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，直接用于考研答题。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