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

数据结构实验指导 （实验四 线索二叉树实验） 胡学钢 张晶 合肥工业大学计算机与信息学院 (Jsjxhuxg@hfut.edu.cn) 2009年3月 实验四 线索二叉树实验——实验目的 实验目的和任务 １、目的 （1）掌握线索二叉树的有关知识。 （2）掌握求解线索二叉树中结点前趋和后继的算法以及以相应次序遍历线索二叉树的算法。 （3）掌握二叉树的线索化算法的设计。 实验四 线索二叉树实验—实验任务 2、实验任务 说明：线索二叉树是为了快速求解二叉树中结点在指定次序下的前驱和后继，而将二叉链表中空的左右孩子指针分别改为指向其前驱和后继结点而得到的结构，反映了运算对数据结构的设计的影响。因此，首先要了解线索二叉树的结构特点，其中原本为空的指针被修改为前驱和后继指针，使得对左右子树和线索的判断发生了变化。利用线索可以实现某些次序下的前驱和后继。本实验期望能理解线索二叉树的结构特点，实现各前驱和后接算法的求解，并掌握将二叉树转换为线索二叉树的算法，即线索化算法。 说明：为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序btrechar.h中的函数的形式给出，并假设该库函数中定义了线索二叉树的相关功能，如显示线索二叉树等。 实验四 线索二叉树实验—实验任务续1 编写算法实现下列问题的求解。 1按先序次序遍历先序线索二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 2按中序次序遍历中序线索二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验四 线索二叉树实验—实验任务续2 编写算法实现下列问题的求解。 3将值为x的结点作为先序线索二叉树T的左子树的（先序）最后一个结点的右孩子插入进去。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 4按中序次序线索化二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 5按后序次序线索化二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验四 线索二叉树实验—实验数据 另外，为便于初学者的实验，以及提高实验的效率，提供了多个这种形式的结构文件，文件名就是所给出的标注，实验时可以按照实验例程中的调用形式调用就可以构造出所需要的结构了。读者也可以自己编写函数来读取文件中所存储的结构信息构造出二叉树（构造所用的基本方法参见后面的讨论）。 实验四 线索二叉树实验  ——实验数据full41.cbt 实验四 线索二叉树实验  ——实验数据full42.cbt 实验四 线索二叉树实验  ——实验数据cbitre.cbt 实验四 线索二叉树实验  ——实验数据tbt1.cbt 实验四 线索二叉树实验  ——实验数据bitre.cbt 实验四 线索二叉树实验  ——实验数据cbtr1.cbt 实验四 线索二叉树实验  ——实验数据letter.cbt 实验四 线索二叉树实验  ——实验数据full5.cbt 实验四 线索二叉树实验——基础部分的讨论 1、线索二叉树的存储结构 2、线索化的实现 3、线索二叉树结构的检验 * 合肥工业大学 人工智能与数据挖掘研究室 * 合肥工业大学 人工智能与数据挖掘研究室