数据结构实验指导课件.ppt

《数据结构实验指导课件.ppt》由会员分享，可在线阅读，更多相关《数据结构实验指导课件.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室数据结构实验指导课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验实验目的实验目的o实验目的和任务实验目的和任务n、目的、目的(1)掌握二叉树的动态链表存储结构及表示。掌握二叉树的动态链表存储结构及表示。(2)掌握二叉树的三种遍历算法（递归和非递归两类）。掌握二叉树的三种遍历算法（递

2、归和非递归两类）。(3)运用二叉树三种遍历的方法求解有关问题。运用二叉树三种遍历的方法求解有关问题。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验实验任务实验任务o2、实验任务、实验任务n说明说明1：为使实验程序简洁直观，下面的部分实验程序中：为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序的一些功能实现仍以调用库函数程序btrechar.h中的函中的函数的形式给出，并假设该库函数中定义了二叉树指针和结数的形式给出，并假设该库函数中定义了二叉树指针和结点类型分别为点类型分别为bitre和和bnode，以及部

3、分常用运算，例如构，以及部分常用运算，例如构建二叉树、以某种方式显示二叉树等。各运算的名称较为建二叉树、以某种方式显示二叉树等。各运算的名称较为直观，因而易于理解。读者可自行设计自己的库函数，也直观，因而易于理解。读者可自行设计自己的库函数，也可到作者的网站下载。可到作者的网站下载。n说明说明2：为便于数据的描述，将测试数据结构列出，并以：为便于数据的描述，将测试数据结构列出，并以一个文件名的形式给出标注，例如测试数据名为一个文件名的形式给出标注，例如测试数据名为full41.cbt的二叉树，其具体结构形式参见二叉树列表中的标有的二叉树，其具体结构形式参见二叉树列表中的标有full41.cbt

4、的二叉树。的二叉树。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验实验任务续实验任务续1编写算法实现下列问题的求解编写算法实现下列问题的求解。o求二叉树的高度。求二叉树的高度。实验测试数据基本要求：实验测试数据基本要求：第一组数据：第一组数据：full41.cbt第二组数据：第二组数据：cbitre.cbto设计算法按中序次序输出二叉树中各结点的值及设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。其所对应的层次数。实验测试数据基本要求：实验测试数据基本要求：第一组数据：第一组数据：full41.cbt第二组数据：第二组数

5、据：cbitre.cbt合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验实验任务续实验任务续2编写算法实现下列问题的求解编写算法实现下列问题的求解。o将按顺序方式存储在数组中的二叉树转换为将按顺序方式存储在数组中的二叉树转换为二叉链表形式。二叉链表形式。实验测试数据基本要求：实验测试数据基本要求：n第一组数据：第一组数据：full41.cbtn第二组数据：第二组数据：letter.cbto复制一棵二叉树复制一棵二叉树T到到T1。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验

6、实验任务续实验任务续3编写算法实现下列问题的求解编写算法实现下列问题的求解。o交换二叉树中每个结点的左右孩子指针的值。交换二叉树中每个结点的左右孩子指针的值。实验测试数据基本要求：实验测试数据基本要求：n第一组数据：第一组数据：full41.cbtn第二组数据：第二组数据：cbitre.cbto设计算法以实现下面所提到以扩展二叉树的先序设计算法以实现下面所提到以扩展二叉树的先序序列作为输入构建二叉树的功能。序列作为输入构建二叉树的功能。实验测试数据基本要求：实验测试数据基本要求：n第一组数据：第一组数据：full41.cbtn第二组数据：第二组数据：cbitre.cbt合肥工业大学合肥工业大学

7、 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验实验数据实验数据o另外，为便于初学者的实验，以及提高实验另外，为便于初学者的实验，以及提高实验的效率，提供了多个这种形式的结构文件，的效率，提供了多个这种形式的结构文件，文件名就是所给出的标注，实验时可以按照文件名就是所给出的标注，实验时可以按照实验例程中的调用形式调用就可以构造出所实验例程中的调用形式调用就可以构造出所需要的结构了。读者也可以自己编写函数来需要的结构了。读者也可以自己编写函数来读取文件中所存储的结构信息构造出二叉树读取文件中所存储的结构信息构造出二叉树（构造所用的基本方法参见后面的讨论）。（构

8、造所用的基本方法参见后面的讨论）。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验 实验数据实验数据full41.cbt合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验 实验数据实验数据full42.cbt合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验 实验数据实验数据cbitre.cbt合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验 实验数据实验数据t

9、bt1.cbt合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验 实验数据实验数据bitre.cbt合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验 实验数据实验数据cbtr1.cbt合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验 实验数据实验数据letter.cbt合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验 实验数据实验数据full5.cbt合肥工业

