线索二叉树的运算数据结构与算法课程设计报告Word格式.docx
《线索二叉树的运算数据结构与算法课程设计报告Word格式.docx》由会员分享,可在线阅读,更多相关《线索二叉树的运算数据结构与算法课程设计报告Word格式.docx(37页珍藏版)》请在冰点文库上搜索。
(4)测试用例:
其中@为虚节点,#为结束标记:
1.输入数据:
abc@d#完全二叉树
插入结点为信息为t;
插入的位置在点:
c
删除结点为t;
插入删除完成后得:
线索输出得:
b->
d->
a->
c->
2.输入数据:
abcde@f#
插入结点为r;
插入的位置在b点,没有左孩子的情况
删除结点为d;
插入删除完成后得:
r->
二、数据结构的选择和概要设计
(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
队头指针加一
图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;
ltag=0;
s->
rtag=0;
//先置0,在线索化中重新设置
lchild=NULL;
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++;
}
}
returnT;
5、建树图示如图7:
0123456
图7建树图示
(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)//前驱结点后继线索化
if(p->
lchild==NULL)
{p->
ltag=1;
p->
lchild=pre;
}
rchild==NULL)//后继结点前驱线索化
rtag=1;
pre=p;
rchild);
(3)二叉树中插入结点
1、方法:
在树中插入一个结点,就必须要以一定的规则来进行插入。
找到要插入的节点的父节点,然后选择是左孩子是右孩子插入,在看要插入的位置是否已经有其他节点,若有节点,则将要插入的结点作为该结点的前驱插入树中。
若没有,则直接插入。
2、查找:
在查找中,由于采用非递归形式会引入栈的操作,其麻烦程度有所不值,故依照中序线索输出,可以得到线索化后可以用的查找功能。
3、查找函数实现:
BiThrNode*SearchChild(BiThrNode*T,charkey_name)//查找孩子结点函数
{
BiThrNode*p,*q;
if(T!
{
if(T->
data==key_name)//找到时,直接返回
returnT;
elseif(T->
ltag!
=1)//左孩子不为空,进入递归
p=SearchChild(T->
lchild,key_name);
if(p!
returnp;
if(T->
rtag!
=1)//右孩子不为空,进入递归
q=SearchChild(T->
rchild,key_name);
if(q!
returnq;
returnNULL;
else
4、插入方法:
在一棵树中插入一个结点,因为插入的位置不同,就对应着不同的插入情况。
通过分析总结出各种情况:
插入结点有左(右)孩子:
直接将节点插入到目标位置,
若该位置已有节点,则插入节点作为已有节点的父亲节点,若没有,直接插入,同时,对插入后的二叉树进行线索化。
5、具体实现:
voidInsert2(BiThrNode*p,BiThrNode*r)//右孩子插入
{BiThrNode*s;
rtag==0)//当目标结点有右孩子的时候
s=p->
rchild;
//保存右孩子,设置r的后继
r->
//后继化
lchild=p;
//连接
rchild=r;
//前驱化
lchild=r;
else//当目标结点没有右孩子的时候
rchild=p->
printf("
插入结点操作已经完成,并同时完成了线索化的恢复\n"
);
voidInsert1(BiThrNode*p,BiThrNode*r)//左孩子插入
ltag==0)//当目标结点有左孩子的时候,接到左孩子最右下端
{s=p->
lchild;
else//当目标结点没有左孩子的时候,直接接入
{r->
lchild=p->
6、图形显示:
如插入abc@d#
中序为a->
插入的结点为:
g要插入的位置为:
d
建树后,结点的线索变化如图8和图9;
其中虚线为待插结点在插入过程中将要变化的线索
a
g^^dvvv^^^^^^
c
^b
待插入元素
d
图8结点的线索变化
(1)
则插入结点后的顺序为:
g->
a
g
图9结点的线索变化
(2)
(4)删除结点函数
1、分析:
要在函数中删除一个结点,也要考虑各种不同的情况。
在删除结点之前也要先找到要删除的点,就调用查找孩子结点函数BiThrNode*SearchChild(BiThrNode*T,charkey_name)找到其结点的指针。
再后面的操作就是怎样删除了,就发现在删除过程中涉及的指针变换需要父亲结点的指针,所以就调用查找父亲结点BiThrNode*SearchPre(BiThrNode*T,BiThrNode*key)来查找该结点的父亲结点指针。
2、删除具体情况:
1).当结点是父亲结点的左孩子时
1.若孩子结点没有左右孩子:
则直接删除;
2.若孩子结点有左孩子没右孩子:
则将孩子结点的左孩子给父亲结点的左孩子;
3.若孩子结点有右孩子没左孩子:
则将孩子结点的右孩子给父亲结点的左孩子;
4.若孩子结点左右孩子都有:
将左孩子上提,孩子结点的左子树的右子树接到孩子结
点的右子树的最左下结点的左子树,再将孩子结点的右子树接到孩子结点左子树的
右子树。
2).当结点是父亲结点的右孩子:
1若孩子结点没有左右孩子:
则将孩子结点的左孩子给父亲结点的右孩子;
则将孩子结点的右孩子给父亲结点的右孩子;
将右孩子上提,将孩子结点的右子树的左子树接到孩子
结点的左子树的最右下结点的右子树,再将孩子结点的左子树接到孩子结点右子树
的左子树。
3、具体实现:
(只列出孩子结点是父结点的左子树的情况)
孩子结点无左右
if(child==pre->
lchild||child==pre)//是父亲结点的左孩子
if(child->
ltag==1&
child->
rtag==1)//孩子结点无左右
pre->
lchild=child->
//child结点后继指向pre,只要保存前驱
//原来是0
free(child);
elseif(child->
=1&
rtag==1)//孩子结点有左无右
//把child左孩子上提
s=child->
//查找child左孩子的最右下端节点(往下)
while(s->
rchild)//该节点是child的前驱,保存child后继
s=s->
rchild=child->
//保存child后继,s右标为1
=1)//孩子结点有右无左
//把右孩子上提
//查找child的后继节点,位置在右孩子的最左下端
lchild!
=NULL)
//把child前驱给s保存,s左标为1
=1)//孩子结点左右都有
//child左孩子上提到child位置
s=child->
//child左孩子的右子树会与child右子树冲突
lchild)
lchild->
//若child->
lchild右子树非空,把child的左孩子的右子树接到孩子
//右子树的最左下结点
=1)//child->
lchild右子树非空,此时s->
ltag本为1
s->
q=child->
while(q->
rchild!
q=q->
q->
//把q的后继指到s上
child->
//child左孩子的右子树设置
//原本不知是否为0,但可以一起考虑
4、图形显示如图10和图11:
如删除结点g
中序为:
b→g→d→a→c→
删除后:
b→d→a→c→
^b
图10图形显示删除结点g
图11图形显示删除结点b
四.上机调试
在调试时,按照原有的思路,查找二叉树中目标节点,用的是出栈和入栈相关操作,但是在具体设计时,遇到的问题有点复杂,结果是在循环时找到了问题所在,由于本身思想的设计就有问题,重新思考了一下,感觉比较麻烦,重新利用线索后二叉树输出函数改出递归遍历,在插入删除时,具体情况具体对待,分出不同的情况,插入删除操作中,规则是咨询了王教授,要求是自己设计,于是选择了不改变线索为原则,和下面的恢复线索可以对照着完成,
在完成时,由于设计好了情况与应对操作,故总体上能够完成,在细节时,参考了《数据结构-c语言描述》.
五、测试结果及分析
程序运行后
1、建立线索二叉树(见下图)
图12建立线索二叉树
2、对线索二叉树进行插入操作(见下图)
图13线索二叉树的插入
3、对线索二叉树进行删除操作(见下图)
图14线索二叉树删除操作
分析:
由以上结果均符合预期的目标,成功完成。
六、用户使用说明
本程序是在VC++6.0中编写,程序运行环境:
DOS
根据程序的提示即可完成文本编辑器的各项功能。
其中具体的操作可依照程序运行时的说明。
七、参考文献
王昆仑、李红。
《数据结构与算法》。
北京:
中国铁道出版社。
八、附录
#include"
stdio.h"
malloc.h"
stdlib.h"
#defineNULL0
#definemaxlen20
typedefstructnode{
chardata;
structnode*lchild,*rchild;
/*左右孩子子树*/
intltag,rtag;
}BiThrNode;
BiThrNode*q[maxlen];
else//余