后序非递归遍历时,每遇到一个结点,先把它推入栈中,让 Poplin=0。在遍历其左子树前,改结点的 PopTim=1,将其左孩子推入栈中。在遍历完左子树后,还不能访问该结点,必须继续遍历右子树,此时改 结点的 Poplin=2,并把其右孩子推入栈中。在遍历完右子树后,结点才退栈访问。 60161162626262 d 6 e 后序遍历的非递归算法1 void Postorder( BiTree T) i BiTree p=T,q=NULL; SqStack S; InitStack(S); Push(S, P); while( Stack Empty (s) i if(p & p!=q) Push(s, p): p=p->lchild; j else( Pop(S, p) if(StackEmpty()) if(p->rchild & p->rchild!=g) i Push(s, p); p=p->rchild; j else printf("%c",p->data); q=p i 后序遍历的非递归算法2 void postorder(BiTree T) i BiTree P=T, g, int flag, SqStack S: InitStack(s) while(P)i'(s top)=P; Stop++; P=P->lchild; while((S top!=S base)&& flag) i P=*(Stop-1); i printf("%c", P->data); S.top-, q=p; 3 else P=P->rchild; flag=0, 1 i while((S top!=S base)后序非递归遍历时，每遇到一个结点，先把它推入栈中，让 PopTim=0。在遍历其左子树前，改结点的 PopTim=1，将其左孩子推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，此时改 结点的 PopTim=2，并把其右孩子推入栈中。在遍历完右子树后，结点才退栈访问。 后序遍历的非递归算法 1 void Postorder(BiTree T) { BiTree p=T,q=NULL; SqStack S;InitStack(S); Push(S,p); while (!StackEmpty(S)) { if (p && p!=q) { Push(S,p); p=p->lchild; } else { Pop(S,p); if (!StackEmpty(S)) if (p->rchild && p->rchild!=q) { Push(S,p); p=p->rchild; } else {printf("%c",p->data); q=p;} } } } 后序遍历的非递归算法 2 void postorder(BiTree T) {BiTree P=T,q; int flag; SqStack S; InitStack(S); do { while (P){ *(S.top)=P;S.top++;P=P->lchild;} q=NULL; flag=1; while ((S.top!=S.base) && flag) { P=*(S.top-1); if (P->rchild == q) { printf("%c",P->data); S.top--; q=p;} else { P=P->rchild; flag=0;} } }while ((S.top!=S.base)); }