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