数据结构线索二叉树的应用精选.doc

数据结构课程设计报告 （2010 / 2011 学年第?二?学期） 题????目： 线索二叉树的应用 专业班级： 09计算机（2）班 学生姓名： 学????号： 指导教师：?? 设计周数： ????19、20周 设计成绩： 2011???年?7 月?4 日 需求分析： 1、题目：线索二叉树的应用 2、目的和任务： 《数据结构》课程设计是计算机科学与技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。 其任务为：要求：实现线索树建立、插入、删除、恢复线索的实现。 3、数据输入输出：原始数据要求输入二叉树的7个结点：，输出的是一个二叉树，这就实现了二叉树的建立过程。然后对二叉树进行线索化。对其进行插入：在7结点处插入结点8；删除：删除结点8;恢复线索等功能。 进行二叉树的初始化，依次输入，以*结束： * 线索二叉树的应用 **************************** 1、进行二叉树线索化 2、进行插入操作 3、删除 4、中序输出 5、线索输出 0、退出 请选择：1 已经实现二叉树的线索化，可选择5查看线索 4、设计算法测试用例：（1）输入结点:;(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） 约定： 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））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指向下一个等待链接的父结点。 二叉树的中序