1、 数据结构课程设计数据结构课程设计 题题 目目: : 线索二叉树的生成及其遍历线索二叉树的生成及其遍历 学学 院：院： 班班 级：级： 学学 生生 姓姓 名：名： 学学 生生 学学 号：号： 指指 导导 教教 师：师： 2012 2012 年年 1212 月月 5 5 日日 课程设计任务书课程设计任务书 姓名 班级 学号 设计题目 线索二叉树的生成及其遍历 理论要点 二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构， 使 每个结点都有了唯一前驱和后继（第一个结点无前驱， 最后一个结点无后 继） 。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只 有在遍历中得到。为了容易找到前
2、驱和后继，有两种方法。一是在结点结 构中增加向前和向后的指针 fwd 和 bkd，这种方法增加了存储开销，不可 取；二是利用二叉树的空链指针。 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历 一颗二叉树。在遍历过程中，访问结点的操作是检查当前的左， 右指针域是否为空，将它们改为指向前驱结点或后续结点的线 索。为实现这一过程，设指针 pre 始终指向刚刚访问的结点，即 若指针 p 指向当前结点，则 pre 指向它的前驱，以便设线索。 另外，在对一颗二叉树加线索时，必须首先申请一个头结点， 建立头结点与二叉树的根结点的指向关系，对二叉树线索化后， 还需建立最后一个结点与头结点之间的线索。 中
3、序线索二叉树：若结点的 ltag=1，lchild 指向其前驱；否则，该结点 的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。若 rtag=1，rchild 指向其后继；否则，该结点的后驱是以该结点为根的右子 树上按中序遍历的第一个结点。 设计目标 以二叉链表作为存储结构时，只能找到结点的左、右孩子的 信息，而得不到结点的前驱与后继信息，为了使这种信息只有在 遍历的动态过程中才能得到。增设两个指针分别指示其前驱和后 继，但会使得结构的存储密度降低；并且利用结点的空链域存放 （线索链表），方便。同时为了记下遍历过程中访问结点的先后 关系，附设一个指针 pre 始终指向刚刚访问过的结点，若
4、指针 p 指向当前访问的结点，则 pre 指向它的前驱。由此得到中序遍历 建立中序线索化链表的算法 研究方法 步骤 遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列， 其实质是对一个非线性结构进行线性化操作，使每个结点（除第一个 和最后一个外）有且仅有一个直接前驱和直接后继。以二叉链表作为 存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前 驱与后继信息，这种信息只有在遍历的动态过程中才能得到。因此采 用将二叉树线索化。主要步骤如下： 第一步 建立二叉树； 第二步 实现二叉树的中序线索化； 第三步 实现中序线索二叉树的遍历。 预期结果 对已生成的二叉树进行中序线索化并利用中序线
5、索实现对二叉树的遍历。 计划与进 步的安排 1，整理思路，查找资料； 2，建立二叉树； 3，将二叉树进行中序线索化； 4，编写程序，运行并修改； 5， 利用中序线索遍历二叉树 6， 书写课程设计论文； 7， 将所编写的程序完善，填写所有的表格； 8， 提交论文。 I 摘要摘要 针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息， 而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程 中才能得到。增设两个指针分别指示其前驱和后继，但会使得结构的存储 密度降低；并且利用结点的空链域存放（线索链表），方便。同时为了记 下遍历过程中访问结点的先后关系，附设一个指针 pre 始终指
6、向刚刚访问 过的结点，若指针 p 指向当前访问的结点，则 pre 指向它的前驱。由此得 到中序遍历建立中序线索化链表的算法 本文通过建立二叉树， 实现二叉树的中序线索化并实现中序线索二叉树的遍历。实 现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。 关键词关键词 二叉树，中序线索二叉树，中序线索二叉树的遍历 II 目录 摘要 . 错误错误! !未定义书签。未定义书签。 第一章,需求分析 错误错误! !未定义书签。未定义书签。 第二章,概要设计 .1 第三章,详细设计2 第四章,调试分析5 第五章,用户使用说明 .5 第六章,测试结果 .5 第七章,绪论 .6 第八章,附录参考文献7 数据结构课程设计 - 1 - 线索二叉树的生成及其遍历 第一章 需求分析 以二叉
