二叉树的定义及基本操作
一、实验目的、意义
（1）熟悉二叉链表表示的二叉树结构及其递归遍历。
（2）掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径。
（3）根据具体问题的需要，能够设计出相关算法。
二、实验内容及要求
说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
具体要求：
（1）定义二叉树的链式存储结构；
（2）建立一颗二叉链表表示的二叉树；
（3）对其进行前序，中序，后序输出。
三、实验所涉及的知识点
C语言算法、循环算法、二叉树结构及其递归遍历、二叉链表的建立，二叉树的前序，中序，后序输出。
四、实验结果及分析
（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。）
五、总结与体会
（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。）
(调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。)
调试时，由于对所学知识点概念模糊，二叉树结构及其递归遍历不熟悉，试验出现了很大的困难，课上未完成实验，并且还出现一些语法上的错误，经过反复排错、查阅资料，花了大量时间才解决问题。
六、程序清单(包含注释)
#include
#include
typedef char DataType;
typedef struct BitNode
{
DataType data;
struct BitNode *lchild,*rchild;
}*BitTree;
void BinTreeInit(BitTree &BT)//初始化二叉树，即把树根指针置空
{
BT=(BitTree)malloc(sizeof(BitNode));
BT->data=NULL;
cout
}
int BinTreeCreat(BitTree &BT)//按先序次序建立一个二叉树
{
char ch;
cin>>ch;
if(ch=='#') BT=NULL;
else
{
if(!(BT=(BitTree)malloc(sizeof(BitNode))))
exit(0);
BT->data=ch;
BinTreeCreat(BT->lchild);
BinTreeCreat(BT->rchild);
}
return 0;
// 按先序序列建立一个二叉树已经完成!
}
void BinTreeEmpty(BitTree &BT)//检查二叉树是否为空
{
if(BT->data==NULL)
cout
else
cout
}
void BinTraverse1(BitTree &BT)//先序序列遍历二叉树
{
if(BT!=NULL)
{
coutdata;
BinTraverse1(BT->lchild);
BinTraverse1(BT->rchild);
}
}
void BinTraverse2(BitTree &BT)//中序序列遍历二叉树
{
if(BT!=NULL)
{
BinTraverse2(BT->lchild);
coutdata;
BinTraverse2(BT->rchild);
}
}
void BinTraverse3(BitTree &BT)//后序序列遍历二叉树
{
if(BT!=NULL)
{
BinTraverse3(BT->lchild);
BinTraverse3(BT->rchild);
coutdata;
}
}
int BinTreeDepth(BitTree BT)//求二叉树的深度
{
int depthval;
if(BT)
{
int depthLeft=BinTreeDepth(BT->lchild);
int depthRight=BinTreeDepth(BT->rchild);
depthval=1+
(depthLeft>depthRight?depthLeft:depthRight);
}
else depthval=0;
return depthval;
}
int BinTreeCount(BitTree BT)//求二叉树中所有结点数
{
int node;
if(BT)
{
int lchild=BinTreeCount(BT->lchild);
int rchild=BinTreeCount(BT->rchild);
node=lchild+rchild+1;
}
else
node=0;
return node;
}
void main()
{
int i;
BitTree BT;
cout
cout
for(;;)
{
cout
cin>>i;
if(i==1)
BinTreeInit(BT);
else if(i==2)
{
cout
BinTreeCreat(BT);
}
else if(i==3)
BinTreeEmpty(BT);
else if(i==4)
{ BinTraverse1(BT);
cout
BinTraverse2(BT);
cout
BinTraverse3(BT);
cout
}
else if(i==5)
cout
else if(i==6)
cout
else
return ;
}
}
二叉树的定义及基本操作
一、实验目的、意义
（1）熟悉二叉链表表示的二叉树结构及其递归遍历。
（2）掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径。
（3）根据具体问题的需要，能够设计出相关算法。
二、实验内容及要求
说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
具体要求：
（1）定义二叉树的链式存储结构；
（2）建立一颗二叉链表表示的二叉树；
（3）对其进行前序，中序，后序输出。
三、实验所涉及的知识点
C语言算法、循环算法、二叉树结构及其递归遍历、二叉链表的建立，二叉树的前序，中序，后序输出。
四、实验结果及分析
（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。）
五、总结与体会
（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。）
(调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。)
调试时，由于对所学知识点概念模糊，二叉树结构及其递归遍历不熟悉，试验出现了很大的困难，课上未完成实验，并且还出现一些语法上的错误，经过反复排错、查阅资料，花了大量时间才解决问题。
六、程序清单(包含注释)
#include
#include
typedef char DataType;
typedef struct BitNode
{
DataType data;
struct BitNode *lchild,*rchild;
}*BitTree;
void BinTreeInit(BitTree &BT)//初始化二叉树，即把树根指针置空
{
BT=(BitTree)malloc(sizeof(BitNode));
BT->data=NULL;
cout
}
int BinTreeCreat(BitTree &BT)//按先序次序建立一个二叉树
{
char ch;
cin>>ch;
if(ch=='#') BT=NULL;
else
{
if(!(BT=(BitTree)malloc(sizeof(BitNode))))
exit(0);
BT->data=ch;
BinTreeCreat(BT->lchild);
BinTreeCreat(BT->rchild);
}
return 0;
// 按先序序列建立一个二叉树已经完成!
}
void BinTreeEmpty(BitTree &BT)//检查二叉树是否为空
{
if(BT->data==NULL)
cout
else
cout
}
void BinTraverse1(BitTree &BT)//先序序列遍历二叉树
{
if(BT!=NULL)
{
coutdata;
BinTraverse1(BT->lchild);
BinTraverse1(BT->rchild);
}
}
void BinTraverse2(BitTree &BT)//中序序列遍历二叉树
{
if(BT!=NULL)
{
BinTraverse2(BT->lchild);
coutdata;
BinTraverse2(BT->rchild);
}
}
void BinTraverse3(BitTree &BT)//后序序列遍历二叉树
{
if(BT!=NULL)
{
BinTraverse3(BT->lchild);
BinTraverse3(BT->rchild);
coutdata;
}
}
int BinTreeDepth(BitTree BT)//求二叉树的深度
{
int depthval;
if(BT)
{
int depthLeft=BinTreeDepth(BT->lchild);
int depthRight=BinTreeDepth(BT->rchild);
depthval=1+
(depthLeft>depthRight?depthLeft:depthRight);
}
else depthval=0;
return depthval;
}
int BinTreeCount(BitTree BT)//求二叉树中所有结点数
{
int node;
if(BT)
{
int lchild=BinTreeCount(BT->lchild);
int rchild=BinTreeCount(BT->rchild);
node=lchild+rchild+1;
}
else
node=0;
return node;
}
void main()
{
int i;
BitTree BT;
cout
cout
for(;;)
{
cout
cin>>i;
if(i==1)
BinTreeInit(BT);
else if(i==2)
{
cout
BinTreeCreat(BT);
}
else if(i==3)
BinTreeEmpty(BT);
else if(i==4)
{ BinTraverse1(BT);
cout
BinTraverse2(BT);
cout
BinTraverse3(BT);
cout
}
else if(i==5)
cout
else if(i==6)
cout
else
return ;
}
}