《二叉树前序、中序、后序三种遍历的非递归算法.doc》由会员分享，可在线阅读，更多相关《二叉树前序、中序、后序三种遍历的非递归算法.doc（7页珍藏版）》请在金锄头文库上搜索。
1、二叉树前序、中序、后序三种遍历的非递归算法二叉树前序、中序、后序三种遍历的非递归算法.txt35温馨是大自然的一抹色彩，独具慧眼的匠师才能把它表现得尽善尽美；温馨是乐谱上的一个跳动音符，感情细腻的歌唱者才能把它表达得至真至纯一。教科书标准算法1.先序遍历非递归算法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; if (!Sta
2、ckEmpty(s) /通过下一次循环中的内嵌while实现右子树遍历 p=pop(s); p=p-rchild; /endif /endwhile 2.中序遍历非递归算法void InOrderUnrec(Bitree *t) Stack s; StackInit(s); Bitree *p=t; while (p!=NULL | !StackEmpty(s) while (p!=NULL) /遍历左子树 push(s,p); p=p-lchild; if (!StackEmpty(s) p=pop(s); visite(p-data); /访问根结点 p=p-rchild; /通过下一次循
3、环实现右子树遍历 /endif /endwhile3.后序遍历非递归算法typedef enumL,R tagtype;typedef struct Bitree ptr; tagtype tag;stacknode;typedef struct stacknode Elemmaxsize; int top;SqStack;void PostOrderUnrec(Bitree t) SqStack s; stacknode x; StackInit(s); p=t; do while (p!=null) /遍历左子树 x.ptr = p; x.tag = L; /标记为左子树 push(s,x
4、); p=p-lchild; while (!StackEmpty(s) & s.Elems.top.tag=R) x = pop(s); p = x.ptr; visite(p-data); /tag为R，表示右子树访问完毕，故访问根结点 if (!StackEmpty(s) s.Elems.top.tag =R; /遍历右子树 p=s.Elems.top.ptr-rchild; while (!StackEmpty(s);/PostOrderUnrec 二。前序最简洁算法void PreOrderUnrec(Bitree *t) Bitree *p; Stack s; s.push(t);
5、 while (!s.IsEmpty() s.pop(p); visit(p-data); if (p-rchild != NULL) s.push(p-rchild); if (p-lchild != NULL) s.push(p-lchild); 三。后序算法之二void 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!=NULL & pre!=root-right) root=root-right; else root=pre=s.top(); visit(root); s.pop(); root=NULL; 一个比较容易理解的后序遍历:void PostOrder(Bitree *t) TreeNode *node = NULL,*last = NULL; Stack s; s,Init(); s.push(t); while(!s.IsEmpty() node = s.pop(); if(last = node-left | last = node-right)/左右子树已经访问完了，该访问根节点了 visit(node); last = node; else if(node-left | node-right) /左右子树未访问，当前节点入栈，左右节点入栈 s.push(node); if(node-right) s.push(node-right); if(node-left) s.push(node-left); else /当前节点为叶节点，访问 visit(node); last = node;
