线索二叉树的应用

1、课程设计说明书（数据结构课程设计）专 业: 网络工程 课程名称: 数据结构课程设计 班级: 网络B11-1设计题目: 线索二叉树的应用 设计时间: 2013-2-25 至 2013-3-8 评 语:_评阅成绩: 评阅教师: 一、问题描述与需求分析1、问题描述 本实验的问题是建立一个线索二叉树，并实现线索二叉树的插入、删除、恢复线索等功能。2、功能需求分析 本程序要实现的功能是： 1. 线索二叉树的建立。 2.线索二叉树的插入。 3.线索二叉树的删除。 4.线索二叉树的恢复。 想要完成上面的功能，我们首先是要知道上面是线索二叉树。我们可以从数据结构的书上找到答案，利用二叉链表的空指针域将空的左孩

2、子指针域改为指向其前驱，空的右孩子指针域改为指向其后继。这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表。 N个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点的在某种遍历次序下的前驱和后继结点的指针，这种加上了线索的二叉链表称为线索链表。相应的二叉树称为线线索二叉树。根据线索二叉树性质的不同，线索二叉树可以分为前序线索二叉树，中序线索二叉树和后续线索二叉树三种，此次课程设计中使用的是中序线索二叉树。二、概要设计1、总体设计思路 首先就是要建立一个二叉树，然后再对二叉树进行线索化。 线索链表中的结点结构为：其中：线索二叉树及其存储结构如在线索树上进行遍历

3、，只需先找到序列中的第一个结点，然后依次找结点后继为空时而止。以上图为例子说明在线索树中查找结点的后继。树中所有叶子的结点是线索，则右链域直接指示结点的后继，如结点b的后继为结点*。树中所有非终端结点的右链均为指针，则无法由此得到后继的信息。然而根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树最左下的结点。列入在找结点*的后继时，首先沿右指针找到其右子树的根结点“”，然后顺其左指针往下直至其左标志为1的结点，即为结点* 的后继，在图中是结点c。反之，在中序结点中找结点前驱的规律是：若其左标志为“1”，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左

4、子树最右下的结点）为其前驱。 开始定义二叉树 建立二叉树 选择菜单输入i(1-5) N N N N I=3 I=2 I=1 I=5 I=4 输出线索二叉树二叉树的线索化中序输出二叉树Y Y Y Y Y删除结点并线索haunted插入结点并线索化 结束 程序流程图2、 模块简介 本程序有五个模块功能。每个模块功能均实现特定的功能。1. 二叉树的建立：中序输入二叉树，为程序提供数据，输入的时候空域用表示。2. 进行二叉树的线索化： 按中序遍历顺序将二叉树线索化，只需要在遍历的过程中将二叉树的每个结点的空的左右孩子的指针域分别修改为指向其前驱和后继，若其左子树为空，则将其左孩子域线索化，使其左孩子指

5、针lchild指向其后继，并且ltag置1. 3插入操作： 输入要插入的结点信息，然后再查找要插入结点的位置，插入新结点。 4删除操作，确定要删除的结点，查找出要删除的结点，找到之后会显示ltag和rtag信息。 5输出线索二叉树，输出的线索二叉树为经过处理的二叉树。 三、详细设计1、数据结构设计 程序采用线索链表做存储结构。程序中有二叉树的建立，插入，删除，恢复线索，这些操作都是基于线索链表作的。2、 算法分析与实现二叉树的建立： 建立一个二叉树，需要按照某种顺序依次输入二叉树中的结点，且该输入顺序必须隐含结点间的逻辑结构信息。这种建立的方法，按全二叉树的层次顺序，一次输入结点信息建立二叉链

6、表的过程。以表示空结点，以#表示输入结束的标志，。 一次输入结点信息，若其不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为跟结点，否则将新结点作为孩子链接到它的父亲结点上。 在函数中设置一个队列，该队列是一个指针类型的数组，保存以输入的结点的地址。使队列指针front指向当前与孩子建立链接的父亲结点，队尾指针rear指向当前输入的结点。若rear为偶数，则该结点为父结点的左孩子，若rear为奇数，则为父结点的右孩子。若父结点或孩子结点为虚结点，则无需链接，若父结点与其两个孩子结点链接完毕，则使front指向下一个等待链接的父结点。 算法实现： Bithptr *Qmaxsize;

