请看一下我写的这段二叉树后续遍历非递归算法问题出在哪
- C/C++ code
void PostOrderTraverse(BiTree T){ if(T){ Stack s; InitStack(&s); BiTree p; BiTree q=NULL; Push(&s,T); while(!StackEmpty(s)){ while(Gettop(s,&p)&&p){ Push(&s,p->lchild); } Pop(&s,&p); if(!StackEmpty(s)){ Gettop(s,&p); if(p->rchild==NULL||p->rchild==q){ Pop(&s,&p); printf("%c",p->data); q=p; p=NULL; Push(&s,p); } else p=p->rchild; } } }}
[解决办法]
- C/C++ code
//3.后序遍历非递归算法#define maxsize 100typedef enum{L,R} tagtype;typedef struct { Bitree ptr; tagtype tag;}stacknode;typedef struct{ stacknode Elem[maxsize]; int top;}SqStack;
[解决办法]
- C/C++ code
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); p=p->lchild; }
[解决办法]
- C/C++ code
while (!StackEmpty(s) && s.Elem[s.top].tag==R) { x = pop(s); p = x.ptr; visite(p->data); } if (!StackEmpty(s)) { s.Elem[s.top].tag =R; p=s.Elem[s.top].ptr->rchild; } }while (!StackEmpty(s));}//PostOrderUnrec