华中科技大学数据结构实验报告

1、课 程 实 验 报 告课程名称： 数据结构实验 专业班级： 信息平安202102 学 号： 姓 名： 指导教师： 报告日期： 2021年 10月 28 日 计算机科学与技术学院华中科技大学计算机学院数据结构实验报告目 录黑体小2号加粗居中.间距前后0.5行1基于顺序存储结构的线性表实现11.1问题描述11.2系统设计11.3系统实现11.4实验小结12 基于二叉链表的二叉树实现22.1问题描述22.2系统设计22.3系统实现22.4实验小结2指导教师评定意见3附录A 基于顺序存储结构线性表实现的源程序4附录B 基于二叉链表二叉树实现的源程序5章为宋体小4号加粗，其余宋体小4号，行间距1.5倍,

2、段落前后0行华中科技大学计算机学院数据结构实验报告1 基于顺序存储结构的线性表实现黑体小2加粗，居中，间距前后0.5行1.1 问题描述黑体4号加粗，间距前后0.5行采用顺序表的物理结构，构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示。定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等根本运算对应的函数，并给出适当的操作提示显示，可选择以文件的形式进行存储和加载，即将生成的线性表存入到相应的文件中，也可以从文件中获取线性表进行操作。1.1.1 线性表的根本概念线性表是最常用且最简单的一种数据结构，即n个数据元素的有限序列。线性表

3、中元素的个数n定义为线性表的长度，n=0时成为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素。线性表的存储结构分为线性存储和链式存储。1.1.2 逻辑结构与根本运算线性表的数据逻辑结构定义如下: ADT List 数据对象：D=ai|aiElemSet，i=1，2，n，n0 数据关系：R1= <ai-1，ai> | ai-1，aiD，i=2，n 依据最小完备性和常用性相结合的原那么，以函数形式定义了包括线性表的初始化表、加载表、保存表、销毁表、清空表、判定空表、求表长、获得元素、查找元素、获得前驱、获得后继、插

4、入元素、删除元素、遍历表 14 个根本运算，要求分别定义函数来实现上述功能，具体功能运算如下：初始化表：函数名称是InitaList(L)；初始条件是线性表L不存在已存在；操作结果是构造一个空的线性表。销毁表：函数名称是DestroyList(L)；初始条件是线性表L已存在；操作结果是销毁线性表L。清空表：函数名称是ClearList(L)；初始条件是线性表L已存在；操作结果是将L重置为空表。判定空表：函数名称是ListEmpty(L)；初始条件是线性表L已存在；操作结果是假设L为空表那么返回TRUE,否那么返回FALSE。求表长：函数名称是ListLength(L)；初始条件是线性表已存在；

