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

数据结构课程设计报告（2010 / 2011 学年第二学期）题目： 线索二叉树的应用专业班级： 09计算机（2）班学生姓名：学号：指导教师：设计周数： 19、20周设计成绩：2011年7 月4 日一、 需求分析：1、题目：线索二叉树的应用2、目的和任务：数据结构课程设计是计算机科学与技术专业集中实践性环节之一，是学习完数据结构课程后进行的一次全面的综合练习。其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。其任务为：要求：实现线索树建立、插入、删除、恢复线索的实现。3、数据输入输出：原始数据要求输入二叉树的7个结点：1234567，输出的是一个二叉树，这就实现了二叉树的建立过程。然后对二叉树进行线索化。对其进行插入：在7结点处插入结点8；删除：删除结点8;恢复线索等功能。进行二叉树的初始化，依次输入，以*结束：1234567*线索二叉树的应用*1、进行二叉树线索化2、进行插入操作3、删除4、中序输出5、线索输出0、退出请选择：1已经实现二叉树的线索化，可选择5查看线索4、设计算法测试用例：（1）输入结点:1234567;(2)对输入的二叉树进行线索化；（3）查看二叉树的中序线索输出：4-2-5-1-6-3-7；（4）在7结点处插入结点8，此时完成线索化恢复，查看二叉树的中序线索输出：4-2-5-1-6-3-8-7;(5)删除结点8，此时完成线索化恢复，发现结点8，ltag=1,rtag=1,查看二叉树的中序线索输出：4-2-5-1-6-3-7;(6)继续删除结点r，发现无该结点，则输入错误。二、数据结构的选择和概要设计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的后继结点为其右子树中最左下的结点。五、 心得体会本次课程设计，使我对数据结构这门课程有了更深入的理解。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。我的课程设计题目是线索二叉树的应用。刚开始做这个程序的时候，感到完全无从下手，甚至让我觉得完成这次程序设计根本就是不可能的，于是开始查阅各种资料以及参考文献，之后便开始着手写程序，写完运行时有很多问题。特别是实现线索二叉树的删除运算时很多情况没有考虑周全，经常运行出现错误，但通过同学间的帮助最终基本解决问题。在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对vc有了更深入的了解。数据结构是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。上机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教学内容的目的；另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。此外，还有更重要的一点是：机器是比任何教师更严厉的检查者。因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。 总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。六、测试结果及其分析如图1所示，初始化输入二叉树，实现线索化，查看线索输出： 图1如图2所示，在7结点处插入结点8，恢复线索化，查看中序线索输出为： 图2如图3所示，删除结点8，恢复线索化，查看中序线索输出为： 图3如图4所示，删除结点r，发现无该结点，则输出为： 图4七、参考文献（1）严慰敏 编数据结构习题集清华大学出版社（2）胡学军 编数据结构高等教育出版社附录：源程序：#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&1!=child-rtag)/孩子结点左右都有/*pre-lchild=child-lchild;s=child-rchild;while(