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

1、课 程 实 验 报 告课程名称： 数据结构实验 专业班级： 信息安全201502 学 号： 姓 名： 指导教师： 报告日期： 2016年 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返回其值。遍历表：函数名称是ListTraverse(L,vis

7、it()，初始条件是线性表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分别代表线性表的一个基本运算，在主函数中通过SWITCH语句对应到

9、相应的函数功能，执行完该功能后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. 求线性表表长的思想：将求表长过程写成函数，其中主函数中定义的结构性变量L的引用作为函数

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

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

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

14、素直到最后一个元素以此从前往后向前移动一个单元。经分析，该算法的时间复杂度为O（n）。11. 遍历线性表算法思想：将遍历线性表写成一个函数，函数的参数是结构类型变量，直接用一个循环来对线性表中的每一个元素进行操作。经分析，该算法的时间复杂度为O(n)。图内容：字体大小参考宋体5号，居中1.3 系统实现黑体4号加粗，间距前后0.5行1.3.1 编程环境、运行环境、项目工程描述本次实验采用Microsoft Visual Studio 2015编程软件编写，并用VS2015进行编译运行，项目名称是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

16、-99号线性表哪一个进行操作。如图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，测试结果

19、如图1-10所示。图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）

23、在D中存在唯一的成为根的数据元素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存在；操作

25、结果是若T为空二叉树则返回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或者1，删除c为T中

28、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 系统设计黑体4号加粗，间距前后

30、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、 销毁二叉树算法思想：将二叉树的销毁过程写成函数，函数的参数是指向二叉树根结点的结构类型指针T，采取递归的

32、方式先销毁二叉树的左子树，在销毁二叉树的右子树，最后用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、 结点赋值的算法思想是：将结点赋值写成函数，函数的参数是二叉树的头指针，主函数中输入的关键字，根据关键字获取到根结点，并对根结点赋值，思想同8，不在赘述。经分析，该算法

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

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

37、算法思想同上。经分析，该算法的时间复杂度为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 2015编程软件编写，并用VS2015进行编译运行，项目名称是BinaryTree。2.3.2 头文件及预定义常量说明1、头文件#include <stdio.h>#include <malloc.h>#include <stdlib.h>2、预定义常量（1）函数结果状态宏定义#

41、define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2（2）类型表达式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，会执行序号所对应的操作。图2-3 演示系统操作图23.输入序

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

43、iTreeDepth无二叉树的深度为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）输入查找关键字为B的结点输出关键字为B的

44、结点右孩子为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的左子树作为新生成二叉树的右子树17.Dele

45、teChild输入查找关键字为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所示。图2-5 初始化二

46、叉树测试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-10 层序遍历二叉树的

47、测试结果上述测试与预期的遍历结果是一致的，说明生成二叉树的结构正确性，即生成了如图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-15 对指定结点重新赋值

48、测试结果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.执行功能15，在原二叉树的

49、基础上插入子树，测试结果如图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 Edition, Calvin

52、 College, 2005 3 殷立峰. Qt C+跨平台图形界面程序设计基础. 清华大学出版社,2014: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>#include <

53、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_Sqstatus DestroyList(SqList &L)