7、/建队为指针类型Bithptr *CreatTree()front=1;rear=0; /置空队if(ch!='') /不是虚结点.则建立结点s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;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(

8、rear%2=1)front+; /结点*Qfront的两个孩子处理完front+1线索化算法：线索过程需要按照一定的顺序进行，此次程序使用的是中序遍历，所以线索化也将使用中序线索化。按照某种遍历顺序将二叉树线索化，只需在遍历的过程中将二叉树的每个结点空的左右孩子的指针分别修改为指向其前驱和后继。若其左右树为空，则将其左孩子域线索化，使其左孩子指针lchild指向其后继，并且ltag为1.要实现线索化，就要知道结点*pre是*p的前驱，而*p是*pre的后继。这样，当遍历到结点*p时，可以进行，若*P有空指针域，则将相应的标志为1,；若*p的左线索标志已经建立（p->ltag=1），则可

9、使其前驱线索化，令p->lchild=pre；若*pre的左线索标志已经建立（pre->rtag=1），则可使其后继线索化，令pre->rchild=p; 算法实现;void 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-&

10、gt;rtag=1;pre=p;PreThread(p->rchild);插入结点函数： 在书中插入一个结点，必须要以固定的规则来进行插入。本程序中树的输出使用了中序输出的方法，所以插入的时候使用的规则就是以中序输出为顺序，先查找到一个点，再将要插入的结点，作为该结点的前驱插入树中。如中序为：dbeafcg。插入的结点为：b,则插入后的顺序为dwbeafcg。 使用查找孩子指针函数来查找结点位置的指针。在查找的过程中要处理好线索指针和孩子指针的关系，不能将线索也当做孩子来处理了。并且在循环的判断中，且不能使用以前的空位结束语句，而是要用标志域来进行判断。在查找的过程中，考虑到树的递归性质

11、，所以讲查找函数也设置成递归函数。 算法实现： Bithptr*SearchChild(Bithptr*point,char findnode)Bithptr *point1,*point2;if(point!=NULL)if(point->data=findnode)return point; /找到结点的信息.返回指针elseif(point->ltag!=1) / 判断是否有左子树point1=SearchChild(point->lchild,findnode);/递归if(point1!=NULL)return point1;if(point->rtag!=1

12、) /判断是否有右子树point2=SearchChild(point->rchild,findnode);/递归if(point2!=NULL)return point2;return NULL;elsereturn NULL; 在一棵树种插入一个结点，因为插入的位置不同，就对应着不同的插入情况。当插入结点有左孩子时：找到左孩子的最右下结点将待插的结点插为其结点的右孩子。当插入结点没有左孩子时：直接将带插的结点插为其结点的左孩子。 算法实现：􀈎当结点有左子树时.p2=child;child=child->lchild;while(child->rchild

13、&&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;􀈎当结点没左孩子的时.p1->lchild=child->lchild; /前驱化child->ltag=0;p1->ltag=1;child->lchild

14、=p1;p1->rchild=childp1->rtag=1;删除结点函数： 要在函数中删除一个结点，有几种不同的情况，在删除结点之前要先找到要删除的结点，调用查找孩子结点的函数Bithptr *SearchChild(Bithptr*point,char findnode)，找到其结点指针的指针。删除过程中设计的指针变换需要父亲结点的指针，所以就调用查找父亲结点的函数Bithptr*SearchPre(Bithptr *point,Bithptr *child)来查找该结点的父亲结点的指针。 删除的过程中有不同的情况。 1当要删除结点为父亲的左孩子时 若要删除结点没有左右孩子：则

15、直接删除； 若要删除结点有左孩子没有右孩子：则要删除结点的左孩子给父亲结点的左孩子； 若要删除结点有右孩子没有左孩子：则将要删除结点的右孩子给父亲结点的左孩子； 若要删除结点左右孩子都有：将要删除结点的左子树的右子树接到孩子结点的右子树的最左下结点的左子树.再将孩子结点的右子树接到孩子结点左子树的右子树。 2当要删除结点是父亲结点的右孩子时 若要删除结点没有左右孩子。则直接将空给头指针。 若要删除结点有左孩子没右孩子，则将孩子结点的左孩子作为头结点。 若要删除结点有右孩子没左孩子，则将孩子结点的右孩子作为头结点。 若要删除结点左右孩子都有，则将孩子结点的左孩子作为头结点，将孩子结点的右子树插入

16、孩子结点的左子树的最右下结点的右子树。 算法实现： 􀈎只列出要删除结点是父结点的左子树的情况.要删除结点无左右pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;要删除结点有左无右pre->lchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->

17、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->rtag=1)child->lchild->rchild=pre;要删除结点左右都有.pre->lchild=child->lchild;s=child->rchild;wh

