二叉树的线索化
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的线索化,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含7080字,纯文字阅读大概需要11分钟。
内容图文
![二叉树的线索化](/upload/InfoBanner/zyjiaocheng/1073/7c47b20067f44003873b6b757f4ce0a5.jpg)
二叉树的线索化
概念
二叉树的遍历是将二叉树中结点按一定规律线性化的过程。当以二叉链表作为存储结构时,仅仅能找到左右孩子信息,而不能直接得到结点在遍历序列中的前驱和后继信息。要得到这些信息有两个办法:1.将二叉树遍历一遍。在遍历过程中可得到前序和后继,2.充分利用二叉树中的空链表域。将遍历的过程中的结点的前驱和后继保存下来,实验证明另外一种方法更优。以下介绍第2种方法。
数据结构
在有n个结点的二叉树中。共同拥有2n个链表域。但仅仅有n-1个实用的非空链表域,其余n+1个都是空的,我们能够利用这n+1个链表域来存放遍历过程訪问的结点的前驱和后继。其结构例如以下图:
当中:
ltag = 0表示lchild指向结点的左孩子。ltag = 1表示lchild指向前驱;
rtag = 0表示rchild指向结点的右孩子。rtag = 1表示rchild指向后继;
在这样的存储结构中,指向前驱和后继结点的指针叫做线索,以这样的结构组成的二叉树为线索二叉树。
中序线索化
问题来了!!!为什么我们要选择中序线索化呢?例如以下图所看到的是一个二叉树的先序、中序、后序线索化过程。
二叉树的前序遍历顺序为:ABDG CEHF。假设用下划线来代表空链表域的话,则是:AB D _G C _ E _ H _ F
中序遍历顺序为:DGBAEHCF,假设用下划线来代表空链表域的话,则是:
D G _ B _ A _ E _ H _ C _ F _
后序遍历的顺序为:GDBAHEFC。假设用下划线来代表空链表域的话。则是:_ G _ D B A _ H _ _ E _ F _ C.
从先序、中序、后序线索化的过程中。能够大致看出,中序遍历的空链表域分布更均匀。在指向前驱和后继过程中更好,可是这也不是否能定前序的线索化和后序的线索化,还是依照二叉树的结构和特点以及使用场景来进行选择,在这里就仅仅说明中序线索化。
二叉树的线索化操作
二叉树的线索化操作(中序线索化):
status InitBTree(BTree * BT)初始化建立二叉树;
void OnThread(BTree BT)二叉树线索化。
BTree FindPre(BTree BT)查找线索化结点的前驱;
BTree FindLast(BTree BT)查找线索化结点的后继;
BTree FindNode(BTree BT,char ch)查找指定结点位置;
status InsNode(BTree BT,char par,int pos, char value)线索化二叉树的插入一个结点;
BTree DelNode(BTree BT,char ch);线索化二叉树删除一个结点。
(——————————-C语言实现———————————–)
#include
"stdio.h"
#include
"stdlib.h"
#include
"string.h"
#define ERROR 0#defineTRUE1
typedef int status;
typedef struct BTNode{
char data;
int ltag,rtag; //标识
struct BTNode *lchild,*rchild;
}BTNode, *BTree;
struct BTNode *pre =NULL; //先前结点/*初始化二叉树,建立二叉树*/
status InitBTree(BTree * BT){
//前序建立二叉树
char temp;
scanf("%c",&temp);
if(temp ==‘.‘)(*BT) =NULL;
else{
(*BT) = (BTree)malloc(sizeof(BTNode));
(*BT)->data= temp;
(*BT)->lchild =NULL;(*BT)->rchild =NULL;
(*BT)->ltag =0;(*BT)->rtag =0;
InitBTree(&(*BT)->lchild);
InitBTree(&(*BT)->rchild);
}
returnTRUE;
}
//二叉树线索化void OnThread(BTree BT){
//因为二叉树的中序遍历过程中,左右孩子为空的位置分布较为均匀。所以二叉树线索化是二叉树的中序的悬索化//二叉树的 线索化是将树形结构转化为线性结构if(BT!=NULL){
OnThread(BT->lchild);
if(pre!=NULL&& pre->rchild ==NULL){
pre->rtag =1;
pre->rchild = BT;
}
if(BT->lchild ==NULL){
if(pre !=NULL){
BT->ltag =1;
BT->lchild = pre;
}
}
pre = BT;
OnThread(BT->rchild);
}
}
void PrintTree(BTree BT, int nLayer){ //打印二叉树竖型结构
int i =0;
if(BT ==NULL)return;
PrintTree(BT->rchild,nLayer +1);
for(i =0; i<nLayer;i++){
printf(" ");
}
printf("%c\n",BT->data);
PrintTree(BT->lchild,nLayer +1);
}
BTree FindPre(BTree BT){ //查找结点的前驱
BTree p =NULL;
if(BT!=NULL){
if(BT->lchild ==NULL)returnNULL; //前驱结点为空elseif(BT->lchild!=NULL&& BT->ltag ==1)return BT->lchild;
elseif(BT->lchild !=NULL&& BT->ltag ==0){
p = BT;
while(p->rchild !=NULL&& p->rtag !=1)p = p->rchild;
return p;
}
}
returnNULL;
}
BTree FindLast(BTree BT){ //查找结点后继
BTree p =NULL;
if(BT!=NULL){
if(BT->rchild ==NULL)returnNULL;
elseif(BT->rchild !=NULL&& BT->rtag ==1)return BT->rchild;
elseif(BT->rchild !=NULL&& BT->rtag ==0){
p = BT->rchild;
while(p->lchild !=NULL&& p->ltag ==0)p = p->lchild;
return p;
}
}
returnNULL;
}
BTree FindNode(BTree BT,char ch){ //查找当前节点
BTree p =NULL;
if(BT!=NULL){
if(BT->lchild !=NULL){
p = BT->lchild;
while(p->lchild !=NULL)p = p->lchild; //找到线头
}elseif(BT->lchild ==NULL){ //仅仅有右子树
p = BT;
}
while(p!=NULL){
if(p->data== ch)return p;
p = FindLast(p);
}
}
returnNULL;
}
BTree FindParent(BTree BT,BTree p1){ //查找当前节点
BTree p =NULL;
if(BT!=NULL){
if(BT->lchild !=NULL){
p = BT->lchild;
while(p->lchild !=NULL)p = p->lchild; //找到线头
}elseif(BT->lchild ==NULL){ //仅仅有右子树
p = BT;
}
while(p!=NULL){
if((p->lchild == p1 && p->ltag ==0) || (p->rchild == p1 && p->rtag ==0))return p;
p = FindLast(p);
}
}
returnNULL;
}
status InsNode(BTree BT,char par,int pos, char value){ //par父节点data,pos代表插入的左边还是右边0代表左边,1代表右边
BTree s =NULL,last =NULL,pre1 =NULL;
BTree parent= FindNode(BT,par);
if(parent==NULL){
printf("插入位置不存在...");
return ERROR;
}
if(pos ==1){ //插入右子树
s = (BTree)malloc(sizeof(BTNode));
if(parent->rtag ==1){ //假设右子树为空
s->data= value;
s->ltag =1;s->lchild =parent;
s->rtag =parent->rtag;
s->rchild =parent->rchild;
parent->rtag =0;
parent->rchild = s;
}elseif(parent->rtag ==0){ //右子树不为空if(parent->rchild ==NULL){
s->data= value;
parent->rchild = s;
s->rtag =0;s->rchild =NULL;
s->ltag =1;s->lchild =parent;
returnTRUE;
}
last = FindLast(parent); //查找到父节点直接后继
printf("后继结点:%c\n",last->data);
if(last!=NULL){
s->data= value;
s->rtag =0; s->rchild =parent->rchild;
parent->rchild = s;
s->ltag =1;s->lchild =parent;
last->lchild = s;
}
}
}elseif(pos ==0){ //插入左子树
s = (BTree)malloc(sizeof(BTNode));
if(parent->ltag ==1){ //假设左子树为空
s->data= value;
s->ltag =parent->ltag;s->lchild =parent->lchild;
parent->ltag =0;
s->rtag =1; s->rchild =parent;
}elseif(parent->ltag ==0){
if(parent->lchild ==NULL){
s->data= value;
parent->lchild = s;
s->ltag =0;s->lchild =NULL;
s->rtag =1;s->rchild =parent;
returnTRUE;
}
pre1 = FindPre(parent);
s->data= value;
s->ltag =parent->ltag;
s->lchild =parent->lchild;
parent->lchild = s;
s->rtag =1;
s->rchild =parent;
pre1->rchild = s;
}
}
returnTRUE;
}
BTree DelNode(BTree BT,char ch){ //删除结点
BTree parent=NULL,p =NULL,temp =NULL,temp1 =NULL;
p = FindNode(BT,ch);
if(p ==NULL){
printf("二叉树无此结点\n");
return ERROR;
}
parent= FindParent(BT,p);
if(parent==NULL){ //删除根结点,顶点
temp = FindPre(p); //找到根节点的先驱
temp->rtag =0;temp->rchild = p->rchild;
if(p->rchild->ltag ==1)p->lchild = temp;
temp1 = BT->lchild;
free(BT);
return temp1;
}elseif(p->ltag ==1&& p->rtag ==1){
if(parent->lchild == p){
parent->ltag = p->ltag;
parent->lchild = p->lchild;
}elseif(parent->rchild == p){
parent->rtag = p->rtag;
parent->rchild = p->rchild;
}
return BT;
}elseif(p->ltag ==0&& p->rtag ==0){ //有左右子树if(parent->rchild == p){
temp = FindPre(p);
parent->rchild = p->lchild;
temp->rtag =0;temp->rchild = p->rchild;
free(p);
}elseif(parent->lchild == p){
temp = FindLast(p);
parent->lchild = p->rchild;
temp->ltag =0;temp->lchild = p->lchild;
free(p);
}
}
return BT;
}
void OnOrder(BTree BT){ //遍历
BTree p =NULL;
printf("线索化的遍历:\n");
if(BT!=NULL){
if(BT->lchild !=NULL){
p = BT;
while(p->lchild !=NULL&& p->ltag ==0)p = p->lchild; //找到线头
}elseif(BT->lchild ==NULL){ //仅仅有右子树
p = BT;
}
while(p!=NULL){
printf("%c",p->data);
p = FindLast(p);
}
}
printf("\n");
}
/*主函数*/void main(){
BTree BT =NULL; //初始化
BTree temp1 =NULL;
char input;
printf("请输入前序二叉树,空结点以.表示:\n");
InitBTree(&BT); //建立二叉树
getchar();
printf("打印二叉树的树形结构:\n");
PrintTree(BT,1); //
OnThread(BT); //线索化二叉树
OnOrder(BT); //依据线索遍历//查找某一节点
printf("请输入要查找的字符:");
scanf("%c",&input);
getchar();
temp1 = FindNode(BT,input);
if(temp1 ==NULL)printf("查找失败...\n");
else printf("查找到%c\n",temp1->data);
InsNode(BT,‘B‘,0,‘K‘);
printf("插入后遍历:\n");
OnOrder(BT); //依据线索遍历
}
原文:https://www.cnblogs.com/llguanli/p/8323769.html
内容总结
以上是互联网集市为您收集整理的二叉树的线索化全部内容,希望文章能够帮你解决二叉树的线索化所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。