5、操作结果是返回L中数据元素的个数。获得元素：函数名称是GetElem(L,i,e)；初始条件是线性表已存在，1iListLength(L)；操作结果是用e返回L中第i个数据元素的值。查找元素：函数名称是LocateElem(L,e,compare()；初始条件是线性表已存在；操作结果是返回L中第1个与e满足关系compare关系的数据元素的位序，假设这样的数据元素不存在，那么返回值为0。获得前驱：函数名称是PriorElem(L,cur_e,pre_e)；初始条件是线性表L已存在；操作结果是假设cur_e是L的数据元素，且不是第一个，那么用pre_e返回它的前驱，否那么操作失败，pre_e无定

6、义。获得后继：函数名称是NextElem(L,cur_e,next_e)；初始条件是线性表L已存在；操作结果是假设cur_e是L的数据元素，且不是最后一个，那么用next_e返回它的后继，否那么操作失败，next_e无定义。插入元素：函数名称是ListInsert(L,i,e)；初始条件是线性表L已存在且非空，1iListLength(L)+1；操作结果是在L的第i个位置之前插入新的数据元素e。删除元素：函数名称是ListDelete(L,i,e)；初始条件是线性表L已存在且非空，1iListLength(L)；操作结果：删除L的第i个数据元素，用e返回其值。遍历表：函数名称是ListTrav

7、erse(L,visit()，初始条件是线性表L已存在；操作结果是依次对L的每个数据元素调用函数visit()。1.1.3 演示系统与数据文件要求构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提示显示。附录 A 提供了简易菜单的框架。 演示系统可选择实现线性表的文件形式保存。其中，需要设计文件数据记录格式，以高效保存线性表数据逻辑结构(D,R)的完整信息；需要设计线性表文件保存和加载操作合理模式。附录 B 提供了文件存取的方法。 演示系统可选择实现多个线性表管理。1.2 系统设计黑体4号加粗，间距前后0.5行1.2.1 数据物

8、理结构线性表的数据物理结构如下：typedef struct /顺序表顺序结构的定义 ElemType *elem; /定义整型指针，为存储空间基址 int length; /线性表的长度 int listsize; /当前分配的存储容量(以 sizeof(ElemType)为单位) SqList;要实现同时对多个线性表管理，只需要定义一个结构数组即可。1.2.2 演示系统将菜单演示和用户选择写入到while循环中，用OP获取用户的选择，OP初始化为1，以便第一次能进入循环。进入循环后系统首先显示功能菜单，然后用户输入选择0-14，其中1-14分别代表线性表的一个根本运算，在主函数中通过SWI

9、TCH语句对应到相应的函数功能，执行完该功能后BREAK跳出SWITCH语句，继续执行while循环，直至用户输入0退出当前演示系统。在第一次进入循环while时首先会询问用户对哪个线性表进行操作，直至退出演示系统之前一直对指定线性表进行操作。演示系统结构如图1- 运算算法思想与设计线性表运算算法思想与设计如下：1. 初始化线性表思想：将线性表初始化过程写成函数，其中传入函数的参数是主函数中定义的结构型变量L的引用，在函数中，首先使用malloc函数分配LISTSIZE大小的连续内存空间，并将首地址返回赋值给L.elem，由于线性表的长度为0，将L.length初始化为0，即完成

10、了线性表的初始化。经分析，算法的时间复杂度为O(1)。2. 销毁线性表思想：将销毁线性表的过程写成函数，其中传入函数是主函数中定义的结构性变量L。在函数中，首先使用free函数释放掉以L.elem为首地址的连续内存空间，再将L.length,L.listsize重新赋值为0。经分析，该算法的时间复杂度为O(1)。3. 清空线性表的思想：将清空表的过程写成函数，其中将主函数中定义的结构性变量L的引用作为函数参数，在函数中，由于清空操作并不释放内存空间，故只需将线性表的长度置为0即可。经分许，该算法的时间复杂度为O(1)。4. 求线性表表长的思想：将求表长过程写成函数，其中主函数中定义的结构性变量

11、L的引用作为函数的参数，在函数中，直接返回L.length即为所求线性表的表长。经分析，该算法的时间复杂度为O1。5. 获得元素的算法思想：将获得线性表元素写成函数，其中函数的参数是结构型变量L以及数据元素的序号i，由于采取的是线性存储结构，故直接通过访问数组的方式即L.elemi-1来获取元素，当然，在这之前需要判断合法性。经分析，该算法的时间复杂度为O1。6. 查找元素的算法思想：将查找线性表特定值的数据元素写成函数，其中函数的参数是主函数中定义的结构类型变量L以及查找的数据元素的值，通过循环对线性表中的每一个元素与给定值比拟看是否相等，如果相等就返回该元素的次序。经分析，该算法的时间复杂

12、度为On。查找算法的流程图如图1-2所示。图1-2 线性表查找算法流程图7. 获得前驱算法思想：将获得前驱过程写成函数，函数的参数是结构体类型变量以及特定数据元素的值，接受前驱的变量作为另一个参数，首先调用获得元素的函数判断该线性表中特定数据元素的位序，首先判断不为1，否那么的话返回FALSE，然后直接返回其前一个元素即L.elemj-2。经分析，该算法的时间复杂度为On。8. 获得后继算法思想：将获得后继写成函数，函数的参数是结构体类型变量以及特定数据元素的值。首先判断是否为最后一个元素，如果不是那么直接返回其后一个元素，否那么的话返回FALSE，同样该算法需要调用获得元素的函数来确定该特定

13、元素在线性表中的次序。经分析，该算法的时间复杂度为On。9. 插入元素算法思想：将插入函数写成函数，函数的参数是结构型变量以及插入元素的值大小以及插入位置。在函数中，首先判断插入位置的合法性，即是否在线性表中适宜的位置，其次还要判断当前存储空间是否已满，如果满了的话要malloc函数重新分配空间，插入元素时从该位置起到最后一个元素从后开始以此往后移一个单元。经分析，该算法的时间复杂度为On。该算法的程序流程图如图1-3所示。图1-3 线性表中插入元素算法流程图10. 删除元素算法思想：将删除线性表中元素写成函数，函数的参数是结构类型变量，首先判断位序的合法性，在之后直接将删除元素位置后一个元素

14、直到最后一个元素以此从前往后向前移动一个单元。经分析，该算法的时间复杂度为On。11. 遍历线性表算法思想：将遍历线性表写成一个函数，函数的参数是结构类型变量，直接用一个循环来对线性表中的每一个元素进行操作。经分析，该算法的时间复杂度为O(n)。图内容：字体大小参考宋体5号，居中1.3 系统实现黑体4号加粗，间距前后0.5行1.3.1 编程环境、运行环境、工程工程描述本次实验采用Microsoft Visual Studio 2021编程软件编写，并用VS2021进行编译运行，工程名称是linear datastructer。1.3.2 头文件及预定义常量说明1.头文件#include <

15、;stdio.h>#include <malloc.h>#include <stdlib.h>2.预定义常量#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASTABLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 103.类型表达式typedef int status;typedef int ElemType;1.3.3 系统演示操作1.系统一开始会显示菜单提示用户输入选择对1-99

16、号线性表哪一个进行操作。如图1-4所示。图1-4 系统演示12.选择对线性表1进行操作，进入菜单演示界面，如图1-5所示。图1-5 系统演示23.选择退出0，此时会退出当前演示界面，即退出对当前线性表的操作，并显示要求用户选择对哪一个线性表进行操作。如图1-6所示。图1-6 演示系统34.输入0，退出演示系统，结束操作，如图1-7所示。图1-7 系统演示41.3.4 测试方案测试功能及序号输入要管理的线性表序号输入函数的参数具体元素预计输出此时线性表的状态1.IntiaList1无线性表初始化成功分配了连续的物理存储空间，表长度为0，表尺寸为空间大小2.DestroyList1无线性表删除成功

17、线性表连续物理空间被释放， 3.ClearList1无线性表清空成功线性表的物理空间保存，但表长置为0.10.ListInsert(屡次调用)1输入1：1，2：2，3：3，4：4，5：5线性表创立成功创立了一个线性表，序列为：1，2，3，4，54.ListEmpty1无输出线性表非空同上5.ListLength1无输出线性表的长度为5同上6.GetElem1输入数据元素的位序为3输出线性表的第三个元素为3同上8.PriorElem1输入数据元素的值为4输出4的前面一个元素是3同上9.NextElem1输入数据元素的值为2输出2的后面一个元素是3同上11.ListDelete1输入数据元素的置为

18、3输出元素删除成功重新生成了一新的线性表，序列为12457.LocateElem1输入数据元素的值为4输出4是线性表中的第三个数据元素同上13.SaveData1输入保存到的文件名为LY.txt输出文件保存成功同上14.DataLoading1输入要加载的文件名为LY.txt输出文件加载成功同上1.3.5 测试1.输入对线性表1进行操作，进入菜单演示界面，执行功能1，初始化线性表，测试结果如图1-8所示。图1-8 初始化线性表的测试结果2.执行功能2，销毁线性表，测试结果如图1-9所示。图1-9 删除线性表的操作结果3.执行功能10，往线性表中添加数据元素1,2,3,4,5，测试结果如图1-1

19、0所示。图1-10 插入元素的测试结果4.执行功能4，判断线性表是否为空，测试结果如图1-11所示。图1-11 判断线性表非空的测试结果5.执行功能5，求线性表的长度，测试结果如图1-12所示。图1-12 求线性表长度的测试结果6.执行功能6，查找第三个数据元素的数值，测试结果如图1-13所示。图1-13 查找数据元素的测试结果7.执行功能8，确定值为4的数据元素前驱数据元素，测试结果如图1-14所示。图1-14 查找元素的前驱数据元素8.执行功能9，确定值为2的数据元素的后继数据元素，测试结果如图1-15所示。1-15 查找元素的后继数据元素9.执行功能11，删除第三个数据元素，测试结果如图

20、1-16所示。图1-16 删除线性表中的数据元素测试结果10.执行功能13，保存线性表中的数据元素值到文件名为LY.txt的文件中，测试结果如图1-17所示。图1-17 保存线性表测试结果11.清空此时的线性表，在执行功能14，加载线性表，测试结果如图1-18所示。图1-18 线性表加载的测试结果11.执行功能12，遍历并输出线性表中的元素，应该输出1245，测试结果如图1-19所示。图1-19 遍历输出线性表中元素的测试结果1.4 实验小结黑体4号加粗，间距前后0.5行经过本次试验，我充分了解到了线性表的物理结构，并且通过切身的体会熟练掌握了线性表的根本操作，提高了自己写有关线性表的代码的能

21、力，尤其是在写的过程中遇到了许多困难，在屡次寻求同学的帮助下终于解决了。还发现了自己的薄弱之处，就是在文件的处理时存在许多纰漏，导致文件读取不成功。并且我还加深了对线性表的存在与空的区别。还有对“&引用符号的理解，加强了其与“*的区别，“&e使得在函数中调用主函数中的值“e时可以同时更改其值，如在GetElem函数 中调用了“e的值然后在主函数中输出，如果要更改其值的话就必须要用“&符号。2 基于二叉链表的二叉树实现黑体小2加粗，居中，间距前后0.5行，每章另起页2.1 问题描述黑体4号加粗，间距前后0.5行采用二叉链表作为二叉树的物理结构，实现二叉树的根本运算，数据元

22、素的类型名可自行定义。要求构造一个具有菜单的功能演示系统，其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提示。2.1.1 二叉树的根本概念二叉树是一种树型结构，即n个结点的有限集，它的特点是每个结点至多只有两棵子树即二叉树中不存在度大于2的结点，并且，二叉树的子树有左右之分，其次序不能任意颠倒。2.1.2 逻辑结构与根本运算抽象数据类型二叉树的定义如下：ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R:假设D=，那么R=，称BinaryTree为空二叉树；假设D，那么R=H,H是如下二元关系：（1） 在D中存在唯一的成

23、为根的数据元素root，它在关系H中无前驱；（2） 假设D-root,那么存在D-root=D1,Dr,且D1Dr=;（3） 假设D1，那么D1中存在唯一的元素X1，<root,X1>H，且存在D1上的关系H1包含于H；假设Dr,那么Dr中存在唯一的元素Xr，<root,Xr>H,且存在Dr上的关系属于H；（4） D，H1是一棵符合本定义的二叉树，称为根的左子树，Dr，Hr是一棵符合本定义的二叉树，称为根的右子树。依据最小最小完备性和常用性相结合的原那么，以函数形式定义了二叉树的初始化、销毁二叉树、创立二叉树、清空二叉树、判定空二叉树和求二叉树深度等20种根本运算，具体

24、运算功能定义如下：初始化二叉树：函数名称是InitBiTree(T)；初始条件是二叉树T不存在；操作结果是构造空二叉树T。销毁二叉：树函数名称是DestroyBiTree(T)；初始条件是二叉树T已存在；操作结果是销毁二叉树T。创立二叉树：函数名称是CreateBiTree(T,definition)；初始条件是definition 给出二叉树T的定义；操作结果是按definition构造二叉树T。清空二叉树：函数名称是ClearBiTree (T)；初始条件是二叉树T存在；操作结果是将二叉树T清空。判定空二叉树：函数名称是BiTreeEmpty(T)；初始条件是二叉树T存在；操作结果是假设T

25、为空二叉树那么返回TRUE，否那么返回FALSE。求二叉树深度：函数名称是BiTreeDepth(T)；初始条件是二叉树T存在；操作结果是返回T的深度。获得根结点：函数名称是Root(T)；初始条件是二叉树T已存在；操作结果是返回T的根。获得结点：函数名称是Value(T,e)；初始条件是二叉树T已存在，e是T中的某个结点；操作结果是返回e的值。结点赋值：函数名称是Assign(T,&e,value)；初始条件是二叉树T已存在，e是T中的某个结点；操作结果是结点e赋值为value。获得双亲结点：函数名称是Parent(T,e) ；初始条件是二叉树T已存在，e是T中的某个结点；操作结果是

26、假设e是T的非根结点，那么返回它的双亲结点指针，否那么返回NULL。获得左孩子结点：函数名称是LeftChild(T,e)；初始条件是二叉树T存在，e是T中某个节点；操作结果是返回e的左孩子结点指针。假设e无左孩子，那么返回NULL。获得右孩子结点：函数名称是RightChild(T,e)；初始条件是二叉树T已存在，e是T中某个结点；操作结果是返回e的右孩子结点指针。假设e无右孩子，那么返回NULL。获得左兄弟结点：函数名称是LeftSibling(T,e)；初始条件是二叉树T存在，e是T中某个结点；操作结果是返回e的左兄弟结点指针。假设e是T的左孩子或者无左兄弟，那么返回NULL。获得右兄弟

27、结点：函数名称是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或

28、者1，删除c为T中p所指结点的左或右子树。前序遍历：函数名称是PreOrderTraverse(T,Visit()；初始条件是二叉树T存在，Visit是对结点操作的应用函数；操作结果：先序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，那么操作失败。中序遍历：函数名称是InOrderTraverse(T,Visit)；初始条件是二叉树T存在，Visit是对结点操作的应用函数；操作结果是中序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，那么操作失败。后序遍历：函数名称是PostOrderTraverse(T,Visit)；初始条件是二叉树T存在，Visit是对结点操

29、作的应用函数；操作结果是后序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，那么操作失败。按层遍历：函数名称是LevelOrderTraverse(T,Visit)；初始条件是二叉树T存在，Visit是对结点操作的应用函数；操作结果是层序遍历t，对每个结点调用函数Visit一次且一次，一旦调用失败，那么操作失败。2.1.3 演示系统与数据文件要求构造一个具有菜单的功能演示系统。其中，在主函数中完成函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提示。附录A中给出了简单菜单的框架。演示系统可选择实现线性表的文件形式保存，演示系统可选择实现多个线性表的管理。2.2 系统

30、设计黑体4号加粗，间距前后0.5行2.2.1 数据物理结构二叉树的数据物理结构如下：typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild;/左右孩子指针int index;BiTNode,*BiTree;/typedef是将结构类型定义struct BiTNode取别名为BiTNode2.2.2 演示系统将菜单演示和用户选择输入写入到while循环中，用op获取用户的选择。Op初始化为1，以便第一次能进入循环。进入while循环后，系统首先显示功能菜单，然后提示用户输入选择0-20，其中1-20对应二叉树的一

31、个根本操作，分别对应一个函数，通过switch语句将用户输入的序号对应到相应的函数功能，执行完该语句后break跳出switch语句，执行while循环，直到用户输入0选择退出，退出系统。图2-1 系统设计结构图2.2.3 运算算法思想与设计二叉树运算算法思想与设计如下：1、 初始化二叉树算法思想：将初始化二叉树过程写成函数，函数的参数是主函数中所定义的结构类型指针T参数传递为引用方式，即取别名，T所指向的是二叉树的根结点，将T赋值为NULL即完成了二叉树的初始化。经分析，该算法的时间复杂度为O(1)。2、 销毁二叉树算法思想：将二叉树的销毁过程写成函数，函数的参数是指向二叉树根结点的结构类型

32、指针T，采取递归的方式先销毁二叉树的左子树，在销毁二叉树的右子树，最后用free函数释放掉根结点对应的内存空间。经分析，该算法的时间复杂度为O(n)。3、 创立二叉树算法思想：将二叉树的创立过程写成函数，函数的参数是指向二叉树根结点的结构类型指针T，按照先序次序输入二叉树中结点的值，如果第一个字符为#，那么T为空二叉树。否那么，malloc函数分配一个单元的空间作为树的根结点，并为其赋值，采取递归的方式继续创立根结点的左子树和右子树。经分析，该算法的时间复杂度为O(n)。4、 清空二叉树算法思想：将二叉树的清空过程写成函数，函数的参数同上，将根结点的左右孩子指针置为空，此时其左右子树的存储空间

33、并未释放掉。经分析，该算法的时间复杂度为O(1)。5、 判定空二叉树的算法思想：将判定空二叉树写成函数，对于一个二叉树，假设根结点不存在那么为空二叉树，否那么不是空二叉树，那么只需要判断指向根结点的结构类型指针T是否为空即可。经分析，该算法的时间复杂度为O(1)。6、 求二叉树的深度算法思想：将求二叉树的深度写成函数，采取递归的方式求二叉树的深度，如果根结点的左右孩子都不存在，那么返回树的深度为1，否那么的话返回根结点左右子树的深度的最大加上一。经分析，该算法的时间复杂度为O(n)。7、 获得二叉树根结点的算法思想：将求二叉树根结点写成函数，传入头结点，假设其头指针不为空，那么返回该结点的关键

34、字信息。经分析，该算法的时间复杂度为O(1)。8、 获得结点的算法思想是：将获得关键字结点写成函数，函数的参数是二叉树的头指针以及主函数中输入的关键字，通过递归先序遍历二叉树，即先比拟根结点的关键字与给定是否一致，假设一致，返回该结点的INDEX值，否那么继续分别递归遍历其左子树和右子树。或者采取非递归的方式，即使用堆栈来存储根结点的信息，先将根结点入栈，在循环中弹出栈顶元素，比拟关键字，在分别将其右子树和左子树的根结点入栈。经分析，该算法的时间复杂度为O(n)。9、 结点赋值的算法思想是：将结点赋值写成函数，函数的参数是二叉树的头指针，主函数中输入的关键字，根据关键字获取到根结点，并对根结点

35、赋值，思想同8，不在赘述。经分析，该算法的时间复杂度为O(n)。10、 获得双亲结点的算法思想是：将获得双亲结点写成函数，函数的参数是二叉树的头指针，假设头指针为空，那么返回空；否那么，如果头指针左孩子或右孩子不为空且关键字与给定关键字相同，返回根结点，如果不同，采取递归的方式调用原函数，传入的参数分别为根结点的左右子树的根结点。经分析，该算法的时间复杂度为O(n)。11、 获得左兄弟结点的算法思想是：将获得左孩子结点写成函数，函数的参数是二叉树的头指针，如果头指针为空，返回NULL；否那么，如果二叉树的根结点的右孩子关键字与给定关键字一致，返回根结点的左孩子。如果不一致，继续递归调用原函数，

36、传入的参数为二叉树根结点的左子树的根结点指针，如果函数的返回值非空，那么返回该值，否那么继续调用原函数，传入的参数是二叉树根结点的右子树的根结点指针，如果函数的返回值为非空，那么返回该值，否那么返回NULL。经分析，该算法的时间复杂度为O(n)。12、 获得右兄弟结点的算法思想是:算法思想同上。经分析，该算法的时间复杂度为O(n)。13、 获得左孩子结点的算法思想是：将获得左孩子结点写成函数，函数的参数是二叉树的头指针。如果根结点的关键字与给定关键字一致，且其左孩子存在，那么返回其左孩子关键字，否那么递归调用原函数分别将根结点的左右子树根结点指针作为形参，假设返回值非空那么返回该值。经分析，该

37、算法的时间复杂度为O(n)。14、 获得右孩子结点的算法思想是：算法思想同上。经分析，该算法的时间复杂度为O(n)。15、 插入子树的算法思想是：将插入子树写成函数，函数的形参是二叉树的头指针T，指向特定二叉树结点的指针p在主函数中要求输入关键字，通过FIND函数找到插入点位置并将其值记录，再调用CreateBiTNode函数创立根结点c的右子树为空的二叉树，插入的过程即将P所指向结点的左子树或者右子树根结点指针赋值给c的右孩子指针域，而c赋值给p所指结点的左指针域或者右指针域。经分析，该算法的时间复杂度为O(n)。16、 删除子树的算法思想是：将删除子树写成函数，函数的形参是二叉树的头指针，

38、特定结点的指针，根据指向特定结点的指针找到给结点并将其左右孩子指针域置为空，对应的还应该在这之前调用DESTROY函数将其左子树或右子树销毁。经分析，该算法的时间复杂度为O(n)。17、 前序遍历的算法思想是：将前序遍历写成函数，函数的形参是二叉树的头指针，首先访问根结点，并对其执行遍历操作，操作成功后采取递归的方式遍历根结点的左子树，返回值为OK时继续遍历其右子树，最终遍历完成。递归方法前序遍历、中序遍历以及后序遍历的根本区别在与访问根结点的操作是在两次递归操作之间之前还是之后。经分许，该算法的时间复杂度为O(n)。18、 非递归前序遍历的算法思想是：将非递归前序遍历写成函数，函数的形参是二

39、叉树的头指针，仿照递归过程堆栈的使用，首先将根结点的值压入堆栈，执行循环体，堆栈非空，弹出根结点并执行访问操作，将其右子树根结点指针压入堆栈，再将其左子树根结点指针压入堆栈，执行循环。经分析，该算法的时间复杂度为O(n)。19、 非递归中序遍历的算法思想是：将非递归中序遍历写成函数，函数的形参是二叉树的头指针，首先将根结点的值压入堆栈，然后一直向左，将根结点依次压入堆栈，判断堆栈非空，将栈顶元素弹出，访问该结点，如果其右子树非空，对其右子树执行循环操作。经分析，该算法的时间复杂度为O(n)。20、 层序遍历的算法思想是：将层序遍历写成函数，函数的形参是二叉树的头指针，借助队列，使根结点进入队列

40、，根结点出队列，执行访问操作，此时将根结点的左右子树根结点依次进入队列，即队列中的某个元素出队列时将其左右子树根结点放进队列，循环即可一层一层的访问二叉树。经分析，该算法的时间复杂度为O(n)。2.3 系统实现黑体4号加粗，间距前后0.5行2.3.1 编程环境、运行环境、工程工程描述本次实验采用Microsoft Visual Studio 2021编程软件编写，并用VS2021进行编译运行，工程名称是BinaryTree。2.3.2 头文件及预定义常量说明1、头文件#include <stdio.h>#include <malloc.h>#include <st

41、dlib.h>2、预定义常量1函数结果状态宏定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -22类型表达式typedef int status;typedef char TElemType;typedef BiTree QElemType;3系统常量定义#define MAXLENG 10#define MAXSIZE 2#define QMAXSIZE 52.3.3 演示系统操作1.系统一开始会显示功能菜单并提示用户输入选择。图2-2 演示系统操作图12.输入序号020，会执行序号所

42、对应的操作。图2-3 演示系统操作图23.输入序号0，演示系统结束并退出。图2-3 演示系统操作图32.3.4 测试方案测试功能及序号输入函数的参数预计输出此时二叉树的状态1.InitBiTree无二叉树创立成功二叉树根结点指针置为空，未分配具体的存储空间2.DestroyBiTree无二叉树销毁失败二叉树头指针置为空，对应的存储空间被释放3.CreateBiTree依次输入关键字及其对应值：A1 B9 D7 #E0H1#I2#C9F6#G2#J0#二叉树创立成功按照输入关键字的先序序列创立二叉树，每个结点赋值4.ClearBiTree无二叉树清空成功二叉树根结点保存，但其左右指针域置为空5.

43、BiTreeEmpty无二叉树不为空同上36.BiTreeDepth无二叉树的深度为4同上37.Root无二叉树的根结点关键字为A同上38.Value输入关键字为D输出关键字为D的结点值为7同上39.Assign输入关键字E输入关键字为E的结点的值改为9输出关键字为E的结点的值已改为9同上310.Parent输入查找关键字为I的结点输出关键字为I的结点的双亲结点为E同上311.LeftChild(测试1)输入查找关键字为E的结点输出关键字为E的结点的左孩子为H同上312.LeftChild测试2输入查找关键字为F的结点输出关键字为F的左孩子不存在，查找失败同上313.RightChild测试1

44、输入查找关键字为B的结点输出关键字为B的结点右孩子为E同上314.RightChild测试2输入查找关键字为F的结点输出关键字为F的右孩子不存在，操作失败同上315.LeftSibling测试1输入查找关键字为G的结点输出关键字为G的结点左孩子为F同上315.LeftSibling测试2输入查找关键字为B的结点输出关键字为B的结点左孩子不存在，操作失败同上316.InsertChild输入LR值为0，输入查找关键字为J，新生成右子树为空的二叉树输入：M1N2#K3#字母后为该关键字结点的值输出二叉树插入成功在原二叉树的根底上，将新生成二叉树作为关键字为J的结点的左子树，J的左子树作为新生成二叉

45、树的右子树17.DeleteChild输入查找关键字为E的结点，输入LR值为1输出二叉树删除成功在上一根底上，将原二叉树的E结点的右子树删除18.PreOrderTraverse无输出先序遍历序列：ABDEHICFGJ同上319.InOrderTraverse无输出中序遍历序列：DBHEIAFCGJ同上320.PostOrderTraverse无输出后续遍历序列：DHIEBFJGCA同上321.LevelTraverse无输出层序遍历序列：ABCDEFGHIJ同上3表2-1 测试方案图2-4 按以上测试用例生成的原始二叉树2.3.5 测试1.执行功能1.InitBiTree，测试结果如图2-5

46、所示。图2-5 初始化二叉树测试2.执行功能3，创立二叉树，测试结果如图2-6所示。图2-6 二叉树创立3.在上一步的根底上对二叉树的结构进行验证，根据其前序遍历、中序遍历、后续遍历的结果是否与预期一致判断结构是否正确。执行功能17，先序遍历二叉树，并执行PRINT操作，测试结果如图2-7所示。图2-7 先序遍历二叉树的测试结果4.执行功能18，中序遍历二叉树，并执行PRINT操作，测试结果如图2-8所示。图2-8 中序遍历二叉树的测试结果5.执行功能19，后序遍历二叉树，测试结果如图2-9所示。图2-9 后序遍历二叉树的测试结果6.执行功能20，层序遍历二叉树，测试结果如图2-10所示。图2

47、-10 层序遍历二叉树的测试结果上述测试与预期的遍历结果是一致的，说明生成二叉树的结构正确性，即生成了如图2-4所示的二叉树。7.执行功能5，判断二叉树是否为空树，测试结果如图2-11所示。图2-11 判断二叉树是否为空测试结果8.执行功能6，求二叉树的深度，测试结果如图2-12所示。图2-12 求二叉树深度测试结果9.执行功能7，求二叉树的根结点，测试结果如图2-13所示。图2-13 求二叉树根结点的测试结果10.执行功能8，求关键字为D的结点的值，测试结果如图2-14所示。图2-14 求二叉树指定结点的值测试结果11.执行功能9，将关键字为E的结点值改为9，测试结果如图2-15所示。图2-

48、15 对指定结点重新赋值测试结果12.执行功能11，输入查找关键字为E的结点的左孩子，测试结果如图2-16所示。图2-16 查找左孩子的测试结果113.执行功能11，测试关键字为F的结点的左孩子，测试结果如图2-17所示。图2-17 查找左孩子的测试结果214.执行功能10，查找关键字为I的结点的双亲结点，测试结果如图2-18所示。图2-18 查找结点的双亲结点15.执行功能13，查找关键字为E的结点的左兄弟，查找结果如图2-19所示。图2-19 查找结点的左兄弟测试结果116.执行功能13，查找关键字为B的结点的左兄弟，查找结果如图2-20所示。图2-20 查找结点的左兄弟测试结果217.执

49、行功能15，在原二叉树的根底上插入子树，测试结果如图2-21所示。图2-21 插入子树的测试结果插入子树后，先序遍历得到的序列为：ABDEHICFGJMNK,层序遍历得到的序列应该为：ABCDEFGHIJMNK，中序遍历得到的序列为：DBHEIAFCGNKMJ。通过遍历新生成的二叉树验证其结构正确性。图2-22 先序遍历的测试结果图2-23 层序遍历的测试结果图2-24 后序遍历的测试结果以上遍历结果与预期相吻合，说明插入后得到的新二叉树满足结构正确性。18.执行功能16，删除关键字为E的结点的右子树，即I结点，测试结果如图2-25所示。图2-25 删除子树的测试结果未验证结果的正确性，假设对

50、其先序遍历得到的序列应该为：ABDEHCFGJMNK，层序遍历得到的序列应该为：ABCDEFGHJMNK，中序遍历得到的结果应该为：DBHEAFCGNKMJ图2-26 先序遍历的测试结果图2-27 中序遍历的测试结果图2-28 层序遍历的测试结果上面的测试结果与预期相一致，说明删除子树后结构的正确性，函数功能执行正确。19.执行功能2，删除二叉树，此时销毁二叉树的存储空间，头指针置为空，测试结果如图2-29所示。图2-29 销毁二叉树的测试结果二叉树销毁后，进行判断是否为空，应该返回空树，测试结果如图2-30所示。图2-30 验证二叉树为空2.4 实验小结黑体4号加粗，间距前后0.5行通过本次

51、实验，熟悉了二叉树的根本操作，学会了用二叉树去解决一些问题，学习中的主要收获为以下几点：1、 加深了对二叉树的概念和逻辑结构的理解。2、 掌握了二叉树的根本操作。3、 通过递归算法的编写加深了对递归的认识和理解。4、 通过非递归算法的编写加深了对递归内在机制的分析以及学会了如何用堆栈去代替递归到达相同的目的。5、 标准了报告撰写能力。参考文献黑体小2号加粗居中，间距前后0.5行1 严蔚敏等. 数据结构(C语言版). 清华大学出版社2 Larry Nyhoff. ADTs, Data Structures, and Problem Solving with C+.  Second Ed

52、ition, Calvin College, 2005 3 殷立峰. Qt C+跨平台图形界面程序设计根底. 清华大学出版社,2021:1921974 严蔚敏等.数据结构题集(C语言版). 清华大学出版社宋体小4号，行间距1.5倍指导教师评定意见黑体小2加粗居中，间距前后0.5行，另起页一、对实验报告的评语二、对实验报告评分评分工程(分值)程序内容(36.8分)程序标准(9.2分)报告内容(36.8分)报告标准(9.2分)考勤8分逾期扣分合 计(100分)得分附录A 基于顺序存储结构线性表实现的源程序黑体小2加粗居中，间距前后0.5行，另起页#include <stdio.h>#i

53、nclude <malloc.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASTABLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int status;typedef int ElemType;typedef struct ElemType * elem;int length;int listsize;SqList;status Initlist(SqList &L) L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;/InitList