18、ile(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->rchild;q->rchild=s;child->lchild->rchild=child->rchild;child->lchild->rtag=0;四、运行结果和调试分析输

19、入数据，中序建立二叉树。选择1，中序输出二叉树。选择2，进行二叉树的线索化。选择5可以查看线索化后的二叉树。选择一个要插入的结点信息，输入要查找的结点信息。输入5可输出进行插入操作之后的线索二叉树。选择删除操作，输入要删除的结点信息，发现结点后输出结点信息，删除结点操作成功。 五、总结体会 此次课程设计让我充分学习了一个程序的开发过程。代码的编写是一个枯燥的过程，但是其中不乏很多挑战，一个好的程序不仅是要能完成一个特定的任务，更重要的是要能高效的完成任务。 编写完程序之后，大部分的时间就是在对程序进行测试，可想而知，编代码的时间很短，耗费时间的是测试阶段，因为在这个过程中我发现了很多的问题，再

20、针对这些出现的问题，进行修改，是程序具有一个合理的结构，良好的可读性和用户友好性。 当然在整个过程中，也有很多的问题是我无法解决的，在这个时候我会求助于我的同学，他们都很乐意给予我帮助，对我提出的问题进行耐心个的分析，在这个过程中问题不仅解决了，我写学习了同学的思想，他们对解决问题的方法。 此次课程设计还让我感觉到，解决问题时的思想很重要，因为思想决定着你程序的走向，我解决问题的方法，可以说，学习程序设计，思想是很重要的。有一个好的思想，会对程序有很大的帮助。 参考文献1严蔚敏，吴伟民编著数据结构（C语言版）清华大学出版社。源代码：#include "stdio.h"#in

21、clude "malloc.h"#define maxsize 20 /规定树中结点的最大数目#include"windows.h"typedef struct node /定义数据结构int ltag,rtag; /表示child 域指示该结点是否孩子char data; /记录结点的数据struct node *lchild,*rchild; /记录左右孩子的指针Bithptr;Bithptr *Qmaxsize; /建队，保存已输入的结点的地址Bithptr *CreatTree() /建树函数，返回根指针char ch;int front,rea

22、r;Bithptr *T,*s;T=NULL;front=1;rear=0; /置空二叉树printf(" *n");printf(" * *n");printf(" * 线索二叉树的运算。 *n");printf(" * *n");printf(" *n");printf(" 请依次输入数据表示空结点，以#结束n");ch=getchar(); /输入第一个字符while(ch!='#') /判断是否为结束字符s=NULL;if(ch!=''

23、) /判断是否为空结点s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;rear+;Qrear=s; /将结点地址加入队列中if(rear=1)T=s; /输入为第一个结点为根结点elseif(s!=NULL&&Qfront!=NULL) /孩子和双亲结点均不是虚结点if(rear%2=0)Qfront->lchild=s;else Qfront->rchild=s;if(rear%2=1)fr

24、ont+;ch=getchar();return T;void Inorder(Bithptr *T) /中序遍历if(T)if(T->ltag!=1)Inorder(T->lchild);printf("%c",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&

25、&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);void PrintIndex(Bithptr *t) /输出线索Bithptr *f;f=t;if(f)if(f->ltag=1&&f->lchild=NULL&&f->rtag=1) printf(

26、" 【%c 】",f->data);/如果是第一个结点if(f->ltag=1&&f->lchild!=NULL) printf("%c 【%c 】",f->lchild->data,f->data); /如果此结点有前驱就输出前驱和此结点if(f->ltag=1&&f->rtag=1&&f->rchild!=NULL)printf("%c",f->rchild->data); /如果此结点有前驱也有后继?就输出后继els

27、e if(f->rtag=1&&f->rchild!=NULL) printf(" 【%c 】%c",f->data,f->rchild->data);/如果没有前驱?就输出此结点和后继printf("n");if(f->ltag!=1)PrintIndex(f->lchild);if(f->rtag!=1)PrintIndex(f->rchild);Bithptr *SearchChild(Bithptr *point,char findnode) /查找孩子结点函数Bithptr

28、*point1,*point2;if(point!=NULL)if(point->data=findnode) return point;elseif(point->ltag!=1) point1=SearchChild(point->lchild,findnode);if(point1!=NULL)return point1;if(point->rtag!=1) point2=SearchChild(point->rchild,findnode);if(point2!=NULL)return point2;return NULL;elsereturn NULL;

29、Bithptr *SearchPre(Bithptr *point,Bithptr *child) /查找父亲结点函数Bithptr *point1,*point2;if(point!=NULL)if(point->ltag!=1&&point->lchild=child)|(point->rtag!=1&&point->rchild=child)return point;/找到则返回elseif(point->ltag!=1)point1=SearchPre(point->lchild,child);if(point1!=N

30、ULL)return point1;if(point->rtag!=1)point2=SearchPre(point->rchild,child);if(point2!=NULL)return point2;return NULL;elsereturn NULL;void Insert(Bithptr *root)char ch;char c;Bithptr *p1,*child,*p2;printf("请输入要插入的结点的信息:");scanf("%c",&c);scanf("%c",&c);p1=(Bi

31、thptr *)malloc(sizeof(Bithptr); /插入的结点信息p1->data=c;p1->lchild=NULL;p1->rchild=NULL;p1->rtag=0;p1->ltag=0;printf("输入查找的结点信息:");scanf("%c",&ch);scanf("%c",&ch);child=SearchChild(root,ch); /查孩子结点的地址if(child=NULL)printf("没有找到结点n");return ;el

32、se printf("发现结点%cn",child->data);if(child->ltag=0) /当孩子结点有左孩子的时候p2=child;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->lchil

33、d=child; /前驱化p1->ltag=1;else /当孩子结点没有左孩子的时候p1->lchild=child->lchild; /前驱化child->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("输入查找的结

34、点信息:");ch=getchar();ch=getchar();child=SearchChild(t,ch); /查找该结点的孩子结点printf("发现结点:%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",p

35、re->data);else/当是头结点的时候if(child->ltag=1&&child->rtag=1) /没有左右孩子t=NULL;else if(t->ltag=1&&t->rtag!=1) /有右孩子没有左孩子t=child->rchild;child->rchild->lchild=NULL;free(child);return t;elseif(t->ltag!=1&&t->rtag=1) /有左孩子没有右孩子t=child->lchild;child->lc

36、hild->rchild=NULL;free(child);return t;elseif(t->ltag!=1&&t->rtag!=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-

37、>rchild=child->rchild; /连接s->rtag=0;q->lchild=s;free(child);return t;if(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-

38、>rchild=pre;free(child);else if(1!=child->ltag&&1=child->rtag)/孩子结点有左无右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->lch

39、ild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;s->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

40、=child->rchild;while(s->lchild&&s->ltag!=1) /找到右子树的最左下结点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)/是

41、父亲结点的右孩子if(1=child->ltag&&1=child->rtag)/孩子结点无左右pre->rchild=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=child->rchild;if(child->rchild!=NULL