浙江大学城市学院实验报告
课程名称
数据结构基础
实验项目名称
实验十
二叉树的基本操作
实验成绩
指导老师（签名 ）
日期
一.实验目的和要求
1、掌握二叉树的链式存储结构。
2、掌握在二叉链表上的二叉树操作的实现原理与方法。
3、进一步掌握递归算法的设计方法。
二.实验内容
1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。
二叉树二叉链表存储表示如下： struct BTreeNode {
ElemType data;
// 结点值域
BTreeNode *lchild , *rchild ; // 定义左右孩子指针 } ; 基本操作如下：
①void InitBTree( BTreeNode *&BT );
//初始化二叉树BT
②void CreateBTree( BTreeNode *&BT, char *a );
//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构
③int EmptyBTree( BTreeNode *BT);
//检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree( BTreeNode *BT); //求二叉树BT的深度并返回该值
⑤int FindBTree( BTreeNode *BT, ElemType x);
//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
⑥void PreOrder( BTreeNode *BT); //先序遍历二叉树BT ⑦void InOrder( BTreeNode *BT); //中序遍历二叉树BT ⑧void PostOrder( BTreeNode *BT);
//后序遍历发二叉树BT
⑨void PrintBTree( BTreeNode *BT );
//输出二叉树BT ⑩void ClearBTree( BTreeNode *&BT );
//清除二叉树BT
2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tree.h中，并在主函数文件test4_1.cpp中添加相应语句进行测试。 ①void LevelOrder( BTreeNode *BT ) //二叉树的层序遍历
②int Get_Sub_Depth( BTreeNode *T , ElemType x) //求二叉树中以元素值为x的结点为根的子树的深度
3、填写实验报告，实验报告文件取名为report10.doc。
4、上传实验报告文件report10.doc 、源程序文件test4_1.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。
三.函数的功能说明及算法思路
（包括每个函数的功能说明，及一些重要函数的算法实现思路） 函数：void InitBTree( BTreeNode *&BT ) 功能：初始化二叉树BT 思路：将BT指向NULL
函数：void CBTree(BTreeNode *&BT ) 功能：输入二叉树
思路：按先序次序输入二叉树中结点的值（一个字符）特殊字符 $ 表示空树
函数：void PBTree(BTreeNode *BT,int n) 功能：横向打印二叉树
思路：先递归输出右子树，按层次输出空格和“---”控制格式，再输出当前结点值，最后递归左子树
函数：void CreateBTree( BTreeNode *&BT, char *a ) 功能：根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构
思路：根据广义表表示的”(”,”)”和”,”等字符来构建二叉树，用栈S来存储根结点指针，用p来接收当前结点值数据并链接为栈顶元素的左/右孩子
函数：int EmptyBTree( BTreeNode *BT) 功能：检查二叉树BT是否为空，空返回1，否则返回0 思路：返回判断BT是否指向NULL
函数：int DepthBTree( BTreeNode *BT) 功能：求二叉树BT的深度并返回该值
思路：若一棵二叉树为空，则它的深度为0，否则它的深度等于左子树和右子树中的最大深度加1
函数：int FindBTree( BTreeNode *BT, ElemType x) 功能：查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
思路：类似于前序遍历，若空树则返回0。若根结点值等于查找值x则返回1，否则先调用函数本身查找左子树，还未找到则再查找右子树，所有操作完成均为找到，则返回0
函数：void PreOrder( BTreeNode *BT) 功能：先序遍历二叉树BT 思路：使用“根左右”的顺序遍历二叉树
函数：void InOrder( BTreeNode *BT) 功能：中序遍历二叉树BT 思路：使用“左根右”的顺序遍历二叉树
函数：void PostOrder( BTreeNode *BT)
功能：后序遍历二叉树BT 思路：使用“左右根”的顺序遍历二叉树
函数：void PrintBTree( BTreeNode *BT )
功能：输出二叉树BT 思路：按照广义表表示方法输出二叉树（与输入时相同）
函数：void ClearBTree( BTreeNode *&BT )
功能：清除二叉树BT 思路：按照先子树后根结点的顺序删除二叉树
函数（选作）：void LevelOrder( BTreeNode *BT ) 功能：二叉树的层序遍历
思路：初始化一个空队列，若二叉树为空，则空操作；否则，树根指针入队列。当队列非空时循环：出队首元素，并输出该元素（指针）所指结点的值；且若该结点存在左右孩子，则左右孩子指针进队列。输出结果就是层序遍历序列
函数（选作）：求二叉树中以元素值为x的结点为根的子树的深度 功能：int Get_Sub_Depth( BTreeNode *T , ElemType x) 思路：在FindBTree函数的基础上修改，将找到结点时的返回值改为调用DepthBTree求出以该结点为根结点的子树深度即可
四.实验结果与分析
（包括运行结果截图、结果分析等）
测试数据：a(b(c),d(e(f,g),h(,i)))，abc$$$def$$g$$h$i$$ 结果分析：针对该二叉树，程序输出深度为4，正确；查找值f能够找到，正确；先序遍历结果为a b c d e f g h i，正确；中序遍历结果为c b a f e g d h i，正确；后续遍历结果为c b f g e I h d a，正确；输出二叉树的结果与输入一致，正确；使用先序输入二叉树和横向输出部分正确。选作部分，层序遍历结果为a b d c e h f g i，正确；以结点d为根结点的子树深度为3，正确。
五.心得体会
（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）
【附录----源程序】
