二叉树的非递归遍历出错

linbin0182 发布于 2013/04/15 12:28
阅读 96
收藏 1
#include<stdio.h>
#include<stdlib.h>

typedef struct BTre{

int data;

struct BTree *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct {
BiTree top,base;
int length;
}stack;//栈的结构定义
void CreatBinaryTree(BiTree &T)
{//构造一个二叉树(递归定义)
int ch;//以0表示空树
printf("输入结点:");                                                
scanf("%d",&ch);
if(ch==0) T=NULL;//约定值为零的结点为空
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T) exit(1);
T->data=ch;
CreatBinaryTree(T->lchild);//递归
CreatBinaryTree(T->rchild);
}
}
void VistTree(BiTree &T)
{//输出结点
if(T!=NULL)
printf("%d ",T->data);
}
void InitStack(stack &s)
{//初始化一个栈
s.base=(BiTree)malloc((4)*sizeof(BiTNode));
if(!s.base)
exit(1);
s.top=s.base;
s.length=0;
printf("InitStack Successfully!\n");
}
int StackEmpty(stack &s)
{//判断栈是否为空
if(s.length==0||s.base==NULL)
return 0;
else
return  1;
}
void PushStack(stack &s,BiTree &e)//注意参数类型
{//入栈操作
//栈中依次存放的是二叉树中各结点,而且不打乱各结点之间的连接关系
if(s.length>=4)
s.base=(BiTree)realloc(s.base,(4+4)*sizeof(BiTNode));
if(!s.base)
exit(1);
s.top=e;
s.top++;
s.length++;
}
void PopStack(stack &s,BiTree &e)//注意参数类型
{//出栈操作
if(StackEmpty(s))
{
s.top--;
e=s.top;
s.length--;
}
}
void MiddleTree(BiTree &T,stack &S)
{//中序遍历二叉树非递归实现
    BiTree p;
InitStack(S);p=T;
while(p!=NULL||StackEmpty(S))
{
if(p!=NULL)
{
PushStack(S,p);
p=p->lchild;
}
else
{
PopStack(S,p);
VistTree(p);
p=p->rchild;
}
}
}
int main(void)
{
BiTree T;
stack S;
CreatBinaryTree(T);
MiddleTree(T,S);
return 0;

}

为啥编译时没错,就是结果有错

加载中
返回顶部
顶部