线索二叉树的运算程序报告.doc

一、 问题分析和任务定义：1、题目：线索二叉树的运算2、要求和任务：在这个问题中，要解决的任务是：实现线索二叉树的建立、插入、删除、恢复线索的实现.n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。而在此次课程设计中，采用的是中序线索二叉树。3、原始数据的输入、输出格式：原始数据要求输入二叉树的7个结点：abcdefg，输出的是一个二叉树，这就实现了二叉树的建立过程。然后对二叉树进行线索化。对其进行插入：在b结点处插入结点w；删除：删除结点e;恢复线索等功能。进行二叉树的初始化，依次输入：abcdefg线索二叉树的应用*1、进行二叉树线索化2、进行插入操作3、删除4、中序输出5、线索输出0、退出请选择：1已经实现二叉树的线索化，可选择5查看线索4、设计算法测试用例：（1）输入结点:abcdefg;(2)对输入的二叉树进行线索化；（3）查看二叉树的中序线索输出：d-g-b b-e-a a-f-c；（4）在b结点处插入结点w，此时完成线索化恢复，查看二叉树的中序线索输出：d-g g-w-b b-e-a a-f-c;(5)删除结点e，此时完成线索化恢复，发现结点b，ltag=1,rtag=1,查看二叉树的中序线索输出：b-a d-g g-w-b a-f-c;(6)继续删除结点r，发现无该结点，则输入错误。abcdefg（1）输入结点，创建二叉树abcdefg（2）线索化二叉树abcdegwf(3)在b点处插入结点wacbdgwf（4）删除结点e二、数据结构的选择和概要设计1、数据结构二叉树是由n（n=0）个结点组成的有限集合，其中：（1）当n0时，为空二叉树。（2）当n0时，有且仅有一个特定的结点，称为二叉树的根，不相交的子集，其中每一个子集本身又是一棵二叉树，分别称为左子树和右子树。线索化是将二叉树转换成线索二叉树的过程。按某种遍历将二叉树线索化，只需在遍历过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继结点。（1）线索二叉树的结点的结构如下：ltaglchilddatartagrchild约定：Ltag=0 /表示lchild域指示该结点的左孩子Ltag=1 /表示lchild域指示该结点的前驱Rtag=0 /表示rchild域指示该结点的右孩子Rtag=1 /表示rchild域指示该结点的后继 (2)线索链表中结点类型说明： Typedef char datatype; Typedef struct node Int ltag,rtag; Datatype data; Struct node *lchild,*rchild;bithptr;(3)线索化算法：结点*pre 是结点*p的前驱，而*p是*pre的后继。这样，当遍历到结点*p时，可以进行以下三步操作：1）若*p有空指针域，则将相应的标志置1.2）若*p的左线索标志已经建立（p-ltag=1）,则可使其前驱线索化，令p-lchild=pre.3)若*pre的右线索标志已经建立（pre-rtag=1）,则可使其后继线索化，令pre-rchild=p.如此，二叉树的线索化可以在二叉树的遍历过程完成，该算法应为相应顺序的遍历算法的一种变化形式。（4）二叉链表的建立：其算法描述如下：Bitree *crt_bt_pre(bitree *bt) Char ch; Ch=getchar( ); If(ch=) Bt=null; Else Bt=(bitree *)malloc(sizeof(bitree); Bt-data=c; Bt-lchild=crt_bt_pre(bt-lchild); Bt-rchild=crt_bt_pre(bt-rchild); Return(bt);2、设计思想建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0; （2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。 （3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。结点插入算法：由线索二叉树的定义易知插入的节点定是个叶子节点，需注意线索的修改，可分为两种情况：1）：插入的节点t是右儿子，t的中序后继是其父亲的中序后继，中序前驱是其父亲。2）：插入的节点t是左儿子，t的中序前驱是其父亲的中序前驱，中序后继是其父亲。结点删除算法：删除的情况与搜索二叉树的删除的类似1）：删除的节点p是叶子节点，直接删除，修改其父亲的线索。2）：删除的节点p有一个儿子，p有一个左儿子，以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继，中序前驱不变；p有一个右儿子，以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱，中序后继不变。3）：删除的节点p有二个儿子，转化为叶子节点或只有一个儿子节点的删除。3、流程图开始定义二叉树T=CreatTree( )1=i输入i!=0输入选择菜单输入ii=1preThred(T)i=2Insert(T)i=3DeleteNode(T)i=4Inorder(T)退出三、 详细设计和编码1、主函数void main()Bithptr *T;int i;/system(color 1a);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 请选择:);scanf(%d,&i);printf(n);switch(i)case 1:PreThread(T);printf(t已经实现二叉树的线索化n);printf(n);break;case 2:Insert(T);printf(n);break;case 3:T=DeleteNode(T);printf(n);break;case 4:Inorder(T);printf(n);break;case 5:PrintIndex(T);break;case 0:exit(1);default:printf(errornt请继续选择:);2、中序线索化算法：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=NULL) /后继结点前驱线索化p-rtag=1;pre=p;PreThread(p-rchild);四、 上机调试做这个课程设计，想到用各种数据结构和主要的思想，反反复复的修改和改进，花费了好几天的时间。正式着手写程序只用了大概一天的时间，但是调试的时候却用了好几天。1、当用二叉链表作为二叉树的存储结构时。可以方便地找到某个结点的左右孩子，但一般情况下，无法直接摘到该结点在没中遍历序列中的前驱和后继接待你。为了解决这个问题，所以采用线索二叉树。但是在编写过程中，忽略了线索二叉树的改变，没有改变空的左孩子指针域，而后再看了一遍数据结构的相关指导教材，发现了错误，及时改正，将空的左孩子指针域改为指向其前驱。2、在进行线索化的编写过程中，出现了问题。开始只能对几点进行前驱线索化，而不能进行后继线索化。为此做了相应调整：（1）若*p有空指针域，则将相应的标志置1。 （2）若*p的左线索标志已经建立，则可使其前驱线索化，令p-lchild=pre。 （3）若*pre的右线索标志已经建立，则可使其后继线索化，令pre-rchild=p。 3、在编写中序线索二叉树中的后继查找算法时，只编写了其中一种情况，应该有两种情况(1)*p的右子树为空，则p-rchild为右线索，指向*p的后继结点。（2）若*p的右子树非空，根据中序遍历的顺序，*p的后继结点为其右子树中最左下的结点。五、 心得体会 由于暑假忙于认知实习,几乎遗忘了数据结构课程设计,于是在开学后的两个星期内匆忙但不失认真的完成了本人的课程设计.在此期间遇到的困难挫折无数,最终我还是挺过去了.由于对C语言程序设计有一定的实践基础,所以本人在实践的过程中获益不浅.C语言是大一开的课程,所以这个学期并没怎么看过,当要开始设计的时候,还真不知从哪下手!结果第一次的上机,我傻坐着不知道该做什么。回去以后我就重新复习了一遍C语言的内容,发觉自已有许多知识都遗忘了，脑子里对C语言的内容几乎是一遍空白，于是在温习过后便开始做题!一开始做题，也是有点模糊，没有一点做题的思路，在指导老师的指导下，我慢慢的进入状态，设计出对解决问题的思路，但是老师说我的思路还存在问题并且和我详细的说明，我回去后把数据结构书本是上关于线索二叉树的内容又仔细的琢磨了一遍后设计出更好的解题思路。我的设计题目是线索二叉树的应用，包括线索二叉树的建立，插入，删除以及恢复。经过一星期的努力，我基本上完成了大半个程序，但是总是有很多错误出现，有好多是些小问题，这都是我们粗心大意造成的，所以设计程序一定要仔细，不容一点的马虎。当然也有大问题，关于线索二叉树的插入和删除为什么不能插入或删除头节点，这是我遇到的最大困难了，在我百思不得解决的时候，最终在同学的帮助下和老师的指导下，让我在规定的时间内完成了我的课程设计。这次课程设计,让我重新掌握了C语言,而且还得到了用C语言解决实际问题的宝贵经验!六、测试结果及其分析如图1所示，初始化输入二叉树，实现线索化，查看线索输出： 图1如图2所示，在b结点处插入结点w，恢复线索化，查看中序线索输出为： 图2如图3所示，删除结点e，恢复线索化，查看中序线索输出为： 图3如图4所示，删除结点r，发现无该结点，则输出为： 图4七、参考文献 1. 王昆仑、李红。 数据结构与算法。 中国铁道出版社。 2. 郑莉。 C语言程序设计（第三版）学生用书。 清华大学出版社。 3. 刘振安。 C程序设计课程设计。 机械工业出版社。 4. 吴乃陵。 C程序设计。 高等教育出版社。 5. 李春葆。 C程序设计学习与上机实验指导。 北京：清华大学出版社。 6. 范辉。 Visual C+6.0程序设计简明教程。 高等教育出版社。 7. 李龙。 C+程序设计实训教程。 北京：清华大学出版社。 8. 洪国胜。 C+ Builder程序设计轻松上手。 北京：清华大学出版社。 9. 宁国正。 数据结构（C语言版）。 南京：东南大学出版社。2000年6月第一版。 10.严尉敏。 数据结构（C语言版）。 北京：清华大学出版社，1997年4月第一版。 11.胡学钢。 数据结构算法设计指导。 北京：清华大学出版社，1999年第一版。 12.刘大有。 数据结构（面向21世纪课程教材）。 北京：高等教育出版社。 13. 明日科技。 Visual C程序开发范例宝典。 北京：人民邮电出版社。附录：源程序：#include #include malloc.h#include windows.h#define maxsize 30 /规定树中结点的最大数目typedef struct node /定义数据结构int ltag,rtag; /表示child域指示该结点是否孩子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);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;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)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-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(【%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); /如果此结点有前驱也有后继，就输出后继else 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 *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;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!=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,*p2;printf(请输入要插入的结点的信息:);scanf(%c,&c);scanf(%c,&c);p1=(Bithptr *)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);system(pause);return ;else printf(发现结点%cn,child-data);if(child-ltag=0) /当孩子结点有左孩子的时候p2=child;child=child-lchild;while(child-rchild&child-rtag=0) /找到左子树下，最右结点child=child-rchild;printf(发现结点%cn,child-data);p1-rchild=child-rchild; /后继化p1-rtag=1;child-rtag=0;child-rchild=p1; /连接p1-lchild=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(输入查找的结点信息:);ch=getchar();ch=getchar();child=SearchChild(t,ch);printf(发现结点:%cn,child-data);printf(ltag=%d,rtag=%dn,child-ltag,child-rtag);pre=SearchPre(t,child);printf(发现结点:%cn,pre-data);if(NULL=child)printf(没有找到结点:);return t;system(pause);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-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-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;free(child);else if(1!=child-ltag&1!=child-rtag)/孩子结点左右都有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-rchild;q-rchild=s;child-lchild-rchild=child-rchild;child-lchild-rtag=0;free(child);if(child=pre-rchild) /是父亲结点的右孩子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)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(child);else if(1!=child-ltag&