线索二叉树生成及其遍历

1、数据结构课程设计题目：线索二叉树的生成及其遍历学院：理学院班级：数学13-2班学生 姓名：孙晴、张炳赫、张美娜、董自鹏学生学号： 8、12、13、22指导教师：张太发2014 年12月24日I舒和接次才课程设计任务书姓名X y z s班级设计题目线索二叉树的生成及其遍历理论要点二叉树的遍历本质上是将一个复杂的非线性结构转换为线 性结构，使每个结点都有且仅有一个直接前驱结点和直接后继结 点（第一个结点无前驱，最后一个结点无后继）。但是二叉树中 每个结点在这个序列中的直接前驱结点和直接后继结点是什 么？二叉树的存储结构中并没有反映出来，只能在对一叉树遍历 的动态过程中得到这些信息。为了保留结点在某

2、种遍历序列中直 接前驱喝直接后继的位置信息，有两种方法。一是在结点结构中 增加向前和向后的指针 fwd和bkd,这种方法增加了存储开销， 不可取；二是利用二叉树的二叉链表的那些空指针域来指示。建立线索二叉树，或者说对二叉树线索化，实质上就是遍历 一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线 索。为实现这一过程，设指针 pre始终指向刚刚访问的结点，即 若寸旨针p指向当前结点，则 pre指向它的前驱，以便设线索。另外，在对一颗二叉树加线索时，必须首先申请一个头结点， 建立头结点与二叉树的根结点的指向关系，对二叉树线索化后， 还需建

3、立最后一个结点与头结点之间的线索。中序线索一叉树：若结点的ltag=1 , Ichild 指向其前驱；否则，该结点的前驱是以该结点为根的左子树上按中序遍历的最后一 个结点。若rtag=1 , rchild 指向其后继；否则，该结点的后驱 是以该结点为根的右子树上按中序遍历的第一个结点。设计目标以二叉链表作为存储结构时，只能找到结点的左、右孩子的 信息，而得不到结点的前驱与后继信息，为了使这种信息只有在 遍历的动态过程中才得到。增设两个指针分别指示其前驱结点 和后继结点，并且利用结点的空链域存放（线索链表）。同时为 了tb遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，

4、 右指针p指向当前访问的结点， 则pre 指向它的前驱。由此得到中序遍历建立中序线索化链表的算法预期结果对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的 遍历。小组人员 具体分工? s：报告填写? z：程序设计、运行? V ：答辩? x: ppt设计制作计划与进 步的安排在两周（共10天）内完成课程设计，具体安排如下：1 .查找所需要的相关资料，进行整理；2天2 .系统学习相关理论和算法，设计总体流程；2天3 .编写源代码，上机调试，并进行修改逐步完善代码；3天4 .编写课程设计报告；2天5 .进行后续整理工作。1天目录摘要1题目分析错误！未定义书签。错误！未定义书签。1.1 相关思

5、想及概念介绍 11.2 线索二叉树的结构11.3 需求分析22概要设计 22.1 抽象数据类型的定义32.2 主程序的流程32.3 各程序模块之间的层次（调用）关系53详细设计 64调试分析 105用户使用说明 106测试结果 117课程设计体会 128参考文献 129源程序 13i摘要针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程 中才能得到。增设两个指针分别指示其前驱和后继，并且利用结点的空链域存放（线索链表）。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针 p指向

6、当前访问的结点，则pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树， 实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍 历的效果。关键词：二叉树，中序线索二叉树，中序线索二叉树的遍历II数据结构程序设计1题目分析1.1 相关思想及概念介绍（1）二叉树遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访 问一次且仅被访问一次。遍历二叉树中经常要用到的一种操作。 因为在实际应用问题中，常常需要按 一定顺序对二叉树中的每个结点逐个进行访问， 查找具有某一特点的结点，然后 对这些满足条件的

