主题:[菜鸟求助]二叉树中序遍历问题
谁帮我改改这程序啊...
好多错误!
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct
{ int* base;
int* top;
int stacksize;
}SqStack; //定义栈
typedef struct BiTNode
{ char data;
struct BiTNode *lchild,*rchild; //左右孩子
}BiTNode,*BiTree; //定义二叉树
Status InitStack(SqStack &S)
{ //构造一个空栈
S.base=(BiTree*)malloc(STACK_INIT_SIZE * sizeof(BiTNode));
if(!S.base) exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack
Status Push(SqStack &S,BiTree e)
{ //插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)
{ //栈满,追加存储空间
S.base=(BiTree)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}//if
*S.top++=e;
return OK;
}//Push
Status Pop(SqStack &S,BiTree &e)
{ //若栈不空,则删除S的栈顶原定,用e返回其值,并返回OK;否则返回ERROR;
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}//Pop
Status GetTop(SqStack S,BiTree &e)
{ //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR;
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}//GetTop
Status StackEmpty(SqStack S)
{ //若栈为空,则返回TRUE,否则返回ERROR;
if(S.top==S.base) return OK;
else return ERROR;
}//StackEmpty
Status CreateBiTree(BiTree &T)
{ //按先序次序输入二叉树中的结点的值,空格表示空树
//构造二叉链表表示二叉树T.
char ch;
scanf("%c",&ch);
if(ch==' ') T=NULL;
else
{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch; //生成根结点
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}//CreateBiTree
Status InOrderTraverse(BiTree T)
{ //中序遍历二叉树的非递归算法
BiTree p;
SqStack S;
InitStack(S); p=T;
while(p||!StackEmpty(S))
{ if(p){ Push(S,p); p=p->lchild;}//根指针进栈,遍历左子树
else
{ //根指针退栈,访问根结点,遍历右子树
Pop(S,p); if(!p) return ERROR;
p=p->rchild;
}//else
}//while
return OK;
}//InOrderTraverse
/*Status Visit(char e)
{ char* p;
*p=e;
if(*p) printf("%c",*p);
else return ERROR;
return OK;
}*/
void main()
{ BiTree T;
CreateBiTree(T);
InOrderTraverse(T);
}
好多错误!
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct
{ int* base;
int* top;
int stacksize;
}SqStack; //定义栈
typedef struct BiTNode
{ char data;
struct BiTNode *lchild,*rchild; //左右孩子
}BiTNode,*BiTree; //定义二叉树
Status InitStack(SqStack &S)
{ //构造一个空栈
S.base=(BiTree*)malloc(STACK_INIT_SIZE * sizeof(BiTNode));
if(!S.base) exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack
Status Push(SqStack &S,BiTree e)
{ //插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)
{ //栈满,追加存储空间
S.base=(BiTree)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}//if
*S.top++=e;
return OK;
}//Push
Status Pop(SqStack &S,BiTree &e)
{ //若栈不空,则删除S的栈顶原定,用e返回其值,并返回OK;否则返回ERROR;
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}//Pop
Status GetTop(SqStack S,BiTree &e)
{ //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR;
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}//GetTop
Status StackEmpty(SqStack S)
{ //若栈为空,则返回TRUE,否则返回ERROR;
if(S.top==S.base) return OK;
else return ERROR;
}//StackEmpty
Status CreateBiTree(BiTree &T)
{ //按先序次序输入二叉树中的结点的值,空格表示空树
//构造二叉链表表示二叉树T.
char ch;
scanf("%c",&ch);
if(ch==' ') T=NULL;
else
{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch; //生成根结点
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}//CreateBiTree
Status InOrderTraverse(BiTree T)
{ //中序遍历二叉树的非递归算法
BiTree p;
SqStack S;
InitStack(S); p=T;
while(p||!StackEmpty(S))
{ if(p){ Push(S,p); p=p->lchild;}//根指针进栈,遍历左子树
else
{ //根指针退栈,访问根结点,遍历右子树
Pop(S,p); if(!p) return ERROR;
p=p->rchild;
}//else
}//while
return OK;
}//InOrderTraverse
/*Status Visit(char e)
{ char* p;
*p=e;
if(*p) printf("%c",*p);
else return ERROR;
return OK;
}*/
void main()
{ BiTree T;
CreateBiTree(T);
InOrderTraverse(T);
}