二叉树后序遍历

Question

我写的后序遍历有问题。。。无法输出。
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
int tag;
} BiTNode,*BiTree;//树类型
typedef struct SqStack
{
BiTNode *base;
BiTNode *top;
int stacksize;
} SqStack;//栈类型
void InitStack(SqStack *S)//创建
{
S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *S,BiTNode e)//进栈
{
if(S->top-S->base>=S->stacksize)
{
S->base=(BiTNode*)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
S->top++;
}
BiTNode Pop(SqStack *S)//出栈
{
S->top --;
return *S->top;

}
int StackEmpty(SqStack *S)//判断栈是否非空
{
if(S->top == S->base )
return 1;
else
return 0;
}
BiTree CreateBiTree()//创建树（先序递归）
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=p;T->tag=0;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
void PreOrder(BiTree T)//先序
{
SqStack S;
BiTree p=T;
InitStack(&S);
if(p)
Push(&S,*p);
while(!StackEmpty(&S))
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
if(p->rchild)
Push(&S,*p->rchild);
if(p->lchild)
Push(&S,*p->lchild);
}
}
void InOrder(BiTree T)//中序
{
SqStack S;
BiTree p=T;
InitStack(&S);
while(p||!StackEmpty(&S))
{
if(p)
{
Push(&S,*p);
p=p->lchild;
}
else
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
p=p->rchild;
}
}
}

int GetTop(SqStack S,BiTree p)
{
if(!StackEmpty(&S))
{p=S.top-1;return 1;}
else return 0;
}

void PostOrder(BiTree T)
{
SqStack S;
BiTree p=T;
InitStack(&S);
Push(&S,*p);
while(!StackEmpty(&S))
{
while(GetTop(S,p) && p!=NULL &&!p->tag)
Push(&S,*p->lchild);
if(p && p->tag)
printf("%c",p->data);
Pop(&S);
GetTop(S,p);
if(!StackEmpty(&S) && p!=NULL &&(!p->tag))
{
p->tag=1;
Push(&S,*p->rchild);
GetTop(S,p);
}
}
}

void main()
{
BiTree Ta;
printf("请创建树");
Ta=CreateBiTree();
printf("先序遍历:");
printf("\n");
PreOrder(Ta);
printf("\n");
printf("中序遍历:");
printf("\n");
InOrder(Ta);
printf("\n");
printf("后序遍历:");
printf("\n");
PostOrder(Ta);
printf("\n");
}
麻烦高手帮我看看，后序遍历哪里错了，怎么能和程序搭配好，谢谢!

Answer 1

问题在于
int GetTop(SqStack S,BiTree p)
{
if(!StackEmpty(&S))
{p=S.top-1;return 1;}
else return 0;
}
你传递指针进来，是没办法改变指针的指向的。
它仅仅在这个子函数里改变了，但退出这个子函数的时候，没有改变地址。所以你的函数一直在while循环里，当然没有输出结果。