线索二叉树课程设计.docx
《线索二叉树课程设计.docx》由会员分享，可在线阅读，更多相关《线索二叉树课程设计.docx（30页珍藏版）》请在冰点文库上搜索。
线索二叉树课程设计
信息科学与技术学院
《数据结构》课程设计报告
题目名称：
线索二叉树的计算
学生姓名：
刘少博
学号:
**********
专业班级：
计算机科学与技术
指导教师：
高攀
2014年1月8
1、设计的目的与要求
此程序需要完成如下要求：
建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。
实现本程序需要解决以下几个问题：
1、如何建立线索二叉树。
2、如何实现线索二叉树的插入。
3、如何实现线索二叉树的删除。
4、如何实现线索二叉树恢复线索的实现。
此题目是线索二叉树的一系列操作问题。
首先就要明白线索二叉树是什么，利用二叉链表的空指针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继，这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
在这个问题中，要解决的任务是：
实现线索二叉树的建立、插入、删除、恢复线索的实现。
N个结点的二叉链表中含有n+1个空指针域。
利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（ThreadedBinaryTree）。
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
在此次课程设计中，采用的是中序线索二叉树。
摘要…………………………………………………………………………………………4
1、引言……………………………………………………………………………………5
2、设计任务与目的……………………………………………………………………5
3、设计方案与实施………………………………………………………………………5
1、总体设计…………………………………………………………………………5
2、详细设计…………………………………………………………………………7
3、程序清单…………………………………………………………………………13
4、程序调试与体会……………………………………………………………………24
5、运行结果（截图）…………………………………………………………………24
四、结论……………………………………………………………………………………27
五、致谢……………………………………………………………………………………27
六、参考文献………………………………………………………………………………27
摘要
随着人们生活水平的提高，计算机发展异常迅速。
如今，计算机已经深入到我们社会的各个领域，计算机的使用也已不再局限于科学计算，它已进入人类社会的各个领域并发挥着越来越重要的作用。
通过计算机对各类问题求解已经成为一种高效、快捷的方式。
树在计算机领域也得到了广方的应用，如在编译程序中，可以用树表示原程序的语法结构。
本次课程设计主要运用二叉树的一些特点，来实现线索二叉树的建立、插入、删除、恢复线索等等。
关键词：
二叉树，线索链表，线索化，线索。
Abstract
Keywords:
Binarytree,Clueslinkedlist,Cluesoptimization,Clues.
Aspeoplelivingstandardrise,computertoabnormaldevelopmentrapidly.Today,computershavedeeplyintoeveryfieldofoursociety,theuseofcomputersisnolongerlimitedtoscientificcomputing,itenteredthehumansocietyeachdomainandplaysamoreandmoreimportantrole.Throughcomputerforallkindsofproblemsolvinghasbecomeanefficient,quickway.Treesinthefieldofcomputeralsogotwidesquareapplications,suchasincompiler,canusethetreesaystheoriginalprogramgrammaticalstructures.
《数据结构》课程设计
--线索二叉树的计算
一、引言
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。
结构树在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。
树在计算机领域中也得到广泛应用，如在编译源程序时，可用树表示源程序的语法结构。
又如在数据系统库中，树型结构也是信息的重要组织形式之一。
一切具有层次关系的问题都可用树来描述。
二、设计目的与任务
通过本课程设计教学所要求达到的目的是：
建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。
三、设计方案
1、总体设计
首先建立二叉树，然后对二叉树进行线索化。
线索链表的结点结构
?
?
?
线索链表中的结点结构为：
图
（1）线索链表中的结点结构
中序线索二叉树的图示
图
（2）中序线索二叉树
建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。
对于一般的二叉树，需添加虚结点，使其成为完全二叉树。
关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。
可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。
（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针
rear指向当前输入的结点，初始：
front=1,rear=0;
（2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的
右孩子；若父结点和孩子结点为虚结点，则无需链接。
（3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。
二叉树的中序索化算法与中序历算法类似。
只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中前趋结点间线索。
该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。
结点*pre是结点*p的前趋，而*p是*pre的后继。
程序流程图:
图（3）程序流程图
2、详细设计
（1）建树算法：
1、分析：
建立一个二叉链表，需要按照某种顺序依次输入二叉树中的结点，且该输入顺序必须隐含结点间的逻辑结构的信息。
这个建立的方法，按完全二叉树的层次顺序，依次输入结点信息建立二叉链表的过程。
以@表示空结点，以#表示输入结束的标志。
2、算法思想：
依次输入结点信息，若其不是虚结点，则建立一个新结点。
若新结点是第一个结点，则令其为根结点，否则将新结点作为孩子链接到它的父亲结点上。
3、实现：
在函数中设置一队列，该队列是一个指针类型的数组，保存已输入的结点的地址。
使队头指针front指向当前与孩子建立链接的父亲结点，队尾指针rear指向当前输入的结点。
若rear为偶数，则该结点为父结点的左孩子，若rear为奇数，则为父结点的右孩子。
若父结点或孩子结点为虚结点，则无需链接。
若父结点与其两个孩子结点链接完毕，则使front指向下一个等待链接的父结点。
4、主要过程：
Bithptr*Q[maxsize];//建队为指针类型
Bithptr*CreatTree（）{
front=1;rear=0;//置空队
if（ch!
='@'）//不是虚结点，则建立结点
s=（Bithptr*）malloc（sizeof（Bithptr））;
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
s->rtag=0;
s->ltag=0;
if（s!
=NULL&&Q[front]!
=NULL）//孩子和双亲结点都不是虚结点
if（rear%2==0）Q[front]->lchild=s;
elseQ[front]->rchild=s;
if（rear%2==1）front++;//结点*Q[front]的两个孩子处理完，front+1
（2）线索化算法：
1、分析：
线索过程必须要按照一定的顺序来进行，在本程序中因为树的遍历过程使用的是中序遍历，所以为了方便，线索化的过程也是使用中序线索化。
2、方法：
按某种遍历顺序将二叉树线索化，只需要在遍历的过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继。
若其左子树为空，则将其左孩子域线索化，使其左孩子指针lchild指向其后继，并且ltag置1。
3、实现：
要实现线索化，就要知道结点*pre是结点*p的前驱，而*p是*pre的后继。
这样，当遍历到结点*p时，可以进行，若*p有空指针域，则将相应的标志置1；若*p的左线索标志已经建立（p->ltag==1），则可使其前驱线索化，令p->lchild=pre；若*pre的左线索标志已经建立（pre->rtag==1），则可使其后继线索化，令pre->rchild=p;
4、主要过程：
voidPreThread（Bithptr*root）
{
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、方法：
在树中插入一个结点，就必须要以固定的规则来进行插入。
在本程序中对树的输出使用了中序输出的方法，所以插入的时候使用的规则就是以中序输出为顺序，先查找到一个点，再将要插入的结点作为该结点的前驱插入树中。
如中序为：
→d→b→e→a→f→c→g
插入的结点为：
w要插入的位置为：
b
则插入结点后的顺序为：
→d→w→b→e→a→f→c→g
2、查找：
使用查找孩子指针函数来查找结点位置的指针。
在查找的过程中要处理好线索指针和孩子指针的关系，不能将线索也当作孩子处理了。
并且在循环的判断过程中，再不能使用以前的以空为结束语句，而是要用标志域来进行判断。
在查找的过程中，考虑到树的递归性质，所以将查找函数也设置为递归函数。
3、查找函数实现：
Bithptr*SearchChild（Bithptr*point,charfindnode）
{
Bithptr*point1,*point2;
if（point!
=NULL）
{
if（point->data==findnode）returnpoint;//找到结点的信息，返回指针
elseif（point->ltag!
=1）{//判断是否有左子树point1=SearchChild（point->lchild,findnode）;//递归
if（point1!
=NULL）
returnpoint1;
}
if（point->rtag!
=1）{//判断是否有右子树
point2=SearchChild（point->rchild,findnode）;//递归
if（point2!
=NULL）
returnpoint2;
}
returnNULL;
}
else
returnNULL;
}
4、插入方法：
在一棵树中插入一个结点，因为插入的位置不同，就对应着不同的插入情况。
通过分析总结出各种情况：
插入结点有左孩子时：
插入的方法是，找到左子树的最右下结点，将待插的结点插为其结点的右孩子。
插入结点没有左孩子时：
插入的方法是，直接将待插的结点插为其结点的左孩子。
5、插入实现：
（当结点有左子树时）
p2=child;
child=child->lchild;
while（child->rchild&&child->rtag==0）//左子树的最右下结点
child=child->rchild;
p1->rchild=child->rchild;//后继线索化
p1->rtag=1;
child->rtag=0;
child->rchild=p1;//连接结点
p1->lchild=child;//前驱线索化
p1->ltag=1;
（当结点没左孩子的时）
p1->lchild=child->lchild;//前驱化
child->ltag=0;
p1->ltag=1;
child->lchild=p1;
p1->rchild=child
p1->rtag=1;
6、图形显示：
如插入abcdefg#
中序为：
→d→b→e→a→f→c→g
插入的结点为：
w要插入的位置为：
b
建树后，结点的线索变化如图4和图5；
其中虚线为待插结点在插入过程中将要变化的线索
a
图（4）结点的线索变化图a
则插入结点后的顺序为：
→d→w→b→e→a→f→c→g
图（5）结点的线索变化图b
（4）删除结点函数
1、分析：
要在函数中删除一个结点，也要考虑各种不同的情况。
在删除结点之前也要先找到要删除的点，就调用查找孩子结点函数Bithptr*SearchChild（Bithptr*point,charfindnode）找到其结点的指针。
再后面的操作就是怎样删除了，就发现在删除过程中涉及的指针变换需要父亲结点的指针，所以就调用查找父亲结点函数Bithptr*SearchPre（Bithptr*point,Bithptr*child）来查找该结点的父亲结点指针。
2、删除方法：
考虑在删除的过程中的各种不同的情况，就要在程序的设计中进行不同的分类，进行不同的处理，考虑不同的处理过程。
通过总结可以知道各种不同的情况。
（当要删除结点是父亲结点的左孩子时）
若要删除结点没有左右孩子：
则直接删除；
若要删除结点有左孩子没右孩子：
则将要删除结点的左孩子给父亲结点的左孩子；
若要删除结点有右孩子没左孩子：
则将要删除结点的右孩子给父亲结点的左孩子；
若要删除结点左右孩子都有：
将要删除结点的左子树的右子树接到孩子结点的右子树的最左下结点的左子树，再将孩子结点的右子树接到孩子结点左子树的右子树。
（当要删除结点是父亲结点的右孩子时）
若要删除结点没有左右孩子：
则直接删除；
若要删除结点有左孩子没右孩子：
则将要删除结点的左孩子给父亲结点的右孩子；
若要删除结点有右孩子没左孩子：
则将要删除结点的右孩子给父亲结点的右孩子；
若要删除结点左右孩子都有：
将要删除结点的右子树的左子树接到孩子结点的左子树的最右下结点的右子树，再将孩子结点的右子树接到孩子结点右子树的左子树。
（当要删除结点是整个二叉树的头结点时）
若要删除结点没有左右孩子，则直接将空给头指针。
若要删除结点有左孩子没右孩子，则将孩子结点的左孩子作为头结点。
若要删除结点有右孩子没左孩子，则将孩子结点的右孩子作为头结点。
若要删除结点左右孩子都有，则将孩子结点的左孩子作为头结点，将孩子结点的右子树插入孩子结点的左子树的最右下结点的右子树。
3、实现：
（只列出要删除结点是父结点的左子树的情况）
要删除结点无左右
pre->lchild=child->lchild;
pre->ltag=1;
if（child->lchild!
=NULL）
if（child->lchild->rtag==1）child->lchild->rchild=pre;
要删除结点有左无右：
pre->lchild=child->lchild;
s=child->lchild;
while（s->rchild）
s=s->rchild;
s->rchild=child->rchild;
要删除结点有右无左：
pre->lchild=child->rchild;
s=child->rchild;
while（s->lchild）
s=s->lchild;
s->lchild=child->lchild;
if（child->lchild!
=NULL）
if（child->lchild->rtag==1）child->lchild->rchild=pre;
要删除结点左右都有：
pre->lchild=child->lchild;
s=child->rchild;
while（s->lchild）
s=s->lchild;
s->lchild=child->lchild->rchild;//把要删除结点的左孩子的右子树接到孩子右子树的最左下结点
if（child->lchild->rtag!
=1）s->ltag=0;
q=child->lchild;
while（q->rchild）
q=q->rchild;
q->rchild=s;
child->lchild->rchild=child->rchild;
child->lchild->rtag=0;
4、图形显示如图6：
如删除结点e
中序为：
→d→b→e→a→f→c→g
删除后：
→d→b→a→f→c→g
图（6）删除结点图示
3、程序清单
#include"stdio.h"
#include"malloc.h"
#definemaxsize20//规定树中结点的最大数目
typedefstructnode{//定义数据结构
intltag,rtag;//表示child域指示该结点是否孩子
chardata;//记录结点的数据
structnode*lchild,*rchild;//记录左右孩子的指针
}Bithptr;
Bithptr*Q[maxsize];//建队，保存已输入的结点的地址
Bithptr*CreatTree（）{//建树函数，返回根指针
charch;
intfront,rear;
Bithptr*T,*s;
T=NULL;
front=1;rear=0;//置空二叉树
printf（"***********************************\n"）;
printf（"**\n"）;
printf（"*课程设计题目：
线索二叉树的运算。
*\n"）;
printf（"**\n"）;
printf（"***********************************\n"）;
printf（"创建二叉树，请依次输入，@表示虚结点，以#结束\n"）;
ch=getchar（）;//输入第一个字符
while（ch!
='#'）//判断是否为结束字符
{
s=NULL;
if（ch!
='@'）//判断是否为虚结点
{
s=（Bithptr*）malloc（sizeof（Bithptr））;
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
s->rtag=0;
s->ltag=0;
}
rear++;
Q[rear]=s;//将结点地址加入队列中
if（rear==1）T=s;//输入为第一个结点为根结点
else
{
if（s!
=NULL&&Q[front]!
=NULL）//孩子和双亲结点均不是虚结点
if（rear%2==0）
Q[front]->lchild=s;
elseQ[front]->rchild=s;
if（rear%2==1）front++;
}
ch=getchar（）;
}
returnT;
}
voidInorder（Bithptr*T）//中序遍历
{
if（T）
{
if（T->ltag!
=1）Inorder（T->lchild）;
printf（"→%c",T->data）;
if（T->rtag!
=1）Inorder（T->rchild）;
}
}
Bithptr*pre=NULL;
voidPreThread（Bithptr*root）//中序线索化算法，函数实现
{
Bithptr*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）;
}
}
voidPrintIndex（Bithptr*t）//输出线索
{
Bithptr*f;
f=t;
if（f）
{
if（f->ltag==1&&f->lchild==NULL&&f->rtag==1）printf（"【%c】",f->data）;//如果是第一个结点
if（f->ltag==1&&f->lchild!
=NULL）printf（"%c→【%c】",f->lchild->data,f->data）;//如果此结点有前驱就输出前驱和此结点
if（f->ltag==1&&f->rtag==1&&f->rchild!
=NULL）printf（"→%c",f->rchild->data）;//如果此结点有前驱也有后继，就输出后继
elseif（f->rtag==1&&f->rchild!
=NULL）printf（"【%c】→%c",f->data,f->rchild->data）;//如果没有前驱，就输出此结点和后继
printf（"\n"）;
if（f->ltag!
=1）PrintIndex（f->lchild）;
if（f->rtag!
=1）PrintIndex（f->rchild）;
}
}
Bithptr*SearchChild（Bithptr*point,charfindnode）//查找孩子结点函数
{
Bithptr*point1,*point2;
if（point!
=NULL）
{
if（point->data==findnode）returnpoint;
else
if（point->ltag!
=1）{point1=SearchChild（
升级会员 