Question

二叉树非递归后续遍历（链栈编写） 大侠帮忙~~ 找错

status st_PostOrderTraverse(BiNode* pTree)//后序非递归遍历
{ BiNode *p;
SNode *q,*Stop=NULL,*weizhi;
p=pTree;
while(p!=NULL||Stop!=NULL)
{ if(Stop!=NULL)
{
q=(SNode*) malloc(sizeof(SNode));
q->next=Stop;
q->elem=p;
Stop=q;

p=p->rChild;
if(p->lChild==NULL)
{
weizhi=Stop->next;
p=weizhi->elem->lChild;
} }
else
{
q=Stop;
Stop=Stop->next;
printf("%c",q->elem->Data);

}

Answer 1

typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; //有mark域的结点指针类型
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈
{
PMType a;
InitStack(S); //S的元素为PMType类型
Push (S,{T,0}); //根结点入栈
while(!StackEmpty(S))
{
Pop(S,a);
switch(a.mark)
{
case 0:
Push(S,{a.ptr,1}); //修改mark域
if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树
break;
case 1:
Push(S,{a.ptr,2}); //修改mark域
if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树
break;
case 2:
visit(a.ptr); //访问结点,返回
}
}//while
}//PostOrder_Stack
/*分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作. */