#include
#include
#include
#define OK 1
#define OVERFLOW -1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define MAX_TREE_SIZE 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree SElemType;
struct stack
{
SElemType *base;
SElemType *top;
int stacksize;
};
typedef struct stack SqStack;
void main()
{
status InitBiTree(BiTree );
BiTree CreateBiTree(BiTree );
status PreOrder(BiTree );
status InOrder(BiTree T);
status PostOrder(BiTree T);
void Push(SqStack* ,SElemType );
status Pop(SqStack* ,SElemType* );
status InitStack(SqStack* );
status IsEmpty(SqStack* );
status InOrderTraversal(BiTree );
status PreOrderTtaversal(BiTree );
BiTree BT;BT=NULL;
InitBiTree(BT);
printf("请输入树的元素,空元素用#:");
BT=CreateBiTree(BT);
printf("\n递归先序输出:");
PreOrder(BT);
printf("\n递归中序输出:");
InOrder(BT);
printf("\n递归后序输出:");
PostOrder(BT);
printf("\n非递归先序输出:");
PreOrderTtaversal(BT);
printf("\n非递归中序输出:");
InOrderTraversal(BT);
}
status InitBiTree(BiTree T)
{
T=NULL;
return(OK);
}
BiTree CreateBiTree(BiTree T)
{
TElemType ch;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)exit(OVERFLOW);
T->data=ch;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return(T);
}
status PreOrder(BiTree T)
{
if(T)
{
if(!(T->data))
return(ERROR);
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
return(OK);
}
}
status InOrder(BiTree T)
{
if(T)
{
if(!(T->data))return(ERROR);
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
return(OK);
}
}
status PostOrder(BiTree T)
{
if(T)
{
if(!(T->data))return(ERROR);
InOrder(T->lchild);
InOrder(T->rchild);
printf("%c",T->data);
return(OK);
}
}
void Push(SqStack* S,SElemType e)
{
if((S->top-S->base)>S->stacksize)
{
S->base=(SElemType*)realloc(S->base,sizeof(SElemType)*(STACK_INIT_SIZE+STACKINCREMENT));
if(!S->base) exit(ERROR);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
(S->top)++;
}
status Pop(SqStack* S,SElemType* e)
{
if(S->base==S->top) return(ERROR);
e=(--S->top);
return OK;
}
status InitStack(SqStack* S)
{
S->base=(SElemType*)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
if(!S->base) exit(OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
status InOrderTraversal(BiTree BT)
{
BiTree T=BT;
SqStack S;
InitStack(&S);
while(T||!IsEmpty(&S))
{
while(T)
{
Push(&S,T);
T=T->lchild;
}
if(!IsEmpty(&S))
{
Pop(&S,&T);
printf("%d",T->data);
T=T->rchild;
}
}
return(OK);
}
status IsEmpty(SqStack* S)
{
if(S->base==S->top) return(1);
else return(0);
}
status PreOrderTraversal(BiTree BT)
{
BiTree T=BT;
SqStack S;
InitStack(&S);
while(T||!IsEmpty(&S))
{
while(T)
{
Push(&S,T);
printf("%d",T->data);
T=T->lchild;
}
if(!IsEmpty(&S))
{
Pop(&S,&T);
T=T->rchild;
}
}
return(OK);
}
报错:
Linking...
exe32.obj : error LNK2001: unresolved external symbol _PreOrderTtaversal
Debug/exe32.exe : fatal error LNK1120: 1 unresolved externals
执行 link.exe 时出错.