线索二叉树课程设计

1、信息科学与技术学院数据结构课程设计报告题目名称： 线索二叉树的计算 学生姓名： 刘 少 博 学 号: * 专业班级： 计算机科学与技术 指导教师： 高 攀 2014年 1月 8 1、设计的目的与要求 此程序需要完成如下要求：建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。实现本程序需要解决以下几个问题：1、 如何建立线索二叉树。2、 如何实现线索二叉树的插入。3、 如何实现线索二叉树的删除。4、 如何实现线索二叉树恢复线索的实现。此题目是线索二叉树的一系列操作问题。首先就要明白线索二叉树是什么，利用二叉链表的空指 针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后

2、继，这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。 在这个问题中，要解决的任务是：实现线索二叉树的建立、插入、删除、恢复线索的实现。N个 结 点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下 的前趋和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。在此次课程设计中，采用的是中序线索二叉树。 目 录摘

3、要41、 引言52、 设计任务与目的 53、 设计方案与实施5 1、总体设计 52、 详细设计 7 3、程序清单 134、程序调试与体会245、运行结果（截图） 24四、结论27五、致谢27 六、参考文献27 摘 要随着人们生活水平的提高，计算机发展异常迅速。如今，计算机已经深入到我们社会的各个领域，计算机的使用也已不再局限于科学计算，它已进入人类社会的各个领域并发挥着越来越重要的作用。通过计算机对各类问题求解已经成为一种高效、快捷的方式。树在计算机领域也得到了广方的应用，如在编译程序中，可以用树表示原程序的语法结构。 本次课程设计主要运用二叉树的一些特点，来实现线索二叉树的建立、插入、删除、

4、恢复线索等等。关键词：二叉树，线索链表，线索化，线索。Abstract Key words: Binary tree, Clues linked list, Clues optimization, Clues. As people living standard rise, computer to abnormal development rapidly. Today, computers have deeply into every field of our society, the use of computers is no longer limited to scientific co

5、mputing, it entered the human society eachdomain and plays a more and more important role. Through computer for all kinds of problem solving has become an efficient, quick way. Trees in the field of computer also got wide square applications, such as in compiler, can use the tree says the original p

6、rogram grammatical structures. 数据结构课程设计-线索二叉树的计算一、引 言树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。结构树在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序时，可用树表示源程序的语法结构。又如在数据系统库中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。 二、设计目的与任务通过本课程设计教学所要求达到的目的是：建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。三、

7、设计方案1、总体设计 首先建立二叉树，然后对二叉树进行线索化。线索链表的结点结构    线索链表中的结点结构为： 图(1) 线索链表中的结点结构中序线索二叉树的图示  图(2) 中序线索二叉树 建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。 关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。 （1）令队头指针front指向其孩子结点当

8、前输入的建立链接的父结点，队尾指针 rear指向当前输入的结点，初始：front=1,rear=0; （2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。 （3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。二叉树的中序索化算法与中序历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p

9、的前趋，而*p是*pre的后继。程序流程图:图(3) 程序流程图 2、详细设计(1) 建树算法：1、分析：建立一个二叉链表，需要按照某种顺序依次输入二叉树中的结点，且该输入顺序必须隐含结点间的逻辑结构的信息。这个建立的方法，按完全二叉树的层次顺序，依次输入结点信息建立二叉链表的过程。以表示空结点，以#表示输入结束的标志 。2、算法思想：依次输入结点信息，若其不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点，否则将新结点作为孩子链接到它的父亲结点上。3、实现：在函数中设置一队列，该队列是一个指针类型的数组，保存已输入的结点的地址。使队头指针front指向当前与孩子建立链接的父亲

