数据结构课程设计题目: 线索二叉树的生成及其遍历学院：理学院班级：数学13-2班学生姓名：孙晴、张炳赫、张美娜、董自鹏学生学号： 8、12、13、22 指导教师：张太发2014 年 12月 24日课程设计任务书目录摘要................................. 错误!未定义书签。
1 题目分析.......................... 错误!未定义书签。
1.1相关思想及概念介绍 (1)1.2线索二叉树的结构 (1)1.3需求分析 (2)2 概要设计 (2)2.1抽象数据类型的定义 (3)2.2主程序的流程 (3)2.3各程序模块之间的层次(调用)关系 (5)3 详细设计 (6)4 调试分析 (10)5 用户使用说明 (10)6 测试结果 (11)7 课程设计体会 (12)8 参考文献 (12)9 源程序 (13)摘要针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。
增设两个指针分别指示其前驱和后继，并且利用结点的空链域存放（线索链表）。
同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针 p 指向当前访问的结点，则 pre指向它的前驱。
由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。
实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。
关键词：二叉树，中序线索二叉树，中序线索二叉树的遍历1 题目分析1.1 相关思想及概念介绍（1）二叉树遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
遍历二叉树中经常要用到的一种操作。
因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。
通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。
也就是说，遍历操作使非线性结构线性化。
由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。
因此，只要依次遍历这三部分，就可以遍历整个二叉树。
若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有6种：DLR、LDR、LRD、DRL、RDL、和RLD。
如果限定先左后右，则只有前三种方式，即DLR（先序遍历）、LDR（中序遍历）和LRD（后序遍历）。
（1）线索二叉树按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。
在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。
但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。
这些指向直接前驱结点和指向直接后继结点的指针被称为线索，借了线索的二叉树成为线索二叉树。
线索二叉树将为二叉树的遍历提供许多方便。
1.2 线索二叉树的结构1、n个结点有n-1个前驱和n-1个后继；一共有2n个链域，其中：n+1个空链域，n-1个指针域；因此, 可以用空链域来存放结点的前驱和后继。
线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。
2、线索：有效利用二叉链表中空的存储空间，指定原有的孩子指针为空的域来存放指向前驱和后继的信息，这样的指针被称为“线索”。
加线索的过程称为线索化，由此得到的二叉树称作线索二叉树。
若结点有左子树，则左链域lchild指示其左孩子（ltag=0）；否则，令左链域指示其前驱（ltag=1）；若结点有右子树，则右链域rchild指示其右孩子（rtag=0）；否则，令右链域指示其后继（rtag=1）；增设一个头结点，令其lchild指向二叉树的根结点，ltag=0、rtag=1；并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；最后用头指针指示该头结点。
其rchild域的指针指向中序遍历时访问的最后一个结点；反之，令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchild 域的指针均指向头结点，这好比为二叉树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
3、例子：如下图a示的二叉树，其中序线索二叉树为图b所示：1.3 需求分析以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。
增设两个指针分别指示其前驱和后继，并且利用结点的空链域存放（线索链表）。
同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针 p 指向当前访问的结点，则 pre指向它的前驱。
由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。
实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。
主要任务：1.建立二叉树；2.将二叉树进行中序线索化；3.编写程序，运行并修改；4.利用中序线索遍历二叉树5.书写课程设计论文并将所编写的程序完善。
2 概要设计2.1抽象数据类型的定义二叉树的存储结构struct node{ ElemenType data; //数据域int ltag; //左标志域int rtag; //右标志域struct node *lchild; //左指针域struct node *rchild; //右指针域}BTree;2.2主程序的流程3 详细设计（一）算法的C语言实现#include "stdio.h"#include "stdlib.h"#define OK 1typedef char TElemType;typedef int Status;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){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(sizeof(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;}//InOrderThreadingStatus InOrderTraverse_Thr(BiThrTree T){//T指向头结点，头结点的左链lchild指向根结点，非递归算法BiThrTree p;p=T->lchild;while(p!=T) //空树或遍历结束时，T＝＝p{while(p->LTag==Link) p=p->lchild;printf("%c\n",p->data); //访问其左子树为空的结点while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;printf("%c\n",p->data); //访问后续结点}//whilep=p->rchild;}//whilereturn OK;}//InOrderT_ThrStatus CreateBitree(BiThrTree &T){//按先序次序输入二叉树char ch,enter;scanf("%c%c",&ch,&enter);if(ch==' ') T=NULL;else{if(!(T=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(1);T->data=ch;CreateBitree(T->lchild);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(BiThrTree T){ /*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/BiThrTree head;head=(BitThrNodeType *)malloc（sizeof（BiThrType））;/*设申请头结点成功*/head->ltag=0;head->rtag=1;/*建立头结点*/head->rchild=head;/*右指针回指*/if(！T)head->lchild=head;/*若二叉树为空，则左指针回指*/ else{head->lchild=T;pre=head;InThreading(T);/*中序遍历进行中序线索化*/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 && pre->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->rtag==1)pre->rchild=p;pre=p; /* 前驱指向当前结点*/INTHREAD(p->rchild); /* 右子树线索化*/}4 调试分析该程序在调试过程中遇到的问题是：对已学知识运用能力欠缺，尤其是在编程方面，由于C语言等计算机基础课程知识没有很好的掌握同时在学习数据结构时也没有真正弄懂导致编程时小错误不断，而且在遇到许多小的错误时靠自己很难再调整过来，但整体上是一次对所学知识的运用巩固，特别是对二叉树的建立以及对它进行线索方面，翻阅大量的书籍及搜集资料并求教于计算机系的同学，才找到一些解决问题的方法，在用中序遍历线索二叉树时总是搞混不过也因此让我对前序，中序，后序遍历更加理解。