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

课程实验报告

课程名称：数据结构实验

专业班级：信息安全201502 学号： 姓名： 指导教师：

报告日期： 2016年10月 28 日

计算机科学与技术学院

华中科技大学计算机学院数据结构实验报告

目录

1基于顺序存储结构的线性表实现 ..................................... 1 1.1问题描述 ........................................................ 1 1.2系统设计 ........................................................ 3 1.3系统实现 ........................................................ 7 1.4实验小结 ....................................................... 16 2 基于二叉链表的二叉树实现 ....................................... 17 2.1问题描述 ....................................................... 17 2.2系统设计 ....................................................... 20 2.3系统实现 ....................................................... 23 2.4实验小结 ....................................................... 40 指导教师评定意见 ................................................. 42 附录A 基于顺序存储结构线性表实现的源程序 ......................... 44 附录B 基于二叉链表二叉树实现的源程序 ............................. 52

华中科技大学计算机学院数据结构实验报告

1基于顺序存储结构的线性表实现

1.1问题描述

采用顺序表的物理结构，构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示。定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等基本运算对应的函数，并给出适当的操作提示显示，可选择以文件的形式进行存储和加载，即将生成的线性表存入到相应的文件中，也可以从文件中获取线性表进行操作。 1.1.1线性表的基本概念

线性表是最常用且最简单的一种数据结构，即n个数据元素的有限序列。线性表中元素的个数n定义为线性表的长度，n=0时成为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素。线性表的存储结构分为线性存储和链式存储。 1.1.2 逻辑结构与基本运算 线性表的数据逻辑结构定义如下:

ADT List｛

数据对象：D=｛ai|ai∈ElemSet，i=1，2，??，n，n≥0｝ 数据关系：R1=｛ | ai-1，ai∈D，i=2，??，n｝ ｝

依据最小完备性和常用性相结合的原则，以函数形式定义了包括线性表的初 始化表、加载表、保存表、销毁表、清空表、判定空表、求表长、获得元素、查 找元素、获得前驱、获得后继、插入元素、删除元素、遍历表 14 个基本运算， 要求分别定义函数来实现上述功能，具体功能运算如下：

⑴初始化表：函数名称是InitaList(L)；初始条件是线性表L不存在已存在；操作结果是构造一个空的线性表。

⑵销毁表：函数名称是DestroyList(L)；初始条件是线性表L已存在；操作结果是销毁线性表L。

1

华中科技大学计算机学院数据结构实验报告

⑶清空表：函数名称是ClearList(L)；初始条件是线性表L已存在；操作结果是将L重置为空表。

⑷判定空表：函数名称是ListEmpty(L)；初始条件是线性表L已存在；操作结果是若L为空表则返回TRUE,否则返回FALSE。

⑸求表长：函数名称是ListLength(L)；初始条件是线性表已存在；操作结果是返回L中数据元素的个数。