10、结点，队尾指针rear指向当前输入的结点。若rear为偶数，则该结点为父结点的左孩子，若rear为奇数，则为父结点的右孩子。若父结点或孩子结点为虚结点，则无需链接。若父结点与其两个孩子结点链接完毕，则使front指向下一个等待链接的父结点。4、主要过程： Bithptr *Qmaxsize; /建队为指针类型 Bithptr *CreatTree() front=1;rear=0; /置空队 if(ch!='') /不是虚结点，则建立结点 s=(Bithptr *)malloc(sizeof(Bithptr); s->data=ch; s->lchild=NULL;

11、 s->rchild=NULL; s->rtag=0; s->ltag=0; if(s!=NULL&&Qfront!=NULL) /孩子和双亲结点都不是虚结点 if(rear%2=0) Qfront->lchild=s; else Qfront->rchild=s; if(rear%2=1)front+; /结点*Qfront的两个孩子处理完，front+1(2) 线索化算法：1、分析：线索过程必须要按照一定的顺序来进行，在本程序中因为树的遍历过程使用的是中序遍历，所以为了方便，线索化的过程也是使用中序线索化。2、方法：按某种遍历顺序将二叉树线索化

12、，只需要在遍历的过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继。若其左子树为空，则将其左孩子域线索化，使其左孩子指针lchild指向其后继，并且ltag置1。3、实现：要实现线索化，就要知道结点*pre是结点*p的前驱，而*p是*pre的后继。这样，当遍历到结点*p时，可以进行，若*p有空指针域，则将相应的标志置1；若*p的左线索标志已经建立（p->ltag=1），则可使其前驱线索化，令p->lchild=pre；若*pre的左线索标志已经建立（pre->rtag=1），则可使其后继线索化，令pre->rchild=p;4、主要过程： void

13、PreThread(Bithptr *root) PreThread(p->lchild); /左子树线索化if(pre&&pre->rtag=1)pre->rchild=p; /前驱结点后继线索化 if(p->lchild=NULL) p->ltag=1;p->lchild=pre;if(p->rchild=NULL) /后继结点前驱线索化p->rtag=1;pre=p;PreThread(p->rchild);(3) 插入结点函数1、方法：在树中插入一个结点，就必须要以固定的规则来进行插入。在本程序中对树的输出使用了中序

14、输出的方法，所以插入的时候使用的规则就是以中序输出为顺序，先查找到一个点，再将要插入的结点作为该结点的前驱插入树中。如中序为：dbeafcg 插入的结点为：w 要插入的位置为：b 则插入结点后的顺序为：dwbeafcg 2、查找：使用查找孩子指针函数来查找结点位置的指针。在查找的过程中要处理好线索指针和孩子指针的关系，不能将线索也当作孩子处理了。并且在循环的判断过程中，再不能使用以前的以空为结束语句，而是要用标志域来进行判断。在查找的过程中，考虑到树的递归性质，所以将查找函数也设置为递归函数。3、查找函数实现：Bithptr*SearchChild(Bithptr*point,char fin

15、dnode) Bithptr *point1,*point2; if(point!=NULL)if(point->data=findnode)return point; /找到结点的信息，返回指针 else if(point->ltag!=1) /判断是否有左子树point1=SearchChild(point->lchild,findnode);/递归if(point1!=NULL)return point1; if(point->rtag!=1) /判断是否有右子树point2=SearchChild(point->rchild,findnode);/递归if

16、(point2!=NULL)return point2; return NULL; else return NULL;4、插入方法：在一棵树中插入一个结点，因为插入的位置不同，就对应着不同的插入情况。通过分析总结出各种情况： 插入结点有左孩子时：插入的方法是，找到左子树的最右下结点，将待插的结点插为其结点的右孩子。 插入结点没有左孩子时： 插入的方法是，直接将待插的结点插为其结点的左孩子。5、插入实现：（当结点有左子树时）p2=child;child=child->lchild;while(child->rchild&&child->rtag=0) /左子树的

17、最右下结点child=child->rchild;p1->rchild=child->rchild; /后继线索化p1->rtag=1;child->rtag=0;child->rchild=p1; /连接结点p1->lchild=child; /前驱线索化p1->ltag=1;（当结点没左孩子的时）p1->lchild=child->lchild; /前驱化child->ltag=0;p1->ltag=1;child->lchild=p1;p1->rchild=childp1->rtag=1; 6、图形

18、显示：如插入abcdefg# 中序为：dbeafcg 插入的结点为：w 要插入的位置为：b 建树后，结点的线索变化如图4和图5；其中虚线为待插结点在插入过程中将要变化的线索 a b ce d g dvvv f图(4) 结点的线索变化图a 则插入结点后的顺序为：dwbeafcg w a g fe c d b图(5) 结点的线索变化 图b (4) 删除结点函数 1、分析：要在函数中删除一个结点，也要考虑各种不同的情况。在删除结点之前也要先找到要删除的点，就调用查找孩子结点函数Bithptr *SearchChild(Bithptr *point,char findnode)找到其结点的指针。再后面

19、的操作就是怎样删除了，就发现在删除过程中涉及的指针变换需要父亲结点的指针，所以就调用查找父亲结点函数Bithptr *SearchPre(Bithptr *point,Bithptr *child)来查找该结点的父亲结点指针。 2、删除方法：考虑在删除的过程中的各种不同的情况，就要在程序的设计中进行不同的分类，进行不同的处理，考虑不同的处理过程。通过总结可以知道各种不同的情况。（当要删除结点是父亲结点的左孩子时） 若要删除结点没有左右孩子：则直接删除； 若要删除结点有左孩子没右孩子：则将要删除结点的左孩子给父亲结点的左孩子； 若要删除结点有右孩子没左孩子：则将要删除结点的右孩子给父亲结点的左孩

20、子； 若要删除结点左右孩子都有：将要删除结点的左子树的右子树接到孩子结点的右子树的最左下结点的左子树，再将孩子结点的右子树接到孩子结点左子树的右子树。（当要删除结点是父亲结点的右孩子时） 若要删除结点没有左右孩子：则直接删除； 若要删除结点有左孩子没右孩子：则将要删除结点的左孩子给父亲结点的右孩子； 若要删除结点有右孩子没左孩子：则将要删除结点的右孩子给父亲结点的右孩子； 若要删除结点左右孩子都有：将要删除结点的右子树的左子树接到孩子结点的左子树的最右下结点的右子树，再将孩子结点的右子树接到孩子结点右子树的左子树。(当要删除结点是整个二叉树的头结点时) 若要删除结点没有左右孩子，则直接将空给头

21、指针。 若要删除结点有左孩子没右孩子，则将孩子结点的左孩子作为头结点。 若要删除结点有右孩子没左孩子，则将孩子结点的右孩子作为头结点。 若要删除结点左右孩子都有，则将孩子结点的左孩子作为头结点，将孩子结点的右子树插入孩子结点的左子树的最右下结点的右子树。 3、实现：（只列出要删除结点是父结点的左子树的情况） 要删除结点无左右pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;要

22、删除结点有左无右：pre->lchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->rchild=child->rchild;要删除结点有右无左：pre->lchild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;s->lchild=child->lchild;if(child->lchild!=NULL) if(child->lchild->

23、rtag=1)child->lchild->rchild=pre;要删除结点左右都有：pre->lchild=child->lchild;s=child->rchild;while(s->lchild)s=s->lchild;s->lchild=child->lchild->rchild; /把要删除结点的左孩子的右子树接到孩子右子树的最左下结点if(child->lchild->rtag!=1)s->ltag=0;q=child->lchild;while(q->rchild)q=q->rchil

24、d;q->rchild=s;child->lchild->rchild=child->rchild;child->lchild->rtag=0;4、图形显示如图6：如删除结点e 中序为：dbeafcg 删除后：dbafcg g f e d c b a图（6）删除结点图示3、 程序清单#include "stdio.h"#include "malloc.h"#define maxsize 20 /规定树中结点的最大数目typedef struct node /定义数据结构int ltag,rtag; /表示child域指

25、示该结点是否孩子 char data; /记录结点的数据struct node *lchild,*rchild; /记录左右孩子的指针Bithptr; Bithptr *Qmaxsize; /建队，保存已输入的结点的地址 Bithptr *CreatTree() /建树函数，返回根指针char ch;int front,rear;Bithptr *T,*s;T=NULL;front=1;rear=0; /置空二叉树printf("*n"); printf("* *n"); printf("* 课程设计题目：线索二叉树的运算。*n");

26、 printf("* *n"); printf("*n"); printf("创建二叉树，请依次输入，表示虚结点，以#结束n");ch=getchar(); /输入第一个字符while(ch!='#') /判断是否为结束字符s=NULL;if(ch!='') /判断是否为虚结点s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;rea

27、r+; Qrear=s; /将结点地址加入队列中if(rear=1)T=s; /输入为第一个结点为根结点else if(s!=NULL&&Qfront!=NULL) /孩子和双亲结点均不是虚结点if(rear%2=0) Qfront->lchild=s; else Qfront->rchild=s;if(rear%2=1)front+;ch=getchar();return T;void Inorder(Bithptr *T) /中序遍历if(T)if(T->ltag!=1)Inorder(T->lchild);printf("%c"

28、,T->data);if(T->rtag!=1)Inorder(T->rchild);Bithptr *pre=NULL;void PreThread(Bithptr *root) /中序线索化算法，函数实现Bithptr *p;p=root; if(p) PreThread(p->lchild);/线索化左子树 if(pre&&pre->rtag=1)pre->rchild=p; /前驱结点后继线索化 if(p->lchild=NULL) p->ltag=1;p->lchild=pre;if(p->rchild=NU

29、LL) /后继结点前驱线索化p->rtag=1;pre=p;PreThread(p->rchild);void PrintIndex(Bithptr *t) /输出线索Bithptr *f;f=t;if(f)if(f->ltag=1&&f->lchild=NULL&&f->rtag=1) printf("【%c】",f->data); /如果是第一个结点if(f->ltag=1&&f->lchild!=NULL) printf("%c【%c】",f->l

30、child->data,f->data); /如果此结点有前驱就输出前驱和此结点 if(f->ltag=1&&f->rtag=1&&f->rchild!=NULL) printf("%c",f->rchild->data); /如果此结点有前驱也有后继，就输出后继else if(f->rtag=1&&f->rchild!=NULL) printf("【%c】%c",f->data,f->rchild->data);/如果没有前驱，就输出

31、此结点和后继printf("n");if(f->ltag!=1)PrintIndex(f->lchild);if(f->rtag!=1)PrintIndex(f->rchild); Bithptr *SearchChild(Bithptr *point,char findnode) /查找孩子结点函数 Bithptr *point1,*point2; if(point!=NULL) if(point->data=findnode) return point; else if(point->ltag!=1) point1=SearchChi

32、ld(point->lchild,findnode); if(point1!=NULL)return point1; if(point->rtag!=1) point2=SearchChild(point->rchild,findnode); if(point2!=NULL)return point2; return NULL; else return NULL; Bithptr *SearchPre(Bithptr *point,Bithptr *child) /查找父亲结点函数 Bithptr *point1,*point2; if(point!=NULL) if(poi

33、nt->ltag!=1&&point->lchild=child)|(point->rtag!=1&&point->rchild=child) return point;/找到则返回 else if(point->ltag!=1) point1=SearchPre(point->lchild,child); if(point1!=NULL) return point1; if(point->rtag!=1) point2=SearchPre(point->rchild,child); if(point2!=NULL

34、) return point2; return NULL; else return NULL;void Insert(Bithptr *root)char ch;char c;Bithptr *p1,*child,*p2;printf("请输入要插入的结点的信息:"); scanf("%c",&c);scanf("%c",&c); p1=(Bithptr *)malloc(sizeof(Bithptr); /插入的结点信息p1->data=c;p1->lchild=NULL;p1->rchild=NU

35、LL;p1->rtag=0;p1->ltag=0;printf("输入查找的结点信息:"); scanf("%c",&ch);scanf("%c",&ch);child=SearchChild(root,ch); /查孩子结点的地址if(child=NULL)printf("没有找到结点n");return ;else printf("发现结点%cn",child->data);if(child->ltag=0) /当孩子结点有左孩子的时候p2=child

36、;child=child->lchild;while(child->rchild&&child->rtag=0) /找到左子树下，最右结点child=child->rchild;p1->rchild=child->rchild; /后继化 p1->rtag=1;child->rtag=0;child->rchild=p1; /连接 p1->lchild=child; /前驱化p1->ltag=1; else /当孩子结点没有左孩子的时候p1->lchild=child->lchild; /前驱化chi

37、ld->ltag=0;p1->ltag=1;child->lchild=p1;p1->rchild=child;p1->rtag=1;printf("nt插入结点操作已经完成，并同时完成了线索化的恢复n");Bithptr * DeleteNode(Bithptr *t)Bithptr *child,*pre,*s,*q;char ch;printf("输入查找的结点信息:"); ch=getchar();ch=getchar();child=SearchChild(t,ch); /查找该结点的孩子结点printf(&quo

38、t;发现结点:%cn",child->data);printf("ltag=%d,rtag=%dn",child->ltag,child->rtag);if(NULL=child)printf("没有找到结点:");return t;if(child!=t)pre=SearchPre(t,child);printf("发现结点:%cn",pre->data);else /当是头结点的时候if(child->ltag=1&&child->rtag=1) /没有左右孩子t=NU

39、LL;else if(t->ltag=1&&t->rtag!=1) /有右孩子没有左孩子t=child->rchild;child->rchild->lchild=NULL;free(child);return t;else if(t->ltag!=1&&t->rtag=1) /有左孩子没有右孩子t=child->lchild;child->lchild->rchild=NULL;free(child);return t;elseif(t->ltag!=1&&t->rtag!

40、=1) /有左孩子也有右孩子t=child->lchild;s=child->lchild;while(s->rchild&&s->rtag!=1) /查找孩子左子树的最右下结点s=s->rchild;q=child->rchild;while(q->lchild&&q->ltag!=1) /查找孩子右子树的最左下结点q=q->lchild;s->rchild=child->rchild; /连接s->rtag=0;q->lchild=s;free(child);return t; i

41、f(child=pre->lchild|child=pre) /是父亲结点的左孩子if(1=child->ltag&&1=child->rtag)/孩子结点无左右pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;free(child);else if(1!=child->ltag&&1=child->rtag)/孩

42、子结点有左无右 pre->lchild=child->lchild; s=child->lchild; while(s->rchild) /查找左子树的最右下结点s=s->rchild; s->rchild=child->rchild;free(child);else if(1=child->ltag&&1!=child->rtag)/孩子结点有右无左 pre->lchild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;s-

43、>lchild=child->lchild;if(child->lchild!=NULL) if(child->lchild->rtag=1)child->lchild->rchild=pre;free(child); else if(1!=child->ltag&&1!=child->rtag)/孩子结点左右都有 pre->lchild=child->lchild;s=child->rchild;while(s->lchild&&s->ltag!=1) /找到右子树的最左下结点

44、s=s->lchild;q=child->lchild;while(q->rchild&&q->rtag!=1) /找到左子树下最右下结点q=q->rchild;q->rchild=child->rchild; /将孩子结点的右子树接到左子树下最右下结点q->rtag=0;s->lchild=q;free(child); else if(child=pre->rchild) /是父亲结点的右孩子if(1=child->ltag&&1=child->rtag)/孩子结点无左右pre->r

45、child=child->rchild;pre->rtag=1;if(child->rchild!=NULL)if(child->rchild->ltag=1)child->rchild->lchild=pre;free(child);else if(1!=child->ltag&&1=child->rtag)/孩子结点有左无右pre->rchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->rchild=ch

46、ild->rchild;if(child->rchild!=NULL)if(child->rchild->ltag=1)child->rchild->lchild=pre;free(child);else if(1=child->ltag&&1!=child->rtag)/孩子结点有右无左 pre->rchild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;s->lchild=child->lchild;free(ch

47、ild);else if(1!=child->ltag&&1!=child->rtag) /孩子结点左右都有pre->rchild=child->rchild;s=child->rchild;while(s->lchild&&s->ltag!=1) /找到右子树的最左下结点s=s->lchild;q=child->lchild;while(q->rchild&&q->rtag!=1) /找到左子树下最右下结点q=q->rchild;s->lchild=child->

48、;lchild; /将孩子结点的左子树接到右子树下最左下结点s->ltag=0;q->rchild=s;free(child);printf("nt删除结点操作已经完成，并同时完成了线索化的恢复n");return t;void main()Bithptr *T;int i;T=CreatTree();printf("n");i=1;while(i) printf("t1 中序输出二叉树n");printf("t2 进行二叉树线索化n");printf("t3 进行插入操作n");printf("t4 进入删除操作n");printf("t5 输出线索二叉树n");printf("t0 退出n");printf("t 请选择:&qu