实验 三 二叉树的基本操作实现及其应用.doc

软件114班李大宝201100834416

第PAGE

数

据

结

构

实

验

报

告

（三）

姓名:李大宝

学院：计算机学院

班级：软件114班

实验三二叉树的基本操作实现及其应用

一、实验目的

1．熟悉二叉树结点的结构和对二叉树的基本操作。

2．掌握对二叉树每一种操作的具体实现。

3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

4.会用二叉树解决简单的实际问题。

二、实验内容

题目一设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。

1按先序次序建立一个二叉树，

2按（A:先序B:中序C:后序D:层序）遍历输出二叉树的所有结点

以上比做，以下选做

3求二叉树中所有结点数

4求二叉树的深度

****************************************************************

/*定义DataType为char类型*/

typedefcharDataType;

/*二叉树的结点类型*/

typedefstructBitNode

{DataTypedata;

structBitNode*lchild,*rchild;

}*BitTree;

相关函数声明：

1、/*初始化二叉树，即把树根指针置空*/

voidBinTreeInit(BitTreeBT)

2、/*按先序次序建立一个二叉树*/

voidBinTreeCreat(BitTreeBT)

3、/*检查二叉树是否为空*/

intBinTreeEmpty(BitTreeBT)（包括按、中序、后序、按层次）

4、/*按任先序遍历次序输出二叉树中的所有结点*/

voidperordertraverse(BitTreeT)

5、/*按任中序遍历次序输出二叉树中的所有结点*/

voidinordertraverse(BitTreeT)

6、/*按任后序遍历次序输出二叉树中的所有结点*/

voidenordertraverse(BitTreeT)

7、/*按任层序遍历次序输出二叉树中的所有结点*/

voidcengordertraverse(BitTreeT)

8、/*求二叉树的深度*/

intBinTreeDepth(BitTreeBT)

9、/*求二叉树中所有结点数*/

intBinTreeCount(BitTreeBT)

相关函数的实现：

1、/*初始化二叉树，即把树根指针置空*/

voidBinTreeInit(BitTreeBT)

{if(!(BT=(BitNode*)malloc(sizeof(BitNode))))

exit(0);//为树根指针申请空间，申请不到退出。

BT=NULL;}//把树根指针置空,完成初始化。

2、/*按先序次序建立一个二叉树*/

voidBinTreeCreat(BitTreeBT)//递归调用建立二叉树

{charch;ch=getchar();//输入字符。

if(ch==)BT=NULL;//空格代表为空

else{//递归建立二叉树。

if(!(BT=(BitNode*)malloc(sizeof(BitNode))))

exit(0);//为节点申请空间，申请不到退出。

BT-data=ch;//为节点赋值

BinTreeCreat(BT-lchild);//先建立左二叉树。

BinTreeCreat(BT-rchild);}//再建立右二叉树。

}

3、/*检查二叉树是否为空*/

intBinTreeEmpty(BitTreeBT)

{if(BT)return0;//根节点不空，二叉树就不空。返回0

return1;}//否则二叉树就为空，则返回1

4、/*按任先序遍历次序输出二叉树中的所有结点*/

按递归的方法实现的遍历。（中序，后序遍历