7、结点进行处理。通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上 的线性序列。也就是说，遍历操作使非线性结构线性化。由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右 子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以 D L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则 二叉树的遍历方式有 6种：DLR LDR LRD DRL RDL和 RLD如果限定先左 后右，则只有前三种方式，即 DLR（先序遍历）、LDR（中序遍历）和LRD （后序 遍历）。（1）线索二叉树按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排

8、列为一个 线性序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点； 除最后一个结点外，每个结点有且仅有一个直接后继结点。但是， 二叉树中每个 结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。这些指向直接前驱结点和指 向直接后继结点的指针被称为线索，借了线索的二叉树成为线索二叉树。线索二叉树将为二叉树的遍历提供许多方便。1.2 线索二叉树的结构1、n个结点有n-1个前驱和n-1个后继；一共有2n个链域，其中：n+1个 空链域，n-1个指针域；因

9、此，可以用空链域来存放结点的前驱和后继。线索二 叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。2、线索：有效利用二叉链表中空的存储空间，指定原有的孩子指针为空的 域来存放指向前驱和后继的信息，这样的指针被称为“线索”。加线索的过程称 为线索化，由此得到的二叉树称作线索二叉树。若结点有左子树，则左链域Ichild 指示其左孩子（ltag=0 ）;否则，令左 链域指示其前驱（ltag=1 ）;若结点有右子树，则右链域rchild指示其右孩子（rtag=0 ）；否则，令右 链域指示其后继（rtag=1 ）；增设一个头结点，令其Ichild 指向二叉树的根结点，ltag=0、rtag=1

10、 ；并 将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；最后用头指针指示该头结点。其rchild 域的指针指向中序遍历时访问的最后一个结点；反 之，令二叉树中序序列中的第一个结点的Ichild 域指针和最后一个结点rchild 域的指针均指向头结点，这好比为二叉树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。3、例子：如下图a示的二叉树，其中序线索二叉树为图 b所示：1.3 需求分析以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而 得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中 才能得到。增设两个指针

11、分别指示其前驱和后继，并且利用结点的空链域 存放（线索链表）。同时为了记下遍历过程中访问结点的先后关系，附设 一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点,则pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍 历的效果。主要任务：1 .建立二叉树；2 .将二叉树进行中序线索化；3 .编写程序，运行并修改；4 .利用中序线索遍历二叉树5 .书写课程设计论文并将所编写的程序完善2概要设计2.1 抽象数据类型的定义二叉树的存储结构数据域

12、左标志域 右标志域 左指针域 右指针域struct node ElemenType data; /int Itag;/int rtag;/struct node *lchild;/struct node *rchild;/BTree;2.2 主程序的流程-4 -数据结构程序设计2.3各程序模块之间的层次（调用）关Y二叉树丞此结点结束数据结构程序设计3详细设计(一)算法的c语言实现#include "stdio.h"#include "stdlib.h"#define OK 1typedef char TElemType;typedef int Statu

13、s;typedef enum PointerTag Link,Thread;link=0:pointer,Thread=1:threadtypedef struct BiThrNode TElemType data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;BiThrTree pre; /全局变量，始终指向刚刚访问过的结点void InThreading(BiThrTree p) if(p)InThreading(p->lchild);左子树线索化if(!p->lchild)

