线索二叉树的运算数据结构与算法课程设计报告.docx
《线索二叉树的运算数据结构与算法课程设计报告.docx》由会员分享，可在线阅读，更多相关《线索二叉树的运算数据结构与算法课程设计报告.docx（37页珍藏版）》请在冰点文库上搜索。
线索二叉树的运算数据结构与算法课程设计报告
合肥学院
计算机科学与技术系
课程设计报告
2009～2010学年第二学期
课程
数据结构与算法
课程设计名称
线索二叉树的运算
学生姓名
侯山虎
学号
0804012006
专业班级
08计本
（2）班
指导教师
王昆仑张贯虹
2010年6月
一、问题分析和任务定义
（1）题目：
线索二叉树运算:
线索二叉树的应用，实现线索二叉树的建立、插入、删除、恢复线索。
（2）任务定义：
此题目是线索二叉树的一系列操作问题。
首先就要明白线索二叉树是什么，利用二叉链表的空指针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继，这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
（3）分析:
该任务是关于线索二叉树的运算，其中的基本运算应基于二叉树，但又有所不同，首先应解决的问题有：
1，线索二叉树是如何建立的，是通过二叉树来实现线索化，还是直接进行线索化的输入。
若由二叉树建立而来，该二叉树应如何输入，对于具体的二叉树应该使初使用者明白输入的格式。
2，该程序重点内容是有关于线索二叉树的插入和删除，在进行具体的操作时，规则是什么，依照什么原则。
3，在线索恢复中，依照插入删除后的二叉树结构，应该如何设计，是单独恢复，还是在两个重点程序中直接恢复线索。
4，对于插入，删除，恢复线索等，其结果是否符合预定的目标，须由自己判定。
由此，可以给出初步的分析：
A。
依照书上的相关内容和二叉树的定义，线索二叉树应该是在二叉树依照一定格式输入完毕后，对其进行线索化，线索化初步选定为中序线索化，然后线索化的结果进行输出。
B、插入中，首先就要考虑要怎样在二叉树中插入结点。
要插入结点，那么首先就应该考虑要在那里插入结点，那么就引入了结点的查找问题。
结点的查找将建立一个独立的子函数。
找到了结点的位置以后，由于目标节点有左右子树，设计两种情况，选择后就要考虑怎么插入了。
若选择了左子树后，目标节点又有两种情况：
一是已经有左子树，二是没有左子树，此时根据相应的情况，设计正确的操作。
在删除中也有类似的操作，不同的是在删除的过程中，因为要考虑被删除结点的左右子树的连接问题，必须知道要查找结点的父亲结点。
那么就需要另外一个子函数来查找孩子结点的父亲结点。
被删除结点和其父亲结点确定以后，就要考虑删除过程中的各种情况。
C、恢复线索过程中，由于和插入删除操作分离后考虑的过程复杂，并且从设计的目标来说应该是要在删除和插入的过程中实现对线索的恢复，故选择了插入删除中直接恢复线索。
D、在输出中，输出的操作分为两个一是专门用于二叉树的输出判别是否是要线索化的二叉树，此时用中序输出来体现二叉树的结点情况。
二是以输出线索来观察在各种操作的过程中线索的变化情况。
（4）测试用例：
其中@为虚节点，#为结束标记：
1.输入数据：
abc@d#完全二叉树
插入结点为信息为t；
插入的位置在点：
c
删除结点为t；
插入删除完成后得：
线索输出得：
b->d->a->c->
2.输入数据：
abcde@f#
插入结点为r;
插入的位置在b点，没有左孩子的情况
删除结点为d;
插入删除完成后得：
线索输出得：
b->r->a->c->
二、数据结构的选择和概要设计
（1）数据结构的选择：
因为此程序就是对二叉树进行各种操作，所以程序中必然使用的是树形结构。
在将树存储到计算机中时，就有了为存树而使用的存储结构。
因为对线索有大量的操作，所以选择链接存储结构。
在存储的过程中还使用了队类型的数据结构。
队的定义为：
BItree*Q[maxlen];//存放建树过程中的每个结点的指针
树的结点类型定义为：
Typedefstructnode{
Intltag,rtag;//用来指示指针域指的为孩子还是前驱或后继
chardata;//存放结点信息
structnode*lchild,*rchild;//记录孩子结点信息
}Bithptr;
结构图如图1为：
ltagdatartag
lchildrchild
图1结构图
二叉树的存储结构如图2:
图2二叉树的存储结构
（1）数据选择原因：
要存储树在计算机中，为了使用链接存储结构，就要对结点进行设计。
要存储结点信息就要有data域来存储信息，并分别设有左右孩子指针域分别记录此结点的左右孩子指针，使在建树的过程中每个结点的左右孩子指针指向其左右孩子，实现整个二叉树的建立。
这样的存储结构对于二叉树的存储已经足够，但是此程序处理的是线索二叉树。
在存储上就要为结点加上标志域，分别用来指示其指针是指向孩子还是前驱或后继。
当tag标志为0时，表示指针指向的是该结点的左右孩子，当tag标志为1时，表示指向的是该结点的前驱或后继。
（2）概要设计：
在程序中设计有完成各种功能的函数。
二叉树的建立函数：
BiThrNode*creat（BiThrNode*T）
中序遍历函数：
voidinorder（BiThrNode*T）
中序线索化函数：
voidPreThread（BiThrNode*root）
输出线索函数：
voidInorder（BiThrNode*T）
查找孩子指针函数：
BiThrNode*SearchChild（BiThrNode*T,charkey_name）
查找父亲指针函数：
BiThrNode*SearchPre（BiThrNode*T,BiThrNode*key）
插入函数：
voidInsert（BiThrNode*root）
删除函数：
BiThrNode*Delete（BiThrNode*t）
主函数：
voidmain（）;
（4）主要算法和结构流程图：
程序的模块结构如图3
插入函数
查找孩子指针函数
查找父亲指针函数
二叉树的建立函数
中序遍历函数
中序线索化函数
删除函数
输出线索函数
退出
结束
输出头指针
图4：
开始
建队并置空
、
输入结点数据
判断是否为结束
Y
输出头指针
N
判断是否为空
NY
建立结点
结束
加入队中
是否为头结点
Y
N
节点是否为空
Y
连接给对头
N
将节点给左右子树
是否为右孩子
N
队头指针加一
Y
图4树的建立函数如图
是否找到此点
查找插入点结点指针
插入函数流程图如图5：
开始
输入要插入点信息
查找插入点结点指针
结点是否有左子树结点
Y1Y2
直接插入为此结点的右结点
恢复线索1
直接插入为此结点的左结点
恢复线索2
结束
图5插入函数流程图如图
输入删除结点信息
开始
删除函数流程图如图6
查找结点信息
查找父亲结点
是否为父结点左孩子
YN
左右孩子都有
有左孩子没右孩子
有右孩子没左孩子
没有左右孩
把右子树接到左子树的最右下结点的右子树
左右孩子都有
有左孩子没右孩子
没有左右孩子
有右孩子没左孩子
把左孩子作为头结点
把右孩子作为头结点
直接删除
结点右子树接为左子树的最右下结点的右子树
把左孩子作为父结点左孩子
直接删除
把右孩子作为父结点左孩子
恢复线索
结束
图6删除函数流程图
三、详细设计和编码
（1）创建二叉树：
1、分析：
建立一个二叉链表，需要按照某种顺序依次输入二叉树中的结点，且该输入顺序必须隐含结点间的逻辑结构的信息。
这个建立依照层次关系由上往下，由左往右。
以@表示空结点，以#表示结束的标志。
2、实现：
在函数中设置一队列，该队列是一个指针类型的数组，保存已输入的结点的地址。
使队头指针front指向当前需要与孩子建立链接的父亲结点，队尾指针rear指向当前输入的结点。
若rear为偶数，则该结点为父结点的左孩子，若rear为奇数，则为父结点的右孩子。
若父结点或孩子结点为虚结点，则无需链接。
若父结点与其两个孩子结点链接完毕，则使front指向下一个等待链接的父结点。
4、主要过程：
BiThrNode*q[maxlen];
BiThrNode*creat（BiThrNode*T）//创建二叉树
{charch;
intfront=1,rear=0;
BiThrNode*s;
T=NULL;
ch=getchar（）;
while（ch!
='#'）{//当没有结束输入时
s=NULL;
if（ch!
='@'）
{s=（BiThrNode*）malloc（sizeof（BiThrNode））;
s->data=ch;
s->ltag=0;s->rtag=0;//先置0，在线索化中重新设置
s->lchild=NULL;
s->rchild=NULL;}
rear++;
q[rear]=s;
if（rear==1）T=q[rear];
else{
if（s!
=NULL&&q[front]!
=NULL）
if（rear%2==0）//根从1开始，当为2的倍数时，为左子树
q[front]->lchild=s;
else//余1时，为右子树
q[front]->rchild=s;
if（rear%2==1）//右子树已输入完毕，父亲节点往下移
front++;}
ch=getchar（）;}
returnT;
}
5、建树图示如图7：
0123456
图7建树图示
（2）二叉树线索化：
1、分析：
线索过程必须要按照一定的顺序来进行。
2、实现：
要实现线索化，就要知道结点*pre是结点*p的前驱，而*p是*pre的后继。
这样，当遍历到结点*p时，可以进行，若*p有空指针域，则将相应的标志置1；若*p的左线索标志已经建立（p->ltag==1），则可使其前驱线索化,令p->lchild=pre；若*pre的左线索标志已经建立（pre->rtag==1），则可使其后继线索化，令pre->rchild=p;
3.具体实现：
BiThrNode*pre=NULL;
voidPreThread（BiThrNode*root）//中序线索化算法，函数实现
{
BiThrNode*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）;
}
}
（3）二叉树中插入结点
1、方法：
在树中插入一个结点，就必须要以一定的规则来进行插入。
找到要插入的节点的父节点，然后选择是左孩子是右孩子插入，在看要插入的位置是否已经有其他节点，若有节点，则将要插入的结点作为该结点的前驱插入树中。
若没有，则直接插入。
2、查找：
在查找中，由于采用非递归形式会引入栈的操作，其麻烦程度有所不值，故依照中序线索输出，可以得到线索化后可以用的查找功能。
3、查找函数实现：
BiThrNode*SearchChild（BiThrNode*T,charkey_name）//查找孩子结点函数
{
BiThrNode*p,*q;
if（T!
=NULL）
{
if（T->data==key_name）//找到时，直接返回
returnT;
elseif（T->ltag!
=1）//左孩子不为空，进入递归
{
p=SearchChild（T->lchild,key_name）;
if（p!
=NULL）
returnp;}
if（T->rtag!
=1）//右孩子不为空,进入递归
{
q=SearchChild（T->rchild,key_name）;
if（q!
=NULL）
returnq;}
returnNULL;
}
else
returnNULL;
}
4、插入方法：
在一棵树中插入一个结点，因为插入的位置不同，就对应着不同的插入情况。
通过分析总结出各种情况：
插入结点有左（右）孩子：
直接将节点插入到目标位置，
若该位置已有节点，则插入节点作为已有节点的父亲节点，若没有，直接插入，同时，对插入后的二叉树进行线索化。
5、具体实现：
voidInsert2（BiThrNode*p,BiThrNode*r）//右孩子插入
{BiThrNode*s;
if（p->rtag==0）//当目标结点有右孩子的时候
{
s=p->rchild;//保存右孩子，设置r的后继
r->rchild=s;//后继化
r->rtag=0;
r->ltag=1;
r->lchild=p;//连接
p->rchild=r;//前驱化
s->lchild=r;}
else//当目标结点没有右孩子的时候
{
r->rchild=p->rchild;//前驱化
r->rtag=1;
p->rchild=r;
p->rtag=0;
r->lchild=p;
r->ltag=1;}
printf（"插入结点操作已经完成，并同时完成了线索化的恢复\n"）;
}
voidInsert1（BiThrNode*p,BiThrNode*r）//左孩子插入
{BiThrNode*s;
if（p->ltag==0）//当目标结点有左孩子的时候,接到左孩子最右下端
{s=p->lchild;
r->lchild=s;//前驱化
r->ltag=0;
r->rchild=p;//后继化
r->rtag=1;
p->lchild=r;
s->rchild=r;
}
else//当目标结点没有左孩子的时候，直接接入
{r->lchild=p->lchild;//前驱化
r->ltag=1;
p->lchild=r;
p->ltag=0;
r->rchild=p;
r->rtag=1;
}
printf（"插入结点操作已经完成，并同时完成了线索化的恢复\n"）;
}
6、图形显示：
如插入abc@d#
中序为a->b->c->d->
插入的结点为：
g要插入的位置为：
d
建树后，结点的线索变化如图8和图9；
其中虚线为待插结点在插入过程中将要变化的线索
a
g^^dvvv^^^^^^
c
^b
待插入元素
d
图8结点的线索变化
（1）
则插入结点后的顺序为：
b->g->d->a->c->
a
c
^b
g
d
图9结点的线索变化
（2）
（4）删除结点函数
1、分析：
要在函数中删除一个结点，也要考虑各种不同的情况。
在删除结点之前也要先找到要删除的点，就调用查找孩子结点函数BiThrNode*SearchChild（BiThrNode*T,charkey_name）找到其结点的指针。
再后面的操作就是怎样删除了，就发现在删除过程中涉及的指针变换需要父亲结点的指针，所以就调用查找父亲结点BiThrNode*SearchPre（BiThrNode*T,BiThrNode*key）来查找该结点的父亲结点指针。
2、删除具体情况：
1）.当结点是父亲结点的左孩子时
1.若孩子结点没有左右孩子：
则直接删除；
2.若孩子结点有左孩子没右孩子：
则将孩子结点的左孩子给父亲结点的左孩子；
3.若孩子结点有右孩子没左孩子：
则将孩子结点的右孩子给父亲结点的左孩子；
4.若孩子结点左右孩子都有：
将左孩子上提，孩子结点的左子树的右子树接到孩子结
点的右子树的最左下结点的左子树，再将孩子结点的右子树接到孩子结点左子树的
右子树。
2）.当结点是父亲结点的右孩子:
1若孩子结点没有左右孩子：
则直接删除；
2.若孩子结点有左孩子没右孩子：
则将孩子结点的左孩子给父亲结点的右孩子；
3.若孩子结点有右孩子没左孩子：
则将孩子结点的右孩子给父亲结点的右孩子；
4.若孩子结点左右孩子都有：
将右孩子上提，将孩子结点的右子树的左子树接到孩子
结点的左子树的最右下结点的右子树，再将孩子结点的左子树接到孩子结点右子树
的左子树。
3、具体实现：
（只列出孩子结点是父结点的左子树的情况）
孩子结点无左右
if（child==pre->lchild||child==pre）//是父亲结点的左孩子
{
if（child->ltag==1&&child->rtag==1）//孩子结点无左右
{
pre->lchild=child->lchild;//child结点后继指向pre,只要保存前驱
pre->ltag=1;//原来是0
free（child）;
}
elseif（child->ltag!
=1&&child->rtag==1）//孩子结点有左无右
{
pre->lchild=child->lchild;//把child左孩子上提
s=child->lchild;//查找child左孩子的最右下端节点（往下）
while（s->rchild）//该节点是child的前驱，保存child后继
s=s->rchild;
s->rchild=child->rchild;//保存child后继，s右标为1
free（child）;
}
elseif（child->ltag==1&&child->rtag!
=1）//孩子结点有右无左
{
pre->lchild=child->rchild;//把右孩子上提
s=child->rchild;//查找child的后继节点，位置在右孩子的最左下端
while（s->lchild!
=NULL）
s=s->lchild;
s->lchild=child->lchild;//把child前驱给s保存,s左标为1
free（child）;
}
elseif（child->ltag!
=1&&child->rtag!
=1）//孩子结点左右都有
{
pre->lchild=child->lchild;//child左孩子上提到child位置
s=child->rchild;//child左孩子的右子树会与child右子树冲突
while（s->lchild）
s=s->lchild;
s->lchild=child->lchild->rchild;//若child->lchild右子树非空,把child的左孩子的右子树接到孩子
//右子树的最左下结点
if（child->lchild->rtag!
=1）//child->lchild右子树非空，此时s->ltag本为1
s->ltag=0;
q=child->lchild;
while（q->rchild!
=NULL）
q=q->rchild;
q->rchild=s;//把q的后继指到s上
child->lchild->rchild=child->rchild;//child左孩子的右子树设置
child->lchild->rtag=0;//原本不知是否为0，但可以一起考虑
free（child）;
}
4、图形显示如图10和图11：
如删除结点g
中序为:
b→g→d→a→c→
删除后:
b→d→a→c→
c
^b
a
g
d
图10图形显示删除结点g
图11图形显示删除结点b
四．上机调试
在调试时，按照原有的思路，查找二叉树中目标节点，用的是出栈和入栈相关操作，但是在具体设计时，遇到的问题有点复杂，结果是在循环时找到了问题所在，由于本身思想的设计就有问题，重新思考了一下，感觉比较麻烦，重新利用线索后二叉树输出函数改出递归遍历，在插入删除时，具体情况具体对待，分出不同的情况，插入删除操作中，规则是咨询了王教授，要求是自己设计，于是选择了不改变线索为原则，和下面的恢复线索可以对照着完成，
在完成时，由于设计好了情况与应对操作，故总体上能够完成，在细节时，参考了《数据结构-c语言描述》.
五、测试结果及分析
程序运行后
1、建立线索二叉树（见下图）
图12建立线索二叉树
2、对线索二叉树进行插入操作（见下图）
图13线索二叉树的插入
3、对线索二叉树进行删除操作（见下图）
图14线索二叉树删除操作
分析：
由以上结果均符合预期的目标，成功完成。
六、用户使用说明
本程序是在VC++6.0中编写，程序运行环境：
DOS
根据程序的提示即可完成文本编辑器的各项功能。
其中具体的操作可依照程序运行时的说明。
七、参考文献
王昆仑、李红。
《数据结构与算法》。
北京：
中国铁道出版社。
八、附录
#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
#defineNULL0
#definemaxlen20
typedefstructnode{
chardata;
structnode*lchild,*rchild;/*左右孩子子树*/
intltag,rtag;
}BiThrNode;
BiThrNode*q[maxlen];
BiThrNode*creat（BiThrNode*T）//创建二叉树
{charch;
intfront=1,rear=0;
BiThrNode*s;
T=NULL;
ch=getchar（）;
while（ch!
='#'）{//当没有结束输入时
s=NULL;
if（ch!
='@'）
{s=（BiThrNode*）malloc（sizeof（BiThrNode））;
s->data=ch;
s->ltag=0;s->rtag=0;//先置0，在线索化中重新设置
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
q[rear]=s;
if（rear==1）T=q[rear];
else{
if（s!
=NULL&&q[front]!
=NULL）
if（rear%2==0）//根从1开始，当为2的倍数时，为左子树
q[front]->lchild=s;
else//余
升级会员 