Question

利用栈将二叉树递归算法转化为非递归算法

用C语言程序写，小弟不会写了，算法看不懂 急救

Answer 1

#define struct_sizes 20
#define adds 10

typedef struct bitnode//二叉树的定义
{
int data;//二叉树元素数据类型
struct bitnode *lchild,*rchild;//左右孩子
}*bitree;

typedef struct
//顺序栈的定义
{
bitree *base;//栈底指针
bitree *top;//栈顶指针
int stacksize;
}sqstack;

int initstack(sqstack &S)//新建一个空栈
{
S.base=(bitree *)malloc(struct_sizes*sizeof(bitree));
if(!S.base)return 0;
S.top = S.base;
S.stacksize = struct_sizes;
return 1;
}//initstack

int stackempty(sqstack S)
//判断栈是否为空
{
if(S.base==S.top)return 1;
else return 0;
}

int push(sqstack &S,bitree e)//进栈
{
if(S.top - S.base >= S.stacksize)//栈满重新分配空间
{
S.base = (bitree *)realloc(S.base,(S.stacksize + adds) * sizeof (bitree));
if(!S.base)return 0;
S.top = S.base + S.stacksize;
S.stacksize += adds;
}
*(S.top++)=e;
return 1;
}//push

int pop(sqstack &S,bitree &e)//出栈
{
if(S.top == S.base)return 0;
e = * --S.top;
return 1;
}//pop

int gettop(sqstack S,bitree &e)//取栈顶元素
{
if(S.top == S.base) return 0;
e = *(S.top - 1);
return 1;
}//gettop

int mid_travel(bitree T)//递归二叉树中序遍历
{
if(!T)return 0;
else
{
if(T->lchild)mid_travel(T->lchild);
printf(" %d",T->data);
if(T->rchild)mid_travel(T->rchild);
}
return 1;
}

int mid_norecursion(bitree T)
//中序遍历二叉树T的非递归算法，打印每个数据
{
sqstack S;
bitree p;
if(!T)return 0;
initstack(S);push(S,T);//根指针进栈
while(!stackempty(S))
{
while(gettop(S,p)&&p)push(S,p->lchild);//向左走到尽头
pop(S,p); //空指针退栈
if(!stackempty(S))//访问结点，向右一步
{
pop(S,p);printf(" %d",p->data);
push(S,p->rchild);
}
}
return 1;
}