华中科技大学计算机学院数据结构实验报告
⑿获得右孩子结点：函数名称是RightChild(T,e)；初始条件是二叉树T已存在，e是T中某个结点；操作结果是返回e的右孩子结点指针。若e无右孩子，则返回NULL。
⒀获得左兄弟结点：函数名称是LeftSibling(T,e)；初始条件是二叉树T存在，e是T中某个结点；操作结果是返回e的左兄弟结点指针。若e是T的左孩子或者无左兄弟，则返回NULL。
⒁获得右兄弟结点：函数名称是RightSibling(T,e)；初始条件是二叉树T已存在，e是T中某个结点；操作结果是返回e的右兄弟结点指针。若e是T的右孩子或者无有兄弟，则返回NULL。
⒂插入子树：函数名称是InsertChild(T,p,LR,c)；初始条件是二叉树T存在，p指向T中的某个结点，LR为0或1，,非空二叉树c与T不相交且右子树为空；操作结果是根据LR为0或者1，插入c为T中p所指结点的左或右子树，p 所指结点的原有左子树或右子树则为c的右子树。
⒃删除子树：函数名称是DeleteChild(T.p.LR)；初始条件是二叉树T存在，p指向T中的某个结点，LR为0或1。 操作结果是根据LR为0或者1，删除c为T中p所指结点的左或右子树。
⒄前序遍历：函数名称是PreOrderTraverse(T,Visit())；初始条件是二叉树T存在，Visit是对结点操作的应用函数；操作结果：先序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。
⒅中序遍历：函数名称是InOrderTraverse(T,Visit))；初始条件是二叉树T存在，Visit是对结点操作的应用函数；操作结果是中序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。
⒆后序遍历：函数名称是PostOrderTraverse(T,Visit))；初始条件是二叉树T存在，Visit是对结点操作的应用函数；操作结果是后序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。
⒇按层遍历：函数名称是LevelOrderTraverse(T,Visit))；初始条件是二叉树T存在，Visit是对结点操作的应用函数；操作结果是层序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。
19
华中科技大学计算机学院数据结构实验报告
2.1.3演示系统与数据文件
要求构造一个具有菜单的功能演示系统。其中，在主函数中完成函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提示。附录A中给出了简单菜单的框架。演示系统可选择实现线性表的文件形式保存，演示系统可选择实现多个线性表的管理。
2.2系统设计
2.2.1 数据物理结构
二叉树的数据物理结构如下： typedef struct BiTNode { TElemType data;
struct BiTNode *lchild, *rchild;//左右孩子指针 int index; }BiTNode,*BiTree;
//typedef是将结构类型定义struct BiTNode取别名为BiTNode 2.2.2 演示系统
将菜单演示和用户选择输入写入到while循环中，用op获取用户的选择。Op初始化为1，以便第一次能进入循环。进入while循环后，系统首先显示功能菜单，然后提示用户输入选择（0-20），其中1-20对应二叉树的一个基本操作，分别对应一个函数，通过switch语句将用户输入的序号对应到相应的函数功能，执行完该语句后break跳出switch语句，执行while循环，直到用户输入0选择退出，退出系统。
20
华中科技大学计算机学院数据结构实验报告
图2-1 系统设计结构图
2.2.3 运算算法思想与设计
二叉树运算算法思想与设计如下：
1、 初始化二叉树算法思想：将初始化二叉树过程写成函数，函数的参数是主函数中所定义的结构类型指针T（参数传递为引用方式，即取别名），T所指向的是二叉树的根结点，将T赋值为NULL即完成了二叉树的初始化。经分析，该算法的时间复杂度为O(1)。
2、 销毁二叉树算法思想：将二叉树的销毁过程写成函数，函数的参数是指向二叉树根结点的结构类型指针T，采取递归的方式先销毁二叉树的左子树，在销毁二叉树的右子树，最后用free函数释放掉根结点对应的内存空间。经分析，该算法的时间复杂度为O(n)。
3、 创建二叉树算法思想：将二叉树的创建过程写成函数，函数的参数是指向二叉树根结点的结构类型指针T，按照先序次序输入二叉树中结点的值，如果第一个字符为#，则T为空二叉树。否则，malloc函数分配一个单元的空间作为树的根结点，并为其赋值，采取递归的方式继续创建根结点的左子树和右子树。经分析，该算法的时间复杂度为O(n)。
4、 清空二叉树算法思想：将二叉树的清空过程写成函数，函数的参数同上，将根结点的左右孩子指针置为空，此时其左右子树的存储空间并未释放掉。经分析，该算法的时间复杂度为O(1)。
5、 判定空二叉树的算法思想：将判定空二叉树写成函数，对于一个二叉树，若根结点不存在则为空二叉树，否则不是空二叉树，那么只需要判断指向根结点的结构类型指针T是否为空即可。经分析，该算法的时间复杂
21
华中科技大学计算机学院数据结构实验报告
度为O(1)。
6、 求二叉树的深度算法思想：将求二叉树的深度写成函数，采取递归的方式求二叉树的深度，如果根结点的左右孩子都不存在，则返回树的深度为1，否则的话返回根结点左右子树的深度的最大加上一。经分析，该算法的时间复杂度为O(n)。
7、 获得二叉树根结点的算法思想：将求二叉树根结点写成函数，传入头结点，若其头指针不为空，则返回该结点的关键字信息。经分析，该算法的时间复杂度为O(1)。
8、 获得结点的算法思想是：将获得关键字结点写成函数，函数的参数是二叉树的头指针以及主函数中输入的关键字，通过递归先序遍历二叉树，即先比较根结点的关键字与给定是否一致，若一致，返回该结点的INDEX值，否则继续分别递归遍历其左子树和右子树。或者采取非递归的方式，即使用堆栈来存储根结点的信息，先将根结点入栈，在循环中弹出栈顶元素，比较关键字，在分别将其右子树和左子树的根结点入栈。经分析，该算法的时间复杂度为O(n)。
9、 结点赋值的算法思想是：将结点赋值写成函数，函数的参数是二叉树的头指针，主函数中输入的关键字，根据关键字获取到根结点，并对根结点赋值，思想同8，不在赘述。经分析，该算法的时间复杂度为O(n)。 10、 获得双亲结点的算法思想是：将获得双亲结点写成函数，函数的参数是二叉树的头指针，若头指针为空，则返回空；否则，如果头指针左孩子或右孩子不为空且关键字与给定关键字相同，返回根结点，如果不同，采取递归的方式调用原函数，传入的参数分别为根结点的左右子树的根结点。经分析，该算法的时间复杂度为O(n)。
11、 获得左兄弟结点的算法思想是：将获得左孩子结点写成函数，函数的参数是二叉树的头指针，如果头指针为空，返回NULL；否则，如果二叉树的根结点的右孩子关键字与给定关键字一致，返回根结点的左孩子。如果不一致，继续递归调用原函数，传入的参数为二叉树根结点的左子树的根结点指针，如果函数的返回值非空，则返回该值，否则继续调用原函数，传入的参数是二叉树根结点的右子树的根结点指针，如果函数的返回值为非空，则返回该值，否则返回NULL。经分析，该算法的时间复杂度为O(n)。
12、 获得右兄弟结点的算法思想是:算法思想同上。经分析，该算法的时间复杂度为O(n)。
13、 获得左孩子结点的算法思想是：将获得左孩子结点写成函数，函数的参数是二叉树的头指针。如果根结点的关键字与给定关键字一致，且其左孩子存在，则返回其左孩子关键字，否则递归调用原函数分别将根结点的左右子树根结点指针作为形参，若返回值非空则返回该值。经分析，该算法的时间复杂度为O(n)。
14、 获得右孩子结点的算法思想是：算法思想同上。经分析，该算法的时间复杂度为O(n)。
15、 插入子树的算法思想是：将插入子树写成函数，函数的形参是二叉树的头指针T，指向特定二叉树结点的指针p（在主函数中要求输入关键字，通过FIND函数找到插入点位置并将其值记录），再调用CreateBiTNode函数创建根结点c的右子树为空的二叉树，插入的过程即将P所指向结
22
华中科技大学计算机学院数据结构实验报告
点的左子树或者右子树根结点指针赋值给c的右孩子指针域，而c赋值给p所指结点的左指针域或者右指针域。经分析，该算法的时间复杂度为O(n)。
16、 删除子树的算法思想是：将删除子树写成函数，函数的形参是二叉树的头指针，特定结点的指针，根据指向特定结点的指针找到给结点并将其左右孩子指针域置为空，对应的还应该在这之前调用DESTROY函数将其左子树或右子树销毁。经分析，该算法的时间复杂度为O(n)。 17、 前序遍历的算法思想是：将前序遍历写成函数，函数的形参是二叉树的头指针，首先访问根结点，并对其执行遍历操作，操作成功后采取递归的方式遍历根结点的左子树，返回值为OK时继续遍历其右子树，最终遍历完成。递归方法前序遍历、中序遍历以及后序遍历的根本区别在与访问根结点的操作是在两次递归操作之间之前还是之后。经分许，该算法的时间复杂度为O(n)。
18、 非递归前序遍历的算法思想是：将非递归前序遍历写成函数，函数的形参是二叉树的头指针，仿照递归过程堆栈的使用，首先将根结点的值压入堆栈，执行循环体，堆栈非空，弹出根结点并执行访问操作，将其右子树根结点指针压入堆栈，再将其左子树根结点指针压入堆栈，执行循环。经分析，该算法的时间复杂度为O(n)。
19、 非递归中序遍历的算法思想是：将非递归中序遍历写成函数，函数的形参是二叉树的头指针，首先将根结点的值压入堆栈，然后一直向左，将根结点依次压入堆栈，判断堆栈非空，将栈顶元素弹出，访问该结点，如果其右子树非空，对其右子树执行循环操作。经分析，该算法的时间复杂度为O(n)。
20、 层序遍历的算法思想是：将层序遍历写成函数，函数的形参是二叉树的头指针，借助队列，使根结点进入队列，根结点出队列，执行访问操作，此时将根结点的左右子树根结点依次进入队列，即队列中的某个元素出队列时将其左右子树根结点放进队列，循环即可一层一层的访问二叉树。经分析，该算法的时间复杂度为O(n)。
2.3 系统实现
2.3.1 编程环境、运行环境、项目工程描述
本次实验采用Microsoft Visual Studio 2015编程软件编写，并用VS2015进行编译运行，项目名称是BinaryTree。 2.3.2 头文件及预定义常量说明 1、头文件
#include
#include
（1）函数结果状态宏定义 #define TRUE 1
23