数据结构课程设计之线索二叉树的应用

1、大学数据结构课程设计报告题目：线索二叉树的应用院（系）：计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2011.6.16-2011.6.29指导教师: 指导教师评语： 成绩： 签名： 年 月 日20102011年度 第 2 学期 一、需求分析1.问题描述：在这个问题中，要解决的任务是：实现线索二叉树的建立、插入、删除、恢复线索的实现.n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针。加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索

2、二叉树三种。在此次课程设计中，采用的是中序线索二叉树。 2.基本功能 1： 定义数据结构； 2：建立二叉树函数，返回根指针；3：中序遍历； 4:中序线索化算法函数实现；5：输出线索； 6：查找数据结点函数； 7：查找父亲结点函数； 8：插入结点函数； 9：删除结点函数。 3.输入输出 原始数据要求输入二叉树的七个结点：abcdefg，输入的是一个二叉树，这就实现了二叉树的建立过程。然后对二叉树进行线索化。对其进行插入：在d结点插入结点h；删除：删除结点f；恢复线索等功能。 * * *课程设计题目: 线索二叉树的运算.* *创建二叉树，请依次输入，表示虚结点，以#结束: abcdefg 1 中序

3、输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出请选择:1 dgbeafc 1 中序输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出请选择:2 已经实现二叉树的线索化，（可选择'5'查看线索）二、 概要设计 1.设计思路：建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个

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

5、点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。结点插入算法：由线索二叉树的定义易知插入的节点定是个叶子节点，需注意线索的修改，可分为两种情况：(1）：插入的节点t是右儿子，t的中序后继是其父亲的中序后继，中序前驱是其父亲。(2）：插入的节点t是左儿子，t的中序前驱是其父亲的中序前驱，中序后继是其父亲。结点删除算法：删除的情况与搜索二叉树的删除的类似(1）：删除的节点p是叶子节点，直接删除，修改其父亲的线索。(2）：删除的节点p有一个儿子，p有一个左儿子，以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继，中序前驱

6、不变；p有一个右儿子，以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱，中序后继不变。(3）：删除的节点p有二个儿子，转化为叶子节点或只有一个儿子节点的删除。2.数据结构设计：抽象数据类型二叉树的定义如下： ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D=，则R=，称BinaryTree为空二叉树； 若D=，则R=H，H是如下二元关系： （1）在D中存在唯一的成为根的数据元素root，它在关系H下无前驱； （2）若Droot，则存在Droot=（D1,Dr），且D1Dr=； （3）若D1，则D1中存在惟一的元素X1，<root,X

7、1>H,且存在D1上的关系 H1H；若Dr，则Dr中存在惟一的元素Xr，<root,Xr>H,且存在Dr上的关系 HrH,H=<root,X1>,<root,Xr>,H1,Hr； （4）（D1,H）是一颗符合本定义的二叉树，称为根的左子树，（Dr， Hr） 是一颗符合本定义的二叉树，称为根的右子树。 基本操作P： *CreatTree() 操作结果：建立二叉树树函数，返回根指针 Inorder(*T) 初始条件：二叉树已存在，已知其根结点。 操作结果：中序遍历输出各结点二叉树。 PreThread(*root) 初始条件：二叉树已存在，已知其根结点。

8、操作结果：中序线索化二叉树。 PrintIndex(*t) 初始条件：二叉树已存在，已知其根结点。 操作结果：输出线索二叉树的线索。 *SearchChild(*point,findnode) 初始条件：二叉树已存在，已知其根结点；已知结点的数据。 操作结果：返回数据对应的结点；若不存在此结点，则返回“空”。 *SearchPre(*point,*child) 初始条件：二叉树已存在，已知其根结点；已知其孩子结点。 操作结果：返回child父亲结点；若不存在此结点，则返回“空”。 Insert(*root) 初始条件：二叉树已存在，已知其根结点。 操作结果：将要插入的结点插到要插的目标结点之前

9、，并实现它线索化的恢复；若 目标结点不存在，则输出“没有找到结点”。 *DeleteNode(*t) 初始条件：二叉树已存在，已知其根结点。 操作结果：删除目标结点，并实现它线索化的恢复；若目标结点不存在，则输出 “没有找到结点”。3.软件结构设计：模块（函数名，返回类型，形式参数类型）调用的函数所对应的序号1）创建二叉树（CreatTree,void,）；2）中序遍历二叉树（Inorder,void,Bithptr *T）3）中序线索化二叉树（PreThread,void,Bithptr *root）4)输出线索二叉树（PrintIndex,void,Bithptr *t）5)查找数据结点（

10、SearchChild,Bithptr,Bithptr *pointchar findnode）6)查找父亲结点（SearchPre,Bithptr,Bithptr *pointBithptr *child）7)插入结点（Insert,void,Bithptr *root）58)删除结点（DeleteNode,Bithptr ,Bithptr *t）5,69)主程序模块(main,void,)1,2,3,4,7,8三、 详细设计1.结点类型typedef struct nodeint ltag,rtag;struct node *lchild,*rchild;char data;Bithptr

