利用栈存储指向一个二叉树结点的指针,可不知为什么,在进行中序遍历时,进行调试时总卡在GetTop()函数这里,请大神帮我看看
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
typedef struct
{
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S)//创建一个栈
{
S.base=(BiTree *)malloc(sizeof(BiTree)*STACK_INIT_SIZE);
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,BiTree p)
{
if((S.top-S.base)>=S.stacksize)
{
S.base=(BiTree *)malloc((STACKINCREMENT+S.stacksize)*sizeof(BiTree));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=p;
return OK;
}
Status Pop(SqStack &S,BiTree &p)
{
if(S.base==S.top) return ERROR;
p=*--S.top;
return OK;
}
Status StackEmpty(SqStack &S)
{
if(S.top==S.base) return true;
//xprintf("%c",p->data);
else return false;
}
Status GetTop(SqStack S,BiTree &p)//得到栈顶元素,S是一个存放指
//向一个二叉树结点的指针的栈
{
BiTree q;
if(S.top==S.base) return ERROR;
q=*S.top;
q->data=3;
p=q;
//for(int i=0;i
//p=NULL;
printf("%c",p->data);
return OK;
}
Status Visit(ElemType ch)
{
putchar(ch);
return OK;
}
Status CreateBiTree(BiTree &T){ // 算法6.4
// 按先序次序输入二叉树中结点的值(一个字符),’#’字符表示空树,
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
T->data=ch;// 生成根结点
CreateBiTree(T->lchild);// 构造左子树
CreateBiTree(T->rchild);// 构造右子树
}
return OK;
} // CreateBiTree
Status PrintElement(ElemType e) { // 输出元素e的值
printf("%c", e );
return OK;
}// PrintElement
Status PreOrderTraverse(BiTree T, Status(*Visit)(ElemType)) {
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
}
else return OK;
} // PreOrderTraverse
Status InOrderTraverse( BiTree T, Status(*Visit)(ElemType) ){
SqStack S;
BiTree p;
InitStack(S);
Push(S,p);
//printf("%c",p->data);
while(!StackEmpty(S))
{
while(GetTop(S,p)&&p) Push(S,p->lchild);
Pop(S,p);
if(!StackEmpty(S))
{
Pop(S,p);
//printf("fdffdf");
if(!Visit(p->data)) return ERROR;
Push(S,p->rchild);
}
}
return OK;
} // InOrderTraverse
Status PostOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) {
// 后序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。
//补全代码,可用多个语句
if(T==NULL) return OK;
PostOrderTraverse(T->lchild,Visit);
PostOrderTraverse(T->rchild,Visit);
Visit(T->data);
return OK;
} // PostOrderTraverse
int main() //主函数
{
BiTree T;
CreateBiTree(T);
PreOrderTraverse(T,Visit);
printf("\n");
InOrderTraverse(T,Visit);
printf("\n");
PostOrderTraverse(T,Visit);
return 0;
//补充代码
}//main