合肥工业大学数据结构实验课件实验三 二叉树实验.ppt

数据结构实验指导 （实验三 二叉树实验） 胡学钢 张晶 合肥工业大学计算机与信息学院 (Jsjxhuxg@hfut.edu.cn) 2009年3月 实验三 二叉树实验——实验目的 实验目的和任务 １、目的 (1)掌握二叉树的动态链表存储结构及表示。 (2)掌握二叉树的三种遍历算法（递归和非递归两类）。 (3)运用二叉树三种遍历的方法求解有关问题。 实验三 二叉树实验——实验任务 2、实验任务 说明1：为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序btrechar.h中的函数的形式给出，并假设该库函数中定义了二叉树指针和结点类型分别为bitre和bnode，以及部分常用运算，例如构建二叉树、以某种方式显示二叉树等。各运算的名称较为直观，因而易于理解。读者可自行设计自己的库函数，也可到作者的网站下载。 说明2：为便于数据的描述，将测试数据结构列出，并以一个文件名的形式给出标注，例如测试数据名为full41.cbt的二叉树，其具体结构形式参见二叉树列表中的标有full41.cbt的二叉树。 实验三 二叉树实验——实验任务续1 编写算法实现下列问题的求解。 1求二叉树的高度。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： cbitre.cbt 2设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： cbitre.cbt 实验三 二叉树实验——实验任务续2 编写算法实现下列问题的求解。 3将按顺序方式存储在数组中的二叉树转换为二叉链表形式。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 4复制一棵二叉树T到T1。 实验三 二叉树实验——实验任务续3 编写算法实现下列问题的求解。 5交换二叉树中每个结点的左右孩子指针的值。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： cbitre.cbt 6设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二叉树的功能。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： cbitre.cbt 实验三 二叉树实验——实验数据 另外，为便于初学者的实验，以及提高实验的效率，提供了多个这种形式的结构文件，文件名就是所给出的标注，实验时可以按照实验例程中的调用形式调用就可以构造出所需要的结构了。读者也可以自己编写函数来读取文件中所存储的结构信息构造出二叉树（构造所用的基本方法参见后面的讨论）。 实验三 二叉树实验 ——实验数据full41.cbt 实验三 二叉树实验 ——实验数据full42.cbt 实验三 二叉树实验 ——实验数据cbitre.cbt 实验三 二叉树实验 ——实验数据tbt1.cbt 实验三 二叉树实验 ——实验数据bitre.cbt 实验三 二叉树实验 ——实验数据cbtr1.cbt 实验三 二叉树实验 ——实验数据letter.cbt 实验三 二叉树实验 ——实验数据full5.cbt 实验三 二叉树实验——简要说明 为了完成针对特定问题和要求的二叉树的算法的实验，通常需要完成以下工作： （1）设计或选择合适的存储结构。在许多情况下可能是指定一种存储结构，就二叉树来说，一般默认为或者是较多地采用二叉链表存储结构。具体结构的设计可参考教科书。 （2）设计出针对所选择的结构的算法。 （3）构造一棵（或者多棵，为了能充分地实验，应该分别构建多棵）二叉树以作为算法运行时的数据。为达到有效检验算法的目的，一般要求所构造的二叉树要尽可能多地包含多种情况，要有一定的复杂度，否则难以达到预定的目标。 实验三 二叉树实验——简要说明(续) （4）运行算法以验证和检查算法的功能，发现存在的问题，并予以纠正。在这一环节要注意： 一般来说，对实际数据运行算法（或程序）不能替代正确性证明，某次运行成功不能说明算法一定正确。反之，若对某次运行不成功，则说明算法有错误或遗漏。由于初学者在算法设计中难免的不完备性或理解的局限性，使得算法中存在不同程度的问题。通过对具有一定复杂程度的实际数据的运行可有效发现存在的这些问题，提高学习的效果。因此，要注意算法运行的充分性，通