11、; /结点2.二叉树的实现void *CreatTree()/建立二叉树void Inorder(Bithptr *T)/中序遍历二叉树3.线索二叉树的实现void PreThread(Bithptr *root)/中序线索化二叉树void PrintIndex(Bithptr *t)/输出线索二叉树void Insert(Bithptr *root)/插入结点void DeleteNode(Bithptr *root)/删除结点4.全局变量Bithptr *Qmaxsize;Bithptr *pre=NULL;5.主函数void main()Bithptr *T;int i;T=CreatT

12、ree();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 请选择:");scanf("%d",&i);printf("n&quo

13、t;);switch(i)case 1:Inorder(T);printf("n");break;case 2:PreThread(T);printf("t 已经实现二叉树的线索化，（可选择'5'查看线索）n");printf("n");break;case 3:Insert(T);printf("n");break;case 4:T=DeleteNode(T);printf("n");break;case 5:PrintIndex(T);break;default:printf

14、("errornt 请继续选择:");Bithptr *CreatTree() /创建二叉树char ch;int front,rear;Bithptr *T,*s;T=NULL;front=1;rear=0;printf("*n");printf("* *n");printf(" *课程设计题目: 线索二叉树的运算.*n");printf("* *n");printf("*n");printf("创建二叉树，请依次输入，表示虚结点，以#结束n");ch=

15、getchar();while(ch!='#')s=NULL;if(ch!='')s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->ltag=0;s->rtag=0;rear+;Qrear=s;if(rear=1)T=s;elseif(s!=NULL&&Qfront!=NULL)if(rear%2=0)Qfront->lchild=s;elseQfront->rchild=s;if(rear%2=

16、1)front+;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&&pre->rt

17、ag=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("%c",f->data);if(f-

18、>ltag=1&&f->lchild!=NULL)printf("%c%c",f->lchild->data,f->data);if(f->ltag=1&&f->rchild!=NULL&&f->rtag=1)printf("%c",f->rchild->data);else if(f->rchild!=NULL&&f->rtag=1)printf("%c%c",f->data,f->rc

19、hild->data);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;elseif(point->ltag!=1)point1=SearchCh

