线索二叉树的运算
计算机科学与技术系
课程设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
2008 ,2009 学年第 2 学期
课程 数据结构
课程设计名称 线索二叉树的运算
学生姓名
学号
专业班级
指导教师 屠菁、张贯红
2009 年 5 月
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目:(线索二叉树运算)实现线索二叉树的建立、插入、删除、恢复线索的实现。
一、 问题分析和任务定义
(1).任务定义:
此程序需要完成如下要求:建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。
实现本程序需要解决以下几个问题:
1、 如何建立线索二叉树。
2、 如何实现线索二叉树的插入。
3、 如何实现线索二叉树的删除。
4、 如何实现线索二叉树恢复线索的实现。
此题目是线索二叉树的一系列操作问题。首先就要明白线索二叉树是什么，利用二叉链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
的空指针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继，这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
在这个问题中，要解决的任务是:实现线索二叉树的建立、插入、删除、恢复线索的实现。n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为"线索")。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。在此次课程设计中，采用的是中序线索二叉树。
(2).问题分析:
既然题目要求要分别实现建立、删除、和恢复线索化三种功能，建立和删除一定是相互独立的模块，可分别建立两个函数来实现功能。第三个功能是恢复线索，就要考虑这个线索恢复是怎样的恢复过程，是怎样恢复的。恢复线索是对二叉树当进行了插入和删除操作过程后，因为过程中有结点的变动，而进行的在操作结束以后对整个二叉树的恢复线索，还是在实现插入和删除的过程中就对操作的结点实现局部的恢复线索。从设计的目标来说应该是要在删除和插入的过程中实现对线索的恢复。而在线索二叉树中插入一个结点或删除一个结点，一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。因此一般来说，这个过程花费的代价几乎与重新进行线索化相同。 二、概要设计和数据结构选择
首先建立二叉树，然后对二叉树进行线索化。
线索链表的结点结构
线索链表中的结点结构为:
图(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的后继。
程序流程图:
开始
定义二叉树
建立二叉树
选择菜单
输入i(0-5)
i=1N
Y
i=2N中序输出二叉树
Y
i=3N进行二叉树线索化
Y
i=4N插入结点并线索化
Y
i=5删除结点并线索化
YN
输出线索二叉树
结束
图(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;
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;
else Q[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、主要过程:
void PreThread(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,char findnode)
{
Bithptr *point1,*point2;
if(point!=NULL)
{
if(point->data==findnode)return point; //找到结点的信息，返回指针
else
if(point->ltag!=1) { //判断是否有左子树
point1=SearchChild(point->lchild,findnode);//递归
if(point1!=NULL)
return point1;
}
if(point->rtag!=1){ //判断是否有右子树
point2=SearchChild(point->rchild,findnode);//递归
if(point2!=NULL)
return point2;
}
return NULL;
}
else
return NULL;
}
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
b
c
^ d e f g
^^dvvv^^图(4) 结点的线索变化图a
^^^^ 则插入结点后的顺序为:?d?w?b?e?a?f?c?g
a
b c
^ d e f g
w 图(5) 结点的线索变化 图b
(4) 删除结点函数
1、分析:要在函数中删除一个结点，也要考虑各种不同的情况。在删除结点之前也要先找到要删除的点，就调用查找孩子结点函数Bithptr *SearchChild(Bithptr *point,char
findnode)找到其结点的指针。再后面的操作就是怎样删除了，就发现在删除过程中涉及的指针变换需要父亲结点的指针，所以就调用查找父亲结点函数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
a
b c
d e f g
图(6)删除结点图示
四、上机调试
1、语法错误及修改:编译中出现的语法问题主要在于子函数和变量的定义，括号的配对，关键字和函数名称的
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
写，以及一些库函数的规范使用等问题时常出现。但这些问题均可以根据编译器的警告提示，一一对应的将其解决。总结其出现原因有多方面的，比如各个变量名称前后不一致，缺少符号等。对了还有一个原因就是中英文的标点混合，这也是一个大的容易错的细节，而且出现问题之后往往难以辨明。经过这次经历后，我想以后这些低级错误会最大限度的避免的。
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"
#include "malloc.h"
#define maxsize 20 //规定树中结点的最大数目 typedef struct node{ //定义数据结构
int ltag,rtag; //表示child域指示该结点是否孩子
char data; //记录结点的数据
struct node *lchild,*rchild; //记录左右孩子的指针
}Bithptr;
Bithptr *Q[maxsize]; //建队，保存已输入的结点的地址
Bithptr *CreatTree(){ //建树函数，返回根指针
char ch;
int front,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;
else Q[front]->rchild=s;
if(rear%2==1)front++;
}
ch=getchar();
}
return T;
}
void Inorder(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;
void PreThread(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);
}
}
void PrintIndex(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); //如果此结点有前驱也有后继，就输出后继
else if(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,char findnode) //查找孩子结点函数 {
Bithptr *point1,*point2;
if(point!=NULL)
{
if(point->data==findnode) return point;
else
if(point->ltag!=1) { point1=SearchChild(point->lchild,findnode);
if(point1!=NULL)return point1;}
if(point->rtag!=1) { point2=SearchChild(point->rchild,findnode);
if(point2!=NULL)return point2;}
return NULL;
}
else
return NULL;
}
Bithptr *SearchPre(Bithptr *point,Bithptr *child) //查找父亲结点函数
{
Bithptr *point1,*point2;
if(point!=NULL)
{
if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rchild==child))
return point;//找到则返回
else
if(point->ltag!=1)
{
point1=SearchPre(point->lchild,child);
if(point1!=NULL)
return point1;
}
if(point->rtag!=1)
{
point2=SearchPre(point->rchild,child);
if(point2!=NULL)
return point2;
}
return NULL;
}
else
return NULL;
}
void Insert(Bithptr *root) {
char ch;
char c;
Bithptr *p1,*child,*p2;
printf("请输入要插入的结点的信息:");
scanf("%c",&c);
scanf("%c",&c);
p1=(Bithptr *)malloc(sizeof(Bithptr)); //插入的结点信息
p1->data=c;
p1->lchild=NULL;
p1->rchild=NULL;
p1->rtag=0;
p1->ltag=0;
printf("输入查找的结点信息:");
scanf("%c",&ch);
scanf("%c",&ch);
child=SearchChild(root,ch); //查孩子结点的地址
if(child==NULL){
printf("没有找到结点\n");
system("pause");
return ;
}
else printf("发现结点%c\n",child->data);
if(child->ltag==0) //当孩子结点有左孩子的时候
{
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;
}
else //当孩子结点没有左孩子的时候
{
p1->lchild=child->lchild; //前驱化
child->ltag=0;
p1->ltag=1;
child->lchild=p1;
p1->rchild=child;
p1->rtag=1;
}
printf("\n\t插入结点操作已经完成，并同时完成了线索化的恢复\n"); }
Bithptr * DeleteNode(Bithptr *t) {
Bithptr *child,*pre,*s,*q;
char ch;
printf("输入查找的结点信息:");
ch=getchar();
ch=getchar();
child=SearchChild(t,ch); //查找该结点的孩子结点
printf("发现结点:%c\n",child->data);
printf("ltag=%d,rtag=%d\n",child->ltag,child->rtag);
if(NULL==child)
{
printf("没有找到结点:");
return t;
}
if(child!=t)
{
pre=SearchPre(t,child);
printf("发现结点:%c\n",pre->data);
}
else
//当是头结点的时候
if(child->ltag==1&&child->rtag==1) //没有左右孩子
t=NULL;
else if(t->ltag==1&&t->rtag!=1) //有右孩子没有左孩子
{
t=child->rchild;
child->rchild->lchild=NULL;
free(child);
return t;
}else
if(t->ltag!=1&&t->rtag==1) //有左孩子没有右孩子
{
t=child->lchild;
child->lchild->rchild=NULL;
free(child);
return t;
}else
if(t->ltag!=1&&t->rtag!=1) //有左孩子也有右孩子
{
t=child->lchild;
s=child->lchild;
while(s->rchild&&s->rtag!=1) //查找孩子左子树的最右下结点
s=s->rchild;
q=child->rchild;
while(q->lchild&&q->ltag!=1) //查找孩子右子树的最左下结点
q=q->lchild;
s->rchild=child->rchild; //连接
s->rtag=0;
q->lchild=s;
free(child);
return t;
}
if(child==pre->lchild||child==pre) //
是父亲结点的左孩子
{
if(1==child->ltag&&1==child->rtag)//孩子结点无左右
{
pre->lchild=child->lchild;
pre->ltag=1;
if(child->lchild!=NULL)
if(child->lchild->rtag==1)child->lchild->rchild=pre;
free(child);
}
else if(1!=child->ltag&&1==child->rtag)//孩子结点有左无右
{
pre->lchild=child->lchild;
s=child->lchild;
while(s->rchild) //查找左子树的最右下结点
s=s->rchild;
s->rchild=child->rchild;
free(child);
}
else if(1==child->ltag&&1!=child->rtag)//孩子结点有右无左
{
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;
free(child);
}
else if(1!=child->ltag&&1!=child->rtag)//孩子结点左右都有
{
pre->lchild=child->lchild;
s=child->rchild;
while(s->lchild&&s->ltag!=1) //找到右子树的最左下结点
s=s->lchild;
q=child->lchild;
while(q->rchild&&q->rtag!=1) //找到左子树下最右下结点
q=q->rchild;
q->rchild=child->rchild; //将孩子结点的右子树接到左子树下最右
下结点
q->rtag=0;
s->lchild=q;
free(child);
}
}else {
if(child==pre->rchild)
//是父亲结点的右孩子
{
if(1==child->ltag&&1==child->rtag)//孩子结点无左右
{
pre->rchild=child->rchild;
pre->rtag=1;
if(child->rchild!=NULL)
if(child->rchild->ltag==1)child->rchild->lchild=pre;
free(child);
}
else if(1!=child->ltag&&1==child->rtag)//孩子结点有左无右
{
pre->rchild=child->lchild;
s=child->lchild;
while(s->rchild)
s=s->rchild;
s->rchild=child->rchild;
if(child->rchild!=NULL)
if(child->rchild->ltag==1)child->rchild->lchild=pre;
free(child);
}
else if(1==child->ltag&&1!=child->rtag)//孩子结点有右无左
{
pre->rchild=child->rchild;
s=child->rchild;
while(s->lchild)
s=s->lchild;
s->lchild=child->lchild;
free(child);
}
else if(1!=child->ltag&&1!=child->rtag) //孩子结点左右都有
{
pre->rchild=child->rchild;
s=child->rchild;
while(s->lchild&&s->ltag!=1) //找到右子树的最左下结点
s=s->lchild;
q=child->lchild;
while(q->rchild&&q->rtag!=1) //找到左子树下最右下结点
q=q->rchild;
s->lchild=child->lchild; //将孩子结点的左子树接到右子树下最左
下结点
s->ltag=0;
q->rchild=s;
free(child);
}
}
}
printf("\n\t删除结点操作已经完成，并同时完成了线索化的恢复\n");
return t;
}
void main()
{
Bithptr *T;
int i;
T=CreatTree();
printf("\n");
i=1;
while(i)
{
printf("\t1 中序输出二叉树\n");
printf("\t2 进行二叉树线索化\n");
printf("\t3 进行插入操作\n");
printf("\t4 进入删除操作\n");
printf("\t5 输出线索二叉树\n");
printf("\t0 退出\n");
printf("\t 请选择:");
scanf("%d",&i);
printf("\n");
switch(i)
{
case 1:Inorder(T);
printf("\n");
break;
case 2:PreThread(T);
printf("\t已经实现二叉树的线索化，(可选择'5'察看线索)\n");
printf("\n");
break;
case 3:Insert(T);printf("\n");break;
case 4:T=DeleteNode(T);printf("\n");break;
case 5:PrintIndex(T);break;
case 0:exit(1);
default:printf("error\n\t请继续选择:");
}
}
}
浙公网安备 33021202002483