10、大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验简要说明简要说明为了完成针对特定问题和要求的二叉树的算法的实验，通常为了完成针对特定问题和要求的二叉树的算法的实验，通常需要完成以下工作：需要完成以下工作：（1）设计或选择合适的存储结构。在许多情况下可能是指定）设计或选择合适的存储结构。在许多情况下可能是指定一种存储结构，就二叉树来说，一般默认为或者是较多地一种存储结构，就二叉树来说，一般默认为或者是较多地采用二叉链表存储结构。具体结构的设计可参考教科书。采用二叉链表存储结构。具体结构的设计可参考教科书。（2）设计出针对所选择的结构的算法。）设

11、计出针对所选择的结构的算法。（3）构造一棵（或者多棵，为了能充分地实验，应该分别构）构造一棵（或者多棵，为了能充分地实验，应该分别构建多棵）二叉树以作为算法运行时的数据。为达到有效检建多棵）二叉树以作为算法运行时的数据。为达到有效检验算法的目的，一般要求所构造的二叉树要尽可能多地包验算法的目的，一般要求所构造的二叉树要尽可能多地包含多种情况，要有一定的复杂度，否则难以达到预定的目含多种情况，要有一定的复杂度，否则难以达到预定的目标。标。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验简要说明简要说明(续续)o（4）运行算法以验证和检查

12、算法的功能，发现存在的问）运行算法以验证和检查算法的功能，发现存在的问题，并予以纠正。在这一环节要注意：题，并予以纠正。在这一环节要注意：n一般来说，对实际数据运行算法（或程序）不能替代一般来说，对实际数据运行算法（或程序）不能替代正确性证明，某次运行成功不能说明算法一定正确。正确性证明，某次运行成功不能说明算法一定正确。反之，若对某次运行不成功，则说明算法有错误或遗反之，若对某次运行不成功，则说明算法有错误或遗漏。由于初学者在算法设计中难免的不完备性或理解漏。由于初学者在算法设计中难免的不完备性或理解的局限性，使得算法中存在不同程度的问题。通过对的局限性，使得算法中存在不同程度的问题。通过对

13、具有一定复杂程度的实际数据的运行可有效发现存在具有一定复杂程度的实际数据的运行可有效发现存在的这些问题，提高学习的效果。因此，要注意算法运的这些问题，提高学习的效果。因此，要注意算法运行的充分性，通过多种情况反复检查。行的充分性，通过多种情况反复检查。合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验基础部分的讨论基础部分的讨论 o1、二叉树的存储结构、二叉树的存储结构o2、建立二叉树的算法、建立二叉树的算法n提出一种以二叉树的扩展二叉树的先序序列作为输入提出一种以二叉树的扩展二叉树的先序序列作为输入建立二叉树的方法建立二叉树的方法 n

14、扩展二叉树扩展二叉树：将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.”标识其为空。称这样处理后的二叉树为原二叉树的扩展二叉树扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树。o3、二叉树结构的检验、二叉树结构的检验合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验基础部分的讨论基础部分的讨论o例：下面二叉树对应的扩展二叉树如右图所示。例：下面二叉树对应的扩展二叉树如右图所示。扩展先序序列为：ABCDEFGHIJKLABCGFEH

15、IJKDL 。ABCGFEHIJKDL 。(a)二叉树(b)扩展二叉树合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验基础部分的讨论基础部分的讨论文件方式存储二叉树：文件方式存储二叉树：可以将二叉树存储到外部文件中，以便反复使用时节省时间。可以将二叉树存储到外部文件中，以便反复使用时节省时间。同样需要注意两者之间的对应，不可造成不对应。同样需要注意两者之间的对应，不可造成不对应。例下面二叉树及其对应的文本文件。Bitre 0A 0 0B 1 0C 1 0D 1 1E 1 0F 1 0G 1 1ABCGFED合肥工业大学合肥工业大学 人

16、工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验基础部分的讨论基础部分的讨论o 存储规则如下所示。bitrebitre 0 01 0 01 0 02 0 02 0 03 0 03 0 05 1 15 1 16 1 16 1 17 1 07 1 08 1 18 1 19 1 19 1 1固定标志每一行对应一个结点每一行对应一个结点,结点按先序次序排列，结点按先序次序排列，三个值分别对应：三个值分别对应：(1)(1)结点的值结点的值(2)(2)左孩子标志左孩子标志(3)(3)右孩子标志右孩子标志 0 0：有孩子，：有孩子，1 1：无孩子：无孩子 1 2 3 5 6 7 8 9 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室实验三实验三 二叉树实验二叉树实验基础部分的讨论基础部分的讨论如何检验二叉树构造是否正确成功？输出扩展二叉树序列 输出三种序 图形化显示树（工具实现）合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室谢谢！谢谢！