真心求教,刚刚自己写了个二叉树中序遍历非递归的算法,但总是显示栈满!!!现在实在是不知道错在哪了?
#include<stdio.h>#include<stdlib.h>
#define max_size 100
#define overflow -1
typedef char datatype;
typedef struct node
{
struct node *lchild,*rchild;
datatype data;
}ptree;
typedef struct
{
int top,base;
struct node *data[max_size];
}stack1;
stack1 s;
ptree *create()
{
int front=1,rear=0;
ptree *root=NULL,*s,*queue[max_size];
char ch;
ch=getchar();
while(ch!='#')
{
s=NULL;
if(ch!='@')
{
if(!(s=(ptree *)malloc(sizeof(ptree))))
exit(0);
s->lchild=NULL;
s->rchild=NULL;
s->data=ch;
}
rear++;
queue[rear]=s;
if(rear==1) root=s;
else
if(s&&queue[front])
if(rear%2==0) queue[front]->lchild=s;
if(rear%2==1)
queue[front++]->lchild=s;
ch=getchar();
}
fflush(stdin);
return root;
}
void initstack() //初始化栈:
{
s.top=s.base=0;
}
void Enstack(ptree *k) //进栈函数;
{
if((s.top-s.base)>=max_size) //判断是否栈已满:
{
printf("栈已满!\n");
exit(0);
}
s.data[s.top++]=k; //未满就将此节点的地址入栈;
}
ptree *Destack()
{
if(s.top<=0)
{
printf("栈空!\n");
exit(0);
}
s.top--;
printf("%c ",s.data[s.top+1]);
return s.data[s.top+1];
}
void inorder(ptree *k) //非递归遍历,
{
if(k==NULL) //假如根结点为空,则为一棵空树:
{
printf("树为空!\n");
exit(0);
}
initstack(); //栈初始化;
while(1)
{
if(k) //当结点不为空时,进行以下操作;
{
if(k->lchild) //假如左孩子存在,
{
Enstack(k); //将父节点入栈
k=k->lchild;
}
else if(k->rchild)
{
Enstack(k); //将此指针指向的地址入栈;
k=k->rchild;
}
else
{
printf("%c ",k->data);
k=Destack()->rchild; //出栈并返回一个地址;
}
}
}
}
int main()
{
ptree *k;
printf("请输入元素创建二叉树(@表示虚节点,#表示结束符):\n");
k=create();
printf("中序遍历结果为:\n");
inorder(k);
free(k);
return 0;
}
inorder()函数中栈初始化时,top为0;当进栈时每次top就变为了100