胡学钢数据结构实验三

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