⑹获得元素：函数名称是GetElem(L,i,e)；初始条件是线性表已存在，1≤i≤ListLength(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无定义。

⑼获得后继：函数名称是NextElem(L,cur_e,next_e)；初始条件是线性表L已存在；操作结果是若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。

⑽插入元素：函数名称是ListInsert(L,i,e)；初始条件是线性表L已存在且非空，1≤i≤ListLength(L)+1；操作结果是在L的第i个位置之前插入新的数据元素e。

⑾删除元素：函数名称是ListDelete(L,i,e)；初始条件是线性表L已存在且非空，1≤i≤ListLength(L)；操作结果：删除L的第i个数据元素，用e返回其值。

⑿遍历表：函数名称是ListTraverse(L,visit())，初始条件是线性表L已存在；操作结果是依次对L的每个数据元素调用函数visit()。 1.1.3 演示系统与数据文件

要求构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所 需实参值的准备和函数执行结果的显示，并给出适当的操作提示显示。附录 A 提 供了简易菜单的框架。

2

华中科技大学计算机学院数据结构实验报告

演示系统可选择实现线性表的文件形式保存。其中，①需要设计文件数据记 录格式，以高效保存线性表数据逻辑结构(D,{R})的完整信息；②需要设计线性 表文件保存和加载操作合理模式。附录 B 提供了文件存取的方法。演示系统可选择实现多个线性表管理。

1.2系统设计

1.2.1 数据物理结构

线性表的数据物理结构如下：

typedef struct { //顺序表（顺序结构）的定义 ElemType *elem; //定义整型指针，为存储空间基址

int length; //线性表的长度

int listsize; //当前分配的存储容量(以 sizeof(ElemType)为单位) }SqList;

要实现同时对多个线性表管理，只需要定义一个结构数组即可。

1.2.2演示系统

将菜单演示和用户选择写入到while循环中，用OP获取用户的选择，OP初始化为1，以便第一次能进入循环。进入循环后系统首先显示功能菜单，然后用户输入选择0-14，其中1-14分别代表线性表的一个基本运算，在主函数中通过SWITCH语句对应到相应的函数功能，执行完该功能后BREAK跳出SWITCH语句，继续执行while循环，直至用户输入0退出当前演示系统。在第一次进入循环while时首先会询问用户对哪个线性表进行操作，直至退出演示系统之前一直对指定线性表进行操作。演示系统结构如图1-1.

3

华中科技大学计算机学院数据结构实验报告

1.2.3 运算算法思想与设计

线性表运算算法思想与设计如下：

1. 初始化线性表思想：将线性表初始化过程写成函数，其中传入函数的参数是主函数中定义的结构型变量L的引用，在函数中，首先使用malloc函数分配LISTSIZE大小的连续内存空间，并将首地址返回赋值给L.elem，由于线性表的长度为0，将L.length初始化为0，即完成了线性表的初始化。经分析，算法的时间复杂度为O(1)。

2. 销毁线性表思想：将销毁线性表的过程写成函数，其中传入函数是主函数中定义的结构性变量L。在函数中，首先使用free函数释放掉以L.elem为首地址的连续内存空间，再将L.length,L.listsize重新赋值为0。 经分析，该算法的时间复杂度为O(1)。

3. 清空线性表的思想：将清空表的过程写成函数，其中将主函数中定义的结构性变量L的引用作为函数参数，在函数中，由于清空操作并不释放内存空间，故只需将线性表的长度置为0即可。经分许，该算法的时间复杂度为O(1)。

4. 求线性表表长的思想：将求表长过程写成函数，其中主函数中定义的结构性变量L的引用作为函数的参数，在函数中，直接返回L.length即为所求线性表的表长。经分析，该算法的时间复杂度为O（1）。

5. 获得元素的算法思想：将获得线性表元素写成函数，其中函数的参数是结构型变量L以及数据元素的序号i，由于采取的是线性存储结构，故直接通过访问数组的方式即L.elem[i-1]来获取元素，当然，在这之前需要

4

华中科技大学计算机学院数据结构实验报告

判断合法性。经分析，该算法的时间复杂度为O（1）。

6. 查找元素的算法思想：将查找线性表特定值的数据元素写成函数，其中函数的参数是主函数中定义的结构类型变量L以及查找的数据元素的值，通过循环对线性表中的每一个元素与给定值比较看是否相等，如果相等就返回该元素的次序。经分析，该算法的时间复杂度为O（n）。查找算法的流程图如图1-2所示。

图1-2线性表查找算法流程图

7. 获得前驱算法思想：将获得前驱过程写成函数，函数的参数是结构体类型变量以及特定数据元素的值，接受前驱的变量作为另一个参数，首先调用获得元素的函数判断该线性表中特定数据元素的位序，首先判断不为1，否则的话返回FALSE，然后直接返回其前一个元素即L.elem[j-2]。经分析，该算法的时间复杂度为O（n）。

8. 获得后继算法思想：将获得后继写成函数，函数的参数是结构体类型变量以及特定数据元素的值。首先判断是否为最后一个元素，如果不是则直接返回其后一个元素，否则的话返回FALSE，同样该算法需要调用获得元素的函数来确定该特定元素在线性表中的次序。经分析，该算法的时间复杂度为O（n）。

9. 插入元素算法思想：将插入函数写成函数，函数的参数是结构型变量以及插入元素的值大小以及插入位置。在函数中，首先判断插入位置的合

5

华中科技大学计算机学院数据结构实验报告

法性，即是否在线性表中合适的位置，其次还要判断当前存储空间是否已满，如果满了的话要malloc函数重新分配空间，插入元素时从该位置起到最后一个元素从后开始以此往后移一个单元。经分析，该算法的时间复杂度为O（n）。该算法的程序流程图如图1-3所示。

图1-3线性表中插入元素算法流程图

10. 删除元素算法思想：将删除线性表中元素写成函数，函数的参数是结构类型变量，首先判断位序的合法性，在之后直接将删除元素位置后一个元素直到最后一个元素以此从前往后向前移动一个单元。经分析，该算法的时间复杂度为O（n）。

11. 遍历线性表算法思想：将遍历线性表写成一个函数，函数的参数是结构

6

华中科技大学计算机学院数据结构实验报告

类型变量，直接用一个循环来对线性表中的每一个元素进行操作。经分析，该算法的时间复杂度为O(n)。

1.3系统实现

1.3.1 编程环境、运行环境、项目工程描述

本次实验采用Microsoft Visual Studio 2015编程软件编写，并用VS2015进行编译运行，项目名称是linear datastructer。 1.3.2 头文件及预定义常量说明 1.头文件

#include #include #include

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 10

3.类型表达式 typedef int status; typedef int ElemType;

1.3.3系统演示操作

1.系统一开始会显示菜单提示用户输入选择对1-99号线性表哪一个进行操作。如图1-4所示。

7

华中科技大学计算机学院数据结构实验报告

图1-4系统演示1

2.选择对线性表1进行操作，进入菜单演示界面，如图1-5所示。

图1-5系统演示2

3.选择退出0，此时会退出当前演示界面，即退出对当前线性表的操作，并显示要求用户选择对哪一个线性表进行操作。如图1-6所示。

8

华中科技大学计算机学院数据结构实验报告

图1-14 查找元素的前驱数据元素

8.执行功能9，确定值为2的数据元素的后继数据元素，测试结果如图1-15所示。

1-15 查找元素的后继数据元素

9.执行功能11，删除第三个数据元素，测试结果如图1-16所示。

14

华中科技大学计算机学院数据结构实验报告

图1-16 删除线性表中的数据元素测试结果

10.执行功能13，保存线性表中的数据元素值到文件名为LY.txt的文件中，测试结果如图1-17所示。

图1-17 保存线性表测试结果

11.清空此时的线性表，在执行功能14，加载线性表，测试结果如图1-18所示。

15

华中科技大学计算机学院数据结构实验报告

图1-18 线性表加载的测试结果

11.执行功能12，遍历并输出线性表中的元素，应该输出1245，测试结果如图1-19所示。

图1-19 遍历输出线性表中元素的测试结果

1.4实验小结

经过本次试验，我充分了解到了线性表的物理结构，并且通过切身的体会熟练掌握了线性表的基本操作，提高了自己写有关线性表的代码的能力，尤其是在写的过程中遇到了许多困难，在多次寻求同学的帮助下终于解决了。还发现了自己的薄弱之处，就是在文件的处理时存在许多纰漏，导致文件读取不成功。并且我还加深了对线性表的存在与空的区别。还有对“&”引用符号的理解，加强了其与“*”的区别，“&e”使得在函数中调用主函数中的值“e”时可以同时更改其值，如在GetElem函数 中调用了“e”的值然后在主函数中输出，如果要更改

16

华中科技大学计算机学院数据结构实验报告

其值的话就必须要用“&”符号。

2 基于二叉链表的二叉树实现

2.1 问题描述

采用二叉链表作为二叉树的物理结构，实现二叉树的基本运算，数据元素的类型名可自行定义。要求构造一个具有菜单的功能演示系统，其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提示。

2.1.1二叉树的基本概念

二叉树是一种树型结构，即n个结点的有限集，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

2.1.2逻辑结构与基本运算

抽象数据类型二叉树的定义如下：

ADT BinaryTree {

数据对象D：D是具有相同特性的数据元素的集合。 数据关系R:

若D=Φ，则R=Φ，称BinaryTree为空二叉树； 若D≠Φ，则R={H},H是如下二元关系：

（1） 在D中存在唯一的成为根的数据元素root，它在关系H中无前

驱；

（2） 若D-{root}≠Φ,则存在D-{root}={D1,Dr},且D1∩Dr=Φ; （3） 若D1≠Φ，则D1中存在唯一的元素X1，∈H，且存在

D1上的关系H1包含于H；若Dr≠Φ,则Dr中存在唯一的元素Xr，∈H,且存在Dr上的关系属于H；

（4） （D，{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr，

17

华中科技大学计算机学院数据结构实验报告

{Hr}）是一棵符合本定义的二叉树，称为根的右子树。

}

依据最小最小完备性和常用性相结合的原则，以函数形式定义了二叉树的初始化、销毁二叉树、创建二叉树、清空二叉树、判定空二叉树和求二叉树深度等20种基本运算，具体运算功能定义如下：

⑴初始化二叉树：函数名称是InitBiTree(T)；初始条件是二叉树T不存在；操作结果是构造空二叉树T。

⑵销毁二叉：树函数名称是DestroyBiTree(T)；初始条件是二叉树T已存在；操作结果是销毁二叉树T。

⑶创建二叉树：函数名称是CreateBiTree(T,definition)；初始条件是definition 给出二叉树T的定义；操作结果是按definition构造二叉树T。

⑷清空二叉树：函数名称是ClearBiTree (T)；初始条件是二叉树T存在；

操作结果是将二叉树T清空。

⑸判定空二叉树：函数名称是BiTreeEmpty(T)；初始条件是二叉树T存在；操作结果是若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中的某个结点；操作结果是若e是T的非根结点，则返回它的双亲结点指针，否则返回NULL。

⑾获得左孩子结点：函数名称是LeftChild(T,e)；初始条件是二叉树T存在，e是T中某个节点；操作结果是返回e的左孩子结点指针。若e无左孩子，则返回NULL。

18

华中科技大学计算机学院数据结构实验报告

⑿获得右孩子结点：函数名称是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 #include 2、预定义常量

（1）函数结果状态宏定义 #define TRUE 1

23

华中科技大学计算机学院数据结构实验报告

#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 5 2.3.3 演示系统操作

1.系统一开始会显示功能菜单并提示用户输入选择。

图2-2 演示系统操作图1

2.输入序号0~20，会执行序号所对应的操作。

24

华中科技大学计算机学院数据结构实验报告

图2-3 演示系统操作图2

3.输入序号0，演示系统结束并退出。

图2-3 演示系统操作图3

2.3.4 测试计划 测试功能及序号 1.InitBiTree 输入函数的参数 无 预计输出 二叉树创建成功 此时二叉树的状态 二叉树根结点指针置为空，未分配具体的存储空间 25

华中科技大学计算机学院数据结构实验报告

2.DestroyBiTree 3.CreateBiTree 无 二叉树销毁失败 依次输入关键字及其对应值： A1 B9 D7 二叉树创建成功 ##E0H1##I2##C9F6##G2#J0## 无 无 无 无 输入关键字为D 输入关键字E 输入关键字为E的结点的值改为9 输入查找关键字为I的结点 二叉树清空成功 二叉树不为空 4.ClearBiTree 5.BiTreeEmpty 6.BiTreeDepth 7.Root 8.Value 9.Assign 10.Parent 二叉树头指针置为空，对应的存储空间被释放 按照输入关键字的先序序列创建二叉树，每个结点赋值 二叉树根结点保留，但其左右指针域置为空 同上3 二叉树的深度为4 同上3 二叉树的根结点关 键字为A 同上3 输出关键字为D的 结点值为7 同上3 输出关键字为E的 结点的值已改为9 同上3 同上3 同上3 同上3 同上3 同上3 同上3 同上3 输出关键字为I的结点的双亲结点为E 输出关键字为E的11.LeftChild(测试1) 输入查找关键字为E的结点 结点的左孩子为H 输出关键字为F的12.LeftChild（测试2） 输入查找关键字为F的结点 左孩子不存在，查找失败 输出关键字为B的13.RightChild（测试输入查找关键字为B的结点 结点右孩子为E 1） 输出关键字为F的14.RightChild（测试输入查找关键字为F的结点 右孩子不存在，操2） 作失败 输出关键字为G的15.LeftSibling（测试输入查找关键字为G的结点 结点左孩子为F 1） 输出关键字为B的15.LeftSibling（测试输入查找关键字为B的结点 结点左孩子不存2） 在，操作失败 26

华中科技大学计算机学院数据结构实验报告

16.InsertChild 在原二叉树的基础上，将新生成二叉树作为关键字为J的结点的左子树，J的左子树作为新生成二叉树的右子树 输入查找关键字为E的结点，输出二叉树删除成在上一基础上，17.DeleteChild 输入LR值为1 功 将原二叉树的E结点的右子树删除 输出先序遍历序 18.PreOrderTraverse 无 列：ABDEHICFGJ 同上3 19.InOrderTraverse 无 输出中序遍历序 列：DBHEIAFCGJ 同上3 输出后续遍历序 列：DHIEBFJGCA 同上3 输出层序遍历序 列：ABCDEFGHIJ 同上3 表2-1 测试计划 输入LR值为0，输入查找关 键字为J，新生成右子树为空输出二叉树插入成的二叉树输入：M1N2#K3### 功 （字母后为该关键字结点的值） 20.PostOrderTraverse 无 21.LevelTraverse 无

图2-4 按以上测试用例生成的原始二叉树

27

华中科技大学计算机学院数据结构实验报告

2.3.5 测试

1.执行功能1.InitBiTree，测试结果如图2-5所示。

图2-5 初始化二叉树测试

2.执行功能3，创建二叉树，测试结果如图2-6所示。

图2-6 二叉树创建

3.在上一步的基础上对二叉树的结构进行验证，根据其前序遍历、中序遍历、后续遍历的结果是否与预期一致判断结构是否正确。执行功能17，先序遍历二叉树，并执行PRINT操作，测试结果如图2-7所示。

28

华中科技大学计算机学院数据结构实验报告

图2-7 先序遍历二叉树的测试结果

4.执行功能18，中序遍历二叉树，并执行PRINT操作，测试结果如图2-8所示。

图2-8 中序遍历二叉树的测试结果 5.执行功能19，后序遍历二叉树，测试结果如图2-9所示。

29

华中科技大学计算机学院数据结构实验报告

图2-9 后序遍历二叉树的测试结果

6.执行功能20，层序遍历二叉树，测试结果如图2-10所示。

图2-10 层序遍历二叉树的测试结果

上述测试与预期的遍历结果是一致的，说明生成二叉树的结构正确性，即生成了如图2-4所示的二叉树。

7.执行功能5，判断二叉树是否为空树，测试结果如图2-11所示。

30

华中科技大学计算机学院数据结构实验报告

图2-11 判断二叉树是否为空测试结果

8.执行功能6，求二叉树的深度，测试结果如图2-12所示。

图2-12 求二叉树深度测试结果

9.执行功能7，求二叉树的根结点，测试结果如图2-13所示。

31

华中科技大学计算机学院数据结构实验报告

图2-13 求二叉树根结点的测试结果

10.执行功能8，求关键字为D的结点的值，测试结果如图2-14所示。

图2-14 求二叉树指定结点的值测试结果

11.执行功能9，将关键字为E的结点值改为9，测试结果如图2-15所示。

32

华中科技大学计算机学院数据结构实验报告

图2-15 对指定结点重新赋值测试结果

12.执行功能11，输入查找关键字为E的结点的左孩子，测试结果如图2-16所示。

图2-16 查找左孩子的测试结果1

13.执行功能11，测试关键字为F的结点的左孩子，测试结果如图2-17所示。

33

华中科技大学计算机学院数据结构实验报告

图2-17 查找左孩子的测试结果2

14.执行功能10，查找关键字为I的结点的双亲结点，测试结果如图2-18所示。

图2-18 查找结点的双亲结点

15.执行功能13，查找关键字为E的结点的左兄弟，查找结果如图2-19所示。

34

华中科技大学计算机学院数据结构实验报告

图2-19 查找结点的左兄弟测试结果1

16.执行功能13，查找关键字为B的结点的左兄弟，查找结果如图2-20所示。

图2-20 查找结点的左兄弟测试结果2

17.执行功能15，在原二叉树的基础上插入子树，测试结果如图2-21所示。

35

华中科技大学计算机学院数据结构实验报告

图2-21插入子树的测试结果

插入子树后，先序遍历得到的序列为：ABDEHICFGJMNK,层序遍历得到的序列应该为：ABCDEFGHIJMNK，中序遍历得到的序列为：DBHEIAFCGNKMJ。通过遍历新生成的二叉树验证其结构正确性。

图2-22 先序遍历的测试结果

36

华中科技大学计算机学院数据结构实验报告

图2-23 层序遍历的测试结果

图2-24 后序遍历的测试结果

以上遍历结果与预期相吻合，说明插入后得到的新二叉树满足结构正确性。 18.执行功能16，删除关键字为E的结点的右子树，即I结点，测试结果如图2-25所示。

37

华中科技大学计算机学院数据结构实验报告

图2-25 删除子树的测试结果

未验证结果的正确性，若对其先序遍历得到的序列应该为：ABDEHCFGJMNK，层序遍历得到的序列应该为：ABCDEFGHJMNK，中序遍历得到的结果应该为：DBHEAFCGNKMJ

图2-26 先序遍历的测试结果

38

本文来源：https://www.bwwdw.com/article/5x37.html