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

《数据结构课程设计-线索二叉树的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计报告（2010/2011学年第 二 学期）题    目：线索二叉树的应用专业班级：09计算机（2）班学生姓名：学    号：指导教师：  设计周数：    19、20周设计成绩：2011   年 7月 4日一、需求分析：1、题目：线索二叉树的应用2、目的和任务：《数据结构》课程设计是计算机科学与技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。其任务为：要求：实现线索树建立、插入、删

2、除、恢复线索的实现。3、数据输入输出：原始数据要求输入二叉树的7个结点：1234567，输出的是一个二叉树，这就实现了二叉树的建立过程。然后对二叉树进行线索化。对其进行插入：在7结点处插入结点8；删除：删除结点8;恢复线索等功能。进行二叉树的初始化，依次输入，以*结束：1234567*线索二叉树的应用****************************1、进行二叉树线索化2、进行插入操作3、删除4、中序输出5、线索输出0、退出请选择：1已经实现二叉树的线索化，可选择5查看线索4、设计算法测试用例：（1）输入结点:1234567;(2)对输入的二叉树进行线索化；（3）查看二叉树的中序

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）当n＝0时，为空二叉树。（2）当n>0时，有且仅有一个特定的结点，称为二叉树的根，不相交的子集，其中每一个子集本身又是一棵二叉树，分

4、别称为左子树和右子树。线索化是将二叉树转换成线索二叉树的过程。按某种遍历将二叉树线索化，只需在遍历过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继结点。（1）线索二叉树的结点的结构如下：ltaglchilddatartagrchild约定：Ltag=0//表示lchild域指示该结点的左孩子Ltag=1//表示lchild域指示该结点的前驱Rtag=0//表示rchild域指示该结点的右孩子Rtag=1//表示rchild域指示该结点的后继(2)线索链表中结点类型说明：Typedefchardatatype;Typedefstructnode{Intltag,rt

5、ag;Datatypedata;Structnode*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）二叉链表的建立

6、：其算法描述如下：Bitree*crt_bt_pre(bitree*bt){Charch;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、设计思想建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需

7、添加虚结点，使其成为完全二叉树。关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0;（2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。（3）若父结点与其