精品线索二叉树的运算文档格式.docx
《精品线索二叉树的运算文档格式.docx》由会员分享，可在线阅读，更多相关《精品线索二叉树的运算文档格式.docx（29页珍藏版）》请在冰点文库上搜索。
因此一般来说，这个过程花费的代价几乎与重新进行线索化相同。
二、概要设计和数据结构选择
首先建立二叉树，然后对二叉树进行线索化。
线索链表的结点结构
线索链表中的结点结构为：
图
（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）程序流程图
三、详细设计和编码
（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;
lchild=NULL;
rchild=NULL;
rtag=0;
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）线索化算法：
线索过程必须要按照一定的顺序来进行，在本程序中因为树的遍历过程使用的是中序遍历，所以为了方便，线索化的过程也是使用中序线索化。
2、方法：
按某种遍历顺序将二叉树线索化，只需要在遍历的过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继。
若其左子树为空，则将其左孩子域线索化，使其左孩子指针lchild指向其后继，并且ltag置1。
要实现线索化，就要知道结点*pre是结点*p的前驱，而*p是*pre的后继。
这样，当遍历到结点*p时，可以进行，若*p有空指针域，则将相应的标志置1；
若*p的左线索标志已经建立（p->
ltag==1），则可使其前驱线索化，令p->
lchild=pre；
若*pre的左线索标志已经建立（pre->
rtag==1），则可使其后继线索化，令pre->
rchild=p;
voidPreThread（Bithptr*root）
{
PreThread（p->
lchild）;
//左子树线索化
if（pre&
pre->
rtag==1）pre->
//前驱结点后继线索化
if（p->
lchild==NULL）
p->
ltag=1;
lchild=pre;
if（p->
rchild==NULL）//后继结点前驱线索化
rtag=1;
pre=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!
returnpoint1;
}
if（point->
rtag!
=1）{//判断是否有右子树
point2=SearchChild（point->
rchild,findnode）;
if（point2!
returnpoint2;
returnNULL;
}
else
4、插入方法：
在一棵树中插入一个结点，因为插入的位置不同，就对应着不同的插入情况。
通过分析总结出各种情况：
插入结点有左孩子时：
插入的方法是，找到左子树的最右下结点，将待插的结点插为其结点的右孩子。
插入结点没有左孩子时：
插入的方法是，直接将待插的结点插为其结点的左孩子。
5、插入实现：
（当结点有左子树时）
p2=child;
child=child->
lchild;
while（child->
rchild&
child->
rtag==0）//左子树的最右下结点
rchild;
p1->
rchild=child->
//后继线索化
rchild=p1;
//连接结点
lchild=child;
//前驱线索化
（当结点没左孩子的时）
lchild=child->
//前驱化
lchild=p1;
rchild=child
6、图形显示：
如插入abcdefg#
中序为：
建树后，结点的线索变化如图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、实现：
（只列出要删除结点是父结点的左子树的情况）
要删除结点无左右
if（child->
lchild!
lchild->
rtag==1）child->
rchild=pre;
要删除结点有左无右：
s=child->
while（s->
rchild）
s=s->
s->
要删除结点有右无左：
lchild）
=NULL）
要删除结点左右都有：
//把要删除结点的左孩子的右子树接到孩子右子树的最左下结点
=1）s->
q=child->
while（q->
q=q->
q->
4、图形显示如图6：
如删除结点e
删除后：
→d→b→a→f→c→g
图（6）删除结点图示
四、上机调试
1、语法错误及修改：
编译中出现的语法问题主要在于子函数和变量的定义，括号的配对，关键字和函数名称的书写，以及一些库函数的规范使用等问题时常出现。
但这些问题均可以根据编译器的警告提示，一一对应的将其解决。
总结其出现原因有多方面的，比如各个变量名称前后不一致，缺少符号等。
对了还有一个原因就是中英文的标点混合，这也是一个大的容易错的细节，而且出现问题之后往往难以辨明。
经过这次经历后，我想以后这些低级错误会最大限度的避免的。
2、逻辑问题修改和调整：
本程序所写内容基本上都是课本中所未提及知识，所以在编程过程中遇到了很多的难题，另外由于线索二叉树的插入和删除运算过程很复杂，所以设计过程中经常出现各种没有考虑到的情况，通过查找课本和资料以及询问同学及老师最终基本实现线索二叉树的运算处理。
在编译过程中运用了很多的递归运算，比如中序遍历，中序线索二叉树和查找等函数中，这都是在编程中找到的具体解决方法。
五、用户使用说明
本程序运行过程时带有提示性语句。
建立二叉树后先对其进行线索化，以实现线索二索二叉树的运算。
由于线索二叉树插入与删除后对运算后的线索二叉树进行了恢复线索运算，因此在进行插入与删除后不用进行线索化操作便可直接输出运算后的线索二叉树。
具体的使用步骤及方法如下：
在vc里面运行程序后，进入输入界面，首先需要创建一个二叉树，要依次输入，但在输入的过程中应注意，‘@’用来表示虚节点，在输入完成后用‘#’来做输入的结束标识符。
在输入完成后，便会出现程序菜单，这也是本程序的精华和功能部分，具体内容有：
1.中序输出二叉树
2.进行二叉树线索化
3.进行插入操作
4.进入删除操作
5.输出线索二叉树
0.退出
用户可以根据提示选择所要运行的功能，但需要注意的是线索二叉树插入与删除后对运算后的线索二叉树进行了恢复线索运算，因此在进行插入与删除后不用进行线索化操作便可直接输出运算后的线索二叉树。
最后运行完成后，按0退出。
六、测试结果
如图（7）所示，建立二叉树并中序输出
图（7）建立二叉树并中序输出
如图（8）所示，线索化二叉树并输出线索二叉树
图（8）线索化二叉树并输出线索二叉树
如图（9）所示，插入结点F并线索化输出
图（9）插入结点F并线索化输出
如图（10）所示，删除结点D并线索化输出
图（10）删除结点D并线索化输出
七、参考书目
[1]谭浩强.C程序设计.清华大学出版社
[2]王昆仑,李红,数据结构与算法.中国铁道出版社
[3]赵坚,姜梅.数据结构（C语言版）.中国水利水电出版社
[4]孟祥瑞,汤文兵.数据结构（C语言版）.东华理工大学出版社
[5]候风巍.数据结构要点精析.北京航空航天大学出版社
八、附录（源程序）
#include"
stdio.h"
malloc.h"
#definemaxsize20//规定树中结点的最大数目
typedefstructnode{//定义数据结构
intltag,rtag;
//表示child域指示该结点是否孩子
chardata;
//记录结点的数据
structnode*lchild,*rchild;
//记录左右孩子的指针
}Bithptr;
//建队，保存已输入的结点的地址
Bithptr*CreatTree（）{//建树函数，返回根指针
charch;
intfront,rear;
Bithptr*T,*s;
T=NULL;
//置空二叉树
printf（"
***********************************\n"
）;
printf（"
**\n"
printf（"
*课程设计题目：
线索二叉树的运算。
*\n"
创建二叉树，请依次输入，@表示虚结点，以#结束\n"
ch=getchar（）;
//输入第一个字符
while（ch!
#'
）//判断是否为结束字符
{
s=NULL;
if（ch!
）//判断是否为虚结点
{
s=（Bithptr*）malloc（sizeof（Bithptr））;
s->
}
rear++;
Q[rear]=s;
//将结点地址加入队列中
if（rear==1）T=s;
//输入为第一个结点为根结点
else
if（s!
=NULL）//孩子和双亲结点均不是虚结点
if（rear%2==0）
Q[front]->
elseQ[front]->
if（rear%2==1）front++;
ch=getchar（）;
returnT;
voidInorder（Bithptr*T）//中序遍历
if（T）
if（T->
=1）Inorder（T->
printf（"
→%c"
T->
data）;
Bithptr*pre=NULL;
voidPreThread（Bithptr*root）//中序线索化算法，函数实现
Bithptr*p;
p=root;
if（p）{
PreThread（p->
//线索化左子树
if（pre&
//前驱结点后继线索化
p->
if（p->
pre=p;
voidPrintIndex（Bithptr*t）//输出线索
Bithptr*f;
f=t;
if（f）
if（f->
ltag==1&
f->
lchild==NULL&
rtag==1）printf（"
【%c】"
f->
//如果是第一个结点
=NULL）printf（"
%c→【%c】"
data,f->
//如果此结点有前驱就输出前驱和此结点
if（f->
rtag==1&
rchild!
rchild->
//如果此结点有前驱也有后继，就输出后继
elseif（f->
【%c】→%c"
//如果没有前驱，就输出此结点和后继
\n"
=1）PrintIndex（f->
}
Bithptr*SearchChild（Bithptr*point,charfindnode）//查找孩子结点函数
Bithptr*point1,*point2;
data==findnode）returnpoint;
if（point->
=1）{point1=SearchChild（point->
if（point1!
=NULL）returnpoint1;
升级会员 