实验7 二叉树的应用
（1）实验目的
通过该实验，使学生理解二叉树的链式存储，掌握二叉树的几种遍历算法，并通过该实验使学生理解递归的含义，掌握C语言编写递归函数的方法和注意事项。
（2）实验内容
实现教材中算法6.4描述的二叉树创建算法，在此基础上实现二叉树的先序、后序递归遍历算法、两种非递归中序遍历、层序遍历、求二叉树的深度。注意：在非递归算法中用到栈和队列时，不要调用系统的栈和队列，需要自己实现栈和队列的操作。
（3）参考界面
（4）验收/测试用例
? 创建
输入 ：ABCKaTeX parse error: Can't use function '$' in math mode at position 3: DE$?GF$$$ ($表示空格)
该输入对应的树如图所示
? 先序 屏幕输出 A B C D E G F
? 后序 屏幕输出 C G E F D B A
? 中序 屏幕输出 C B E G D F A
(两种中序非递归还需看源代码)
? 层序 屏幕输出 A B C D E F G
? 深度 屏幕显示 深度为5
? 另外自己画出一棵树，再测试一遍。
运行环境
Dev C++
主要源代码
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
#define OK 1
#define ERROR 0
#define MAX_TREE_SIZE 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char TElemType;
typedef bool Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild ,*rchild;
}BiTNode,*BiTree;
BiTree T;
typedef BiTree SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status PushStack(SqStack &S,SElemType p)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++ = p;
return OK;
}
Status PopStack(SqStack &S,SElemType &p)
{
if(S.top == S.base) return ERROR;
p=*--S.top;
return OK;
}
Status TopStack(SqStack &S,SElemType &p)
{
if(S.top==S.base)
return ERROR;
p=*(S.top-1);
return OK;
}
//1.创建二叉树
Status createBiTree(BiTree &T)
{
char ch;
cin>>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;
}
Status Print(TElemType e)
{
printf("%c ",e);
return OK;
}
//2.先序
Status lastT(BiTree &T,Status(* visit)(TElemType e))
{
if(T)
{
if(visit(T->data))
if(lastT(T->lchild,Print))
if(lastT(T->rchild,Print))
return OK;
return ERROR;
}
return OK;
}
//3.中序1
Status zhongT(BiTree &T,Status(* visit)(TElemType e))
{
SqStack S;
InitStack(S);
SElemType p;
PushStack(S,T);
while(S.top!=S.base)
{
while(TopStack(S,p) && p)
PushStack(S,p->lchild);
PopStack(S,p);
if(S.top!=S.base)
{
PopStack(S,p);
if(!visit(p->data))
return ERROR;
PushStack(S,p->rchild);
}
}
}
//4.中序2
Status zhongT2(BiTree T,Status(* visit)(TElemType e))
{
SqStack S;
InitStack(S);
SElemType p;
p=T;
while(p || S.top!=S.base)
{
if(p)
{
PushStack(S,p);
p=p->lchild;
}
else
{
PopStack(S,p);
if(!visit(p->data))
return ERROR;
p=p->rchild;
}
}
return OK;
}
//5.后序
Status postTree(BiTree &T,Status(* visit)(TElemType e))
{
if(T)
{
if(postTree(T->lchild,Print))
if(postTree(T->rchild,Print))
if(visit(T->data))
return OK;
return ERROR;
}
return OK;
}
//6.层序
Status cengTree(BiTree &T,Status(* visit)(TElemType e))
{
int i=0,j=0;
BiTree p[100];
if(T)
p[j++]=T;
while(i<j)
{
visit(p[i]->data);
if(p[i]->lchild)
p[j++]=p[i]->lchild;
if(p[i]->rchild)
p[j++]=p[i]->rchild;
i++;
}
}
int DeepTree(BiTree T)
{
int LD,RD;
if(T==NULL)
return 0;
else
{
LD=DeepTree(T->lchild);
RD=DeepTree(T->rchild);
return (LD>=RD?LD:RD)+1;
}
}
int main()
{
cout<<"********************************"<<endl;
cout<<"******* 1.创建二叉树 ******"<<endl;
cout<<"******* 2.先序遍历二叉树 ******"<<endl;
cout<<"******* 3.中序遍历二叉树1 ******"<<endl;
cout<<"******* 4.中序遍历二叉树2 ******"<<endl;
cout<<"******* 5.后序遍历二叉树 ******"<<endl;
cout<<"******* 6.层序遍历二叉树 ******"<<endl;
cout<<"******* 7.求二叉树的深度 ******"<<endl;
cout<<"******* 8.退出 ******"<<endl;
cout<<"********************************"<<endl;
int n;
do
{
cout<<"请输入选择：" ;
cin>>n;
switch(n)
{
case 1:
cout<<"请输入二叉树的元素来构建二叉树 ($表示空格) ：\n ";
createBiTree(T);
cout<<"创建成功!"<<endl;
break;
case 2:
cout<<"先序遍历：";
lastT(T,Print);
cout<<endl;
break;
case 3:
cout<<"中序遍历1：";
zhongT(T,Print);
cout<<endl;
break;
case 4:
cout<<"中序遍历2：";
zhongT2(T,Print);
cout<<endl;
break;
case 5:
cout<<"后序遍历：";
postTree(T,Print);
cout<<endl;
break;
case 6:
cout<<"层序遍历：";
cengTree(T,Print);
cout<<endl;
break;
case 7:
cout<<"该二叉树的深度是：";
cout<<DeepTree(T)<<endl;
break;
default :
cout<<"输入指令不存在"<<endl;
break;
}
}while(n!=8);
cout<<"程序已退出，欢迎下次使用"<<endl;
return 0;
}