20、ild(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;Bithptr *SearchPre(Bithptr *point,Bithptr *child) /查找父亲结点Bithptr *point1,*point2;if(point!=NULL)if(point->ltag!

21、=1&&point->lchild=child)|(point->rtag!=1&&point->rchild=child)return point;elseif(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)return point2;return NULL;

22、elsereturn 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=NULL;p1->ltag=0;p1->rtag=0;print

23、f("输入查找的结点信息:");scanf("%c",&ch);scanf("%c",&ch);child=SearchChild(root,ch);if(child=NULL)printf("没有找到结点n");return;elseprintf("发现结点%cn",child->data);if(child->ltag=0)p2=child;child=child->lchild;while(child->rchild&&child-&

24、gt;rtag=0)child=child->rchild;p1->rchild=child->rchild;p1->rtag=1;child->rtag=0;child->rchild=p1;p1->lchild=child;p1->ltag=1;elsep1->lchild=child->lchild;child->ltag=0;p1->ltag=1;child->lchild=p1;p1->rchild=child;p1->rtag=1;printf("nt插入结点操作已经完成，并同时完成

25、了线索化的恢复n");Bithptr *DeleteNode(Bithptr *t) /删除结点Bithptr *child,*pre,*s,*q;char ch;printf("输入查找的结点信息:");ch=getchar();ch=getchar();child=SearchChild(t,ch);if(NULL=child)printf("没有找到结点:");return t;if(child!=t)pre=SearchPre(t,child);printf("发现结点%cn",pre->data); prin

26、tf("ltag=%d,rtag=%dn",child->ltag,child->rtag);elseif(child->ltag=1&&child->rtag=1)t=NULL;elseif(child->ltag=1&&child->rtag!=1)t=child->rchild;child->rchild->lchild=NULL;free(child);return t;elseif(t->ltag!=1&&t->rtag=1)t=child->l

27、child; child->lchild->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->rchild=child->

28、;rchild;s->rtag=0;q->lchild=s;free(child);return t;if(child=pre->lchild|child=pre)if(child->ltag=1&&child->rtag=1)pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;free(child);elseif(child-&g

29、t;ltag!=1&&child->rtag!=1)pre->lchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->rchild=child->rchild;free(child);elseif(child->ltag=1&&child->rtag!=1)pre->lchild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;

30、s->lchild=child->lchild;if(child->lchild!=NULL)if(child->lchild->rtag=1)child->lchild->rchild=pre;free(child);elseif(child->ltag!=1&&child->rtag!=1)pre->lchild=child->lchild;s=child->rchild;while(s->lchild&&s->ltag!=1)s=s->lchild;q=child-&

31、gt;lchild;while(q->rchild&&q->rtag!=1)q=q->rchild;q->rchild=child->rchild;q->rtag=0;s->lchild=q;free(child);elseif(child=pre->rchild)if(child->ltag=1&&child->rtag=1)pre->rchild=child->rchild;pre->rtag=1;if(child->rchild!=NULL)if(child->rch

32、ild->ltag=1)child->rchild->lchild=pre;free(child);elseif(child->ltag!=1&&child->rtag=1)pre->rchild=child->lchild;s=child->lchild;while(s->rchild)s=s->rchild;s->rchild=child->rchild;if(child->rchild!=NULL)if(child->rchild->ltag=1)child->rchild-&

33、gt;lchild=pre;free(child);elseif(child->ltag=1&&child->rtag!=1)pre->rchild=child->rchild;s=child->rchild;while(s->lchild)s=s->lchild;s->lchild=child->lchild;free(child);elseif(child->ltag!=1&&child->rtag!=1)pre->rchild;s=child->rchild;while(s-&g

34、t;lchild&&s->ltag!=1)s=s->lchild;q=child->lchild;while(q->rchild&&q->rtag!=1)q=q->rchild;s->lchild=child->lchild;s->ltag=0;q->rchild=s;free(child);printf("nt删除结点操作已经完成，并同时完成了线索化的恢复n");return t;主函数:树的建立:二叉树的线索化:画出函数之间的调用关系图:四.调试分析 程序实际可以实现建立二叉树，

35、中序遍历二叉树，中序线索化二叉树，输出线索二叉 树的线索，查找二叉树的数据结点，查找二叉树结点的父亲结点，在二叉树中插入结点， 在二叉树中删除结点。比较两种存储结构发现，线索二叉树比二叉树多了两个标志域LTag，RTag。于是把两种存储结构合并为Bithptr,并在建立二叉树时把LTag，RTag均置为Link，程序正常运行。在程序编译过程中,不能对根结点进行删除,通过对算法的调整实现的.五、测试结果输入一个二叉树：abcdeff#屏幕打印结果： 1 中序输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出请选择：输入：1屏幕打印结果：dgbeafc 1 中

36、序输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出请选择：输入：2屏幕打印结果：已经实现二叉树的线索化，（可选择5查看线索） 1 中序输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出请选择：输入：5屏幕打印结果：dgbbeaafc 1 中序输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出请选择：输入：3屏幕打印结果：请输入要插入的结点的信息：输入：h屏幕打印结果：输入查找的结点信息：输入：d屏幕打印结果：发现结点d 插入结点操作已经完成，并同时完成了线索花的恢复 1 中序输出

37、二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出请选择：输入：3屏幕打印结果：请输入要插入的结点的信息：输入：j屏幕打印结果：输入查找的结点信息：输入：i屏幕打印结果：没有找到结点 1 中序输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出 请选择：输入：4屏幕打印结果：请输入要插入的结点的信息：输入：f屏幕打印结果：发现结点cltag=1,rtag=1 删除结点操作已经完成，并同时完成了线索化的恢复 1 中序输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出 请选择：输入：4屏幕打

38、印结果：请输入要插入的结点的信息：输入：k屏幕打印结果：没有找到结点 1 中序输出二叉树2 进行二叉树线索化3 进行插入操作4 进行删除操作5 输出线索二叉树0 退出 请选择：六、用户手册1.本程序开发环境为VC 6.0，运行环境为dos操作系统，执行文件为:Binary Tree.exe2.运行该程序的Binary Tree.exe文件，产生如下图所示的界面3.按提示输入二叉树（以“”表示空格）。4.输入完成后，按回车键。5.选择序号1，按回车键；选择序号2，按回车键；选择序号5，按回车键。6.选择序号3，输入h，按回车键； 输入d，按回车键；选择序号3，输入jk，按回 车键； 输入di，按

39、回车键。7.选择序号4，输入f，按回车键；选择序号4，输入k， 按回车键。七、体会与自我评价 在两个星期内匆忙但不是认真的完成了本人的课程设计，虽然在此期间遇到的困难挫折无数，最终我还是挺过来了。对于线索二叉树,我真是记忆不深，但通过本次课程设计，我已经掌握了二叉树线索化这一算法。对于线索的标志域的正确使用时线索化的关键和重点。由于对C语言程序设计有一定的实践基础，所以本人在事件的过程中获益不浅。语言是大一开的课程，所以这个学期并没怎么看过,当要开始设计的时候,还真不知从哪下手!结果第一次的上机,我傻坐着不知道该做什么。回去以后我就重新复习了一遍C语言的内容,发觉自已有许多知识都遗忘了，脑子里

40、对C语言的内容几乎是一遍空白，于是在温习过后便开始做题! 一开始做题，也是有点模糊，没有一点做题的思路，在指导老师的指导下，我慢慢的进入状态，设计出对解决问题的思路，但是老师说我的思路还存在问题并且和我详细的说明，我回去后把数据结构书本是上关于线索二叉树的内容又仔细的琢磨了一遍后设计出更好的解题思路。我的设计题目是线索二叉树的应用，包括线索二叉树的建立，插入，删除以及恢复。经过一星期的努力，我基本上完成了大半个程序，但是总是有很多错误出现，有好多是些小问题，这都是我们粗心大意造成的，所以设计程序一定要仔细，不容一点的马虎。当然也有大问题，关于线索二叉树的插入和删除为什么不能插入或删除头节点，这

41、是我遇到的最大困难了，在我百思不得解决的时候，最终在同学的帮助下和老师的指导下，让我在规定的时间内完成了我的课程设计。这次课程设计,让我重新掌握了C语言,而且还得到了用C语言解决实际问题的宝贵经验!源代码：#include "windows.h"#include<stdio.h>#include<malloc.h>#define maxsize 20typedef struct nodeint ltag,rtag;struct node *lchild,*rchild;char data;Bithptr;Bithptr *Qmaxsize;Bithp

42、tr *CreatTree()char ch;int front,rear;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

43、(ch!='')s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->ltag=0;s->rtag=0;rear+;Qrear=s;if(rear=1)T=s;elseif(s!=NULL&&Qfront!=NULL)if(rear%2=0)Qfront->lchild=s;elseQfront->rchild=s;if(rear%2=1)front+;ch=getchar();return T;void Inord

44、er(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&&pre->rtag=1)pre->rchild=p;if(p->lchild=NULL)p->

45、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("%c",f->data);if(f->ltag=1&&f->lchild!=NULL)printf("%c%c"

46、;,f->lchild->data,f->data);if(f->ltag=1&&f->rchild!=NULL&&f->rtag=1)printf("%c",f->rchild->data);else if(f->rchild!=NULL&&f->rtag=1)printf("%c%c",f->data,f->rchild->data);printf("n");if(f->ltag!=1) PrintI

47、ndex(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;elseif(point->ltag!=1)point1=SearchChild(point->lchild,findnode);if(point1!=NULL)return point1;if(point

48、->rtag!=1)point2=SearchChild(point->rchild,findnode);if(point2!=NULL)return point2;return NULL;elsereturn NULL;Bithptr *SearchPre(Bithptr *point,Bithptr *child)Bithptr *point1,*point2;if(point!=NULL)if(point->ltag!=1&&point->lchild=child)|(point->rtag!=1&&point->rch

49、ild=child)return point;elseif(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)return point2;return NULL;elsereturn NULL;void Insert(Bithptr *root)char ch;char c;Bithptr *p1,*child,*

50、p2;printf("请输入要插入的结点的信息:");scanf("%c",&c);scanf("%c",&c);p1=(Bithptr *)malloc(sizeof(Bithptr);p1->data=c;p1->lchild=NULL;p1->rchild=NULL;p1->ltag=0;p1->rtag=0;printf("输入查找的结点信息:");scanf("%c",&ch);scanf("%c",&ch);child=SearchChild