这是我写的二叉树先序遍历非递归算法,但是我的输出并不完整,为什么呢?难道是因为我申请的空间不够吗?
#include
#include
#define STACK_INIT_SIZE 20//栈初始空间大小
#define INCREAMENT 10//栈空间大小的增量
#define false 0
#define true 1
#define OVERFLOW 0
typedef struct BT{
char data;
struct BT *lchild,*rchild;
}BT,*BN;
typedef struct SqStack{
BT *base;
BT *top;
int stacksize;
}ST; // 栈
void Create(BN *t) // 创建二叉树
{
char c;
scanf("%c",&c);
if(c=='#')
{
*t=NULL;
}
else{
*t=(BN)malloc(sizeof(BT));
(*t)->data=c;
Create(&(*t)->lchild);
Create(&(*t)->rchild);
}
}
void Initstack(ST *s) // 构造空栈
{
s->base=(BT*)malloc(STACK_INIT_SIZE*sizeof(BT));
if(!s->base) exit(OVERFLOW);
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}
int StackEmpty(ST s)
{
if(s.base==s.top)
return true;
else
return false;
}
void push(ST *s,BT e)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(BT*)realloc(s->base,(STACK_INIT_SIZE+INCREAMENT)*sizeof(BT));
s->top=s->base+s->stacksize;
s->stacksize+=INCREAMENT;
}
*s->top=e; // 把指针p放进栈
s->top++;
}
void pop(ST *s,BT *e)
{
if(s->base!=s->top)// 不为空
*e=*--s->top ;
//或s->top--; *e=*s-top;
}
void PreOrder(BN t)
{
ST s; //栈
Initstack(&s);
BN p=t;
while(p||!StackEmpty(s))
{
if(p)
{
printf("%c",p->data); // 即printf
push(&s,*p); // 当前节点入栈
p=p->lchild;
}
else{
pop(&s,p);
p=p->rchild;
}
}
}
int main()
{
BN T=NULL;
printf("请输入数据:\n");
Create(&T); // 构造一棵空树
printf("二叉树创建成功!\n");
printf("先序非递归算法遍历结果为:\n");
PreOrder(T);
return 0;
}