《二叉树前序中序后序三种遍历的非递归算法.docx》由会员分享，可在线阅读，更多相关《二叉树前序中序后序三种遍历的非递归算法.docx（12页珍藏版）》请在三一文库上搜索。
1、二叉树前序、中序、后序三种遍 历的非递归算法o ? i ? e e e X ?1.? e Do e a ? ? ?p Y16 ? void PreOrderUnrec(Bitree *t) Stack s;StackInit(s);Bitree *p=t;while (p!=NULL | !StackEmpty(s)while (p!=NULL) /visite(p-data);push(s,p);p=p-lchild;eauX6X6e-if/ i(!StackEmpty(s). 1y?6 ? ?-? - ?Dp ? u ?while e ? 60X6”二up=pop(s);p=p-rchil
2、d;/endif/endwhile2.?DDo 6 a ? ? ?p Y16 ? void I nOrderUnrec(Bitree *t)Stack s;StackInit(s);Bitree *p=t;while (p!=NULL | !StackEmpty(s)eauX6X6e-while (p!=NULL) / push(s,p);p=p-lchild;if (!StackEmpty(s)(P=pop(s);visite(p-data); /-? e ? u ? a ip=p-rchild;/1y?6 ? ?-?-6?66*66&(1/endif/endwhile3.o otypeDo
3、 e a ? - ?p Y16 ? ef enumL,R tagtype;typedef structBitree ptr;tagtype tag;stacknode;typedef structstacknode Elemmaxsize; int top;JSqStack;void PostOrderUnrec(Bitree t)(SqStack s;stacknode x;Stacklnit(s);p=t;do(while (p! =null) /eAux6xOE-r(x.ptr = p;x. tag = L; /eMQIax6xOE-r push(s,x);p=p-lchild;)&wh
4、ile(!StackEmpty(s) s Elems.top .tag=R)X = pop(s);p = x.ptr;visite(p-data);/tagIaR-iiEOOxOE -A工E工6士工1E - AIE,uapa )if (StackEmpty(s)(s .Elems . top .tag =R; /eAu6dxOE4-p=s.Elems.top.ptr-rchild;while (!StackEmpty(s);/PostOrderUnreci QDdxidaEavoid PreOrderUnrec(Bitree *t)(Bitree *p;Stack s;s.push(t);wh
5、ile (! s.IsEmpty()(s.pop(p)； visit(p-data);if (p-rchild != NULL) s.push(p-rchild);if (p-lchild != NULL) s.push(p-lchild);e y?oo D)o ?-?tvoid BT_PostOrderNoRec(pTreeT root) (stack s;pTreeT pre=NULL;while (NULL != root) | !s.empty() (if (NULL != root)(s.push(root);root = root-left; else root = s.top()
6、;&if(root-right!=NULLpre!=root-right) ( root=root-right; ) else ( root=pre=s.top(); visit(root); s.pop(); root=NULL; ) ) ) o ? e ?e Yro X a i ?a ?o o Do e a uvoid PostOrder(Bitree *t) (TreeNode *node = NULL,*last = NULL;Stack s;s,Init();s.push(t);while(!s.IsEmpty()node = s.pop(); f(lastnode-leftnode-right)/ XoooXoe-o ?u ?u p ?G ?(visit(node);last = node;| last?- - ?e i e? ?else if(node-left | node-right)/ XoooXoe- ?-？e?p?(iN?6 ?X(? s.push(node);if(node-right)s.push(node-right);if(node-left)s.push(node-left);else /N ? ?U 以？a6 ?U 以？? ?e(visit(node);last = node;)