14、p->LTag=Thread;p->lchild=pre;前驱线索if(!pre->rchild)pre->RTag=Thread;pre->rchild=p;后续线索pre=p; / 保持 pre指向p的前驱 InThreading(p->rchild);/右子树线索化/if/InThreadingStatus InOrderThreading(BiThrTree &Thrt,BiThrTree T) /中序遍历二叉树，并将其中序线索化，Thrt指向头结点 /BiThrTree Thrt;if(!(Thrt=(BiThrTree)malloc(si

15、zeof(BiThrNode) exit(-1);Thrt->LTag=Link;/建立头结点Thrt->RTag=Thread; / 右指针回指Thrt->rchild=Thrt;若二叉树为空，则左指针回指中序遍历进行中序线索化 最后一个结点线索化if(!T) Thrt->rchild=Thrt; / else Thrt->lchild=T; pre=Thrt;InThreading(T); / pre->rchild=Thrt;/ pre->RTag=Thread; Thrt->rchild=pre;return OK;InOrderThre

16、adingStatus InOrderTraverse_Thr(BiThrTree T)/T指向头结点，头结点的左链lchild指向根结点，非递归算法BiThrTree p;p=T->lchild;while(p!=T) /空树或遍历结束时，T= = pwhile(p->LTag=Link) p=p->lchild;printf("%cn",p->data); /访问其左子树为空的结点while(p->RTag=Thread&&p->rchild!=T)p=p->rchild;printf("%cn&quo

17、t;,p->data); /访问后续结点/whilep=p->rchild;/whilereturn OK;/InOrderT_ThrStatus CreateBitree(BiThrTree &T)/按先序次序输入二叉树char ch,enter;scanf("%c%c",&ch,&enter);if(ch=' ') T=NULL;elseif(!(T=(BiThrTree)malloc(sizeof(BiThrNode) exit(1);T->data=ch;CreateBitree(T->lchild);

18、CreateBitree(T->rchild);/elsereturn OK;/CreateBitreeint main()BiThrTree T,Thrt;CreateBitree(T);/ 创建InOrderThreading(Thrt,T);/ 线索化InOrderTraverse_Thr(Thrt);/遍历访问return OK;注意点：在输入字符创立二叉树时，要注意叶子结点的输入形式，即叶子结 点的左右空指针也要输入，在我们这里输入空格。(二)建立中序二叉树的递归算法，其中 pre为全局变量。BiThrNodeType *pre;BiThrTree InOrderThr(BiT

19、hrTree T) /*中序遍历二叉树T,并将其中序线索化，pre为全局变量*/BiThrTree head;head=(BitThrNodeType *) malloc (sizeof (BiThrType) ) ;/* 设申请建立头结点*/头结点成功*/head->ltag=0;head->rtag=1;/*head->rchild=head;/*右指针回指 */if( ! T)head->lchild=head;/*若二叉树为空，则左指针回指 */elsehead->lchild=T;pre=head;InThreading(T);/*中序遍历进行中序线索化

20、*/pre->rchild=head;pre->rtag=1;/*最后一个结点线索化*/head->rchild=pre;；return head;void InThreading(BiThrTree p)/*通过中序遍历进行中序线索化*/if(p)InThreading(p->lchild);/* 左子树线索化 */if(p->lchild= NULL* 前驱线索 */p->ltag=1;p->lchild=pre;if(p->rchild=NULL)p->rtag=1;/*后驱线索 */if(pre!=NULL && p

21、re->rtag=1) pre->rchild=p;pre=p;InThreading(p->rchild);/*右子树线索化 */进行中序线索化的算法：bithptr*pre; /*全程变量 */voidINTHREAD(bithptr *p)if(p!=NULL) INTHREAD(p->lchild); /* 左子树线索化 */ if(p->lchild=NULL) p->ltag=1;p->lchild=pre; if(p->rchild=NULL) p->rtag=1;if(pre!=NULL && pre->

22、;rtag=1)pre->rchild=p;pre=p; /*前驱指向当前结点*/INTHREAD(p->rchild); /*右子树线索化 */4调试分析该程序在调试过程中遇到的问题是： 对已学知识运用能力欠缺，尤其是在编 程方面，由于c语言等计算机基础课程知识没有很好的掌握同时在学习数据结构 时也没有真正弄懂导致编程时小错误不断， 而且在遇到许多小的错误时靠自己很 难再调整过来，但整体上是一次对所学知识的运用巩固，特别是对二叉树的建立 以及对它进行线索方面，翻阅大量的书籍及搜集资料并求教于计算机系的同学， 才找到一些解决问题的方法，在用中序遍历线索二叉树时总是搞混不过也因此让

23、我对前序，中序，后序遍历更加理解。同时，在经历了很多次修改重写课程设计 报告的悲惨经历后，懂得了很多关于办公软件方面的知识尤其是自己做的东西一 定要保存并备份。主要出现了两方面问题：A.语法错误（经过多次调试发现有一处缺少了引号）B.逻辑错误。声明一个指针只是在内存中开辟了一个这种数据类型的空间，并让这个指针指向它，由于它还没有指向任何变量，因此不能引用其指向的任何 成员。5用户使用使用该程序时在打开程序的主界面后， 输入相应要求的输入形式，然后就输 出中序遍历，方便简洁。例如：运行时，分别输入（前序输入）：1 2 3 0 0 4 0 5 0 0 6 0 0建立如下所示的二叉树:-10 -数据

24、结构程序设计5中序遍历输出：3 245166测试结果运行时，分别输入（前序输入）：1 2 3 0 0 4 0 5 0 0 6 0 0建立如下所示的二叉树：126345中序遍历输出：3 24516数据结构程序设计7结论体会在这次的课程设计中，我们明白了理论和实际还是相差很大的， 理论知识能 学明白单不代表程序就能编出来， 大多数情况下，我们还是不具备完成这项项目 的能力的。它需要我们不仅能够将以前学过的知识与现学的知识融会贯通同时还 要求我们学会怎样如何整合做项目所需要的全部知识以及对为学知识的查询及 自学能力。更重要的时它还要求我们敢于实践勤于动手，遇到有些不会处理的， 我们会上网去查，或者去

25、问老师，或者去问同学。例如以前我们对二叉树的相关 内容并不是很熟悉，但经过这次课程设计后现在我们不仅掌握了它们的使用方 法，更重要的是我们学会了如何去学习， 然后快速地应用到我们所需要的项目当 中。同时我们还得到了很多关于本门课程的体会： 在编写程序的过程中，把整个 系统的框架准确的描述出来是非常重要的而且写程序是需要步步为营不然一不 小心就会出错。我们们的c语言老师曾经说过良好的代码风格是成功的一半。例如在写代码时会有大量的小括号，大括号等，老师曾说这些代码在书写时一定要 同时写一对，这样就可以避免丢掉或忘写其中的一个。真的是深有体会啊！还有在编码的过程中需要时常进行修改，如果程序的可读性不

26、强，代码量又庞大的话， 那么对于我们们来说是一件非常不幸的事情，程序反复的改来改去是非常繁琐 的。因此我们们一定要养成良好的书写代码的习惯。总之，通过一次的课程设计，我们不仅对我们所设计的内容有了更深的了解 同时这门课程的知识掌握也更加牢固了， 而且还学到很多关于办公软件方面的知 识更重要的是通过和计算机方面的老师和同学的交流了解到了很多关于计算机 方面及计算机相关工作的一些知识这位我们在选方向时提供了很珍贵的意见。总而言之这次收获颇多！8参考文献1 .严蔚敏，吴伟民.数据结构C语言版：清华大学出版社，20092 .谭浩强著.C程序设计（第三版）.北京：清华大学出版社，20053 .于海英，王

27、国权编著的C语言程序设计.清华大学出版社2012年版4 .备注：还有一些是通过查找网站内容搜索整理的。9源程序#include <stdio.h>#include <malloc.h>/指针标志定义结点元素全局变量，用于二叉树的线索按前序输入建立二叉树typedef enumLink,Thread PointerTag;typedef int DataType;typedef struct BiThreTree /PointerTag LTag,RTag;DataType data;struct BiThreTree *lchild,*rchild; BiThreTre

28、e;BiThreTree *pre;/化 BiThreTree *CreateTree() / BiThreTree *T;DataType e; scanf("%d",&e);if(e=0)T=NULL;elseT=(BiThreTree *)malloczeof(BiThreTree);T->data=e;T->LTag=Link; /初始化时指针标志均为 LinkT->RTag=Link;T->lchild=CreateTree();T->rchild=CreateTree();return T;void InThread(BiThreTree *T)BiThreTree *p;P=