线索二叉树生成及其遍历

《线索二叉树生成及其遍历》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、.数据结构课程设计题目:线索二叉树的生成及其遍历学院：理学院班级：数学13-2班学生姓名：孙晴、张炳赫、张美娜、董自鹏学生学号：8、12、13、22指导教师：张太发2014年12月24日..课程设计任务书姓名Xyzs班级设计题目线索二叉树的生成及其遍历理论要点二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有且仅有一个直接前驱结点和直接后继结点（第一个结点无前驱，最后一个结点无后继）。但是二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么？二叉树的存储结构中并没有

2、反映出来，只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中直接前驱喝直接后继的位置信息，有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；二是利用二叉树的二叉链表的那些空指针域来指示。建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左,右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pr

3、e指向它的前驱，以便设线索。另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。中序线索二叉树：若结点的ltag=1，lchild指向其前驱；否则，该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。若rtag=1，rchild指向其后继；否则，该结点的后驱是以该结点为根的右子树上按中序遍历的第一个结点。设计目标以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后

4、继信息，为了使这种信息只有在遍历的动态过程中才能得到。增设两个指针分别指示其前驱结点和后继结点，并且利用结点的空链域存放（线索链表）。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法预期结果对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历。小组人员具体分工•s：报告填写•z：程序设计、运行•y：答辩•x：ppt设计制作..计划与进步的安排在两周（共10天）内

5、完成课程设计，具体安排如下：1.查找所需要的相关资料，进行整理；2天2.系统学习相关理论和算法，设计总体流程；2天3.编写源代码，上机调试，并进行修改逐步完善代码；3天4.编写课程设计报告；2天5.进行后续整理工作。1天..目录摘要I1题目分析11.1相关思想及概念介绍.......................................11.2线索二叉树的结构.........................................11.3需求分析................

6、.................................22　概要设计22.1抽象数据类型的定义.......................................32.2主程序的流程.............................................32.3各程序模块之间的层次(调用)关系............................53　详细设计64　调试分析105　用户使用说明106测试结果117　课程设计体会128参考文献129源程序13

7、..摘要针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。增设两个指针分别指示其前驱和后继，并且利用结点的空链域存放（线索链表）。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利

8、用中序线索实现对二叉树的遍历的效果。关键词：二叉树，中序线索二叉树，中序线索二叉树的遍历..1题目分析1.1相关思想及概念介绍（1）二叉树遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。遍历二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