帮帮忙，非递归算法先序建立二叉链表，问题出在哪里呢？
#define STACK_INIT_SIZE 100//测试值：abc@@de@g@@f@@@#define STACKINCREMENT 10
#include <stdio.h>
#include <stdlib.h>
typedef char TElemType;
//////////////////////////////////////////////栈定义
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;//
}BiTNode,*BiTree;
typedef struct
{
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
/////////////////////////////////////////////栈的基本操作
void initialStack(SqStack *s)
{
s->base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree));
if(!s->base) exit(0);
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *s,BiTNode *e)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(BiTree *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(BiTree));
if(!s->base) exit(0);
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*(s->top)++=e;
}
void Pop(SqStack *s,BiTree *e)//////////////////
{
if(s->top==s->base) exit(0);
*e=*--(s->top);//
}
int GetTop(SqStack *s,BiTree *e)///////////////////
{
if(s->top==s->base) return(0);
*e=*(s->top-1);//
return(1);
}
int StackEmpty(SqStack *s)
{
if(s->base==s->top)
return(1);
else
return(0);
}
void ClearStack(SqStack *s)
{
s->top=s->base;
s->stacksize=0;
}
void DestoryStack(SqStack *s)
{
free(s->base);
s->stacksize=0;
}
BiTree CreatBiTree()//非递归算法先序建立二叉链表
{
TElemType ch;
BiTree T,p;
SqStack S;
initialStack(&S);
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=ch;
T->lchild=T->rchild=NULL;
Push(&S,T);
}
while(!StackEmpty(&S))
{
scanf("%c",&ch);
if(ch!=' ')//生成左儿子，直到左儿子为空时退出循环
{
p=(BiTree)malloc(sizeof(BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
T->lchild=p;
T=p;
Push(&S,T);
scanf("%c",&ch);
}
else
Pop(&S,&T);//弹出最后一个左儿子(栈顶元素)
T->lchild=NULL;
scanf("%c",&ch);
if(ch==' ')//右儿子为空的情况
{
while((ch==' ')&&(!StackEmpty(&S)))//弹出栈顶元素，逆向返回，直到右儿子不为空
{
T->rchild=NULL;
Pop(&S,&T);//弹出根结点，进入右子树
scanf("%c",&ch);
}
p=(BiTree)malloc(sizeof(BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
T->rchild=p;//右儿子的根结点p的父亲为T
T=p;
Push(&S,T);
}
else//右儿子不为空的情况
{
p=(BiTree)malloc(sizeof(BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
T->rchild=p;//右儿子的根结点p的父亲为T
T=p;
Push(&S,T);
}
}
return T;
}
void Visit(TElemType e)//对数据元素进行操作的Visit函数
{
printf("%c",e);
}
void PreOrderTraverse(BiTree T)//先序遍历
{
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
/////////////////////////////////
void main()
{
BiTree t;
printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
printf("<参考数据:abc@@de@g@@f@@@，则用空格键表示@，输完后再输入一个回车键.>\n");
t=CreatBiTree();
printf("[先序遍历]:\n");
PreOrderTraverse(t);
printf("\n");
}
程序代码：
