文档介绍：数据结构课程设计报告
(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)当n=0时,为空二叉树。(2)当n>0时,有且仅有一个特定的结点,称为二叉树的根,不相交的子集,其中每一个子集本身又是一棵二叉树,分别称为左子树和右子树。线索化是将二叉树转换成线索二叉树的过程。按某种遍历将二叉树线索化,只需在遍历过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继结点。
(1)线索二叉树的结点的结构如下:
ltag
lchild
data
rtag
rchild
约定:
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、设计思想
建立二叉树(即指在内存中建立二叉树的存储结构),建立一个二叉链表,需按某种顺序一次输入二叉树中的结点,且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树,需添加虚结点,使其成为完全二叉树。
关键在于如何将新结点作为左孩子和右孩子连接到它的父