华中科技大学计算机学院数据结构实验报告
图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，
D1上的关系H1包含于H；若Dr≠Φ,则Dr中存在唯一的元素Xr，
（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