二叉樹三種遍歷算法代碼__共3頁

1、二叉樹三種遍歷算法的源碼二叉樹三種遍歷算法的源碼背誦版本文給出二叉樹先序、中序、后序三種遍歷的非遞歸算法，此三個算法可視為標(biāo)準(zhǔn)算法，直接用于考研答題。1.先序遍歷非遞歸算法#define maxsize 100typedef structBitree Elemmaxsize;int top;SqStack;void PreOrderUnrec(Bitree t)SqStack s;StackInit(s);p=t;while (p!=null | !StackEmpty(s)while (p!=null) /遍歷左子樹visite(p->data);push(s,p);p=p->l

2、child;/endwhileif (!StackEmpty(s) /通過下一次循環(huán)中的內(nèi)嵌while 實(shí)現(xiàn)右子樹遍歷p=pop(s);p=p->rchild;/endif/endwhile/PreOrderUnrec2.中序遍歷非遞歸算法#define maxsize 100typedef structBitree Elemmaxsize;int top;SqStack;void InOrderUnrec(Bitree t)SqStack s;StackInit(s);p=t;while (p!=null | !StackEmpty(s)while (p!=null) /遍歷左子樹pu

3、sh(s,p);p=p->lchild;/endwhileif (!StackEmpty(s)p=pop(s);visite(p->data); / 訪問根結(jié)點(diǎn)p=p->rchild; / 通過下一次循環(huán)實(shí)現(xiàn)右子樹遍歷/endif/endwhile/InOrderUnrec3.后序遍歷非遞歸算法#define maxsize 100typedef enumL,R tagtype;typedef structBitree ptr;tagtype tag;stacknode;typedef structstacknode Elemmaxsize;int top;SqStack;v

4、oid PostOrderUnrec(Bitree t)SqStack s;stacknode x;StackInit(s);p=t;dowhile (p!=null) /遍歷左子樹x.ptr = p;x.tag = L; / 標(biāo)記為左子樹push(s,x);p=p->lchild;while (!StackEmpty(s) && s.Elems.top.tag=R)x = pop(s);p = x.ptr;visite(p->data); /tag 為 R，表示右子樹訪問完畢，故訪問根結(jié)點(diǎn)if (!StackEmpty(s)s.Elems.top.tag =R; / 遍歷右子樹p=s