线索二叉树 线索二叉树有什么优点

1、线索二叉树的结点结构

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构,使每个结点都有了唯一前驱和后继(第一个结点无前驱,最后一个结点无后继)。对于二叉树的一个结点,查找其左右子女是方便的,其前驱后继只有在遍历中得到。为了容易找到前驱和后继,有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd,这种方法增加了存储开销,不可取;二是利用二叉树的空链指针。现将二叉树的结点结构重新定义如下:

lchild

ltag

data

rtag

rchild

其中: ltag=0 时 lchild指向左子女;

ltag=1 时 lchild指向前驱;

rtag=0 时 rchild指向左子女;

rtag=1 时 rchild指向后继;

以这种结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,指向前驱和后继的指针叫线索,加上线索的二叉树叫线索二叉树,对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化。

学习线索化时,有三点必须注意:一是何种“序”的线索化,是先序、中序还是后序;二是要“前驱”线索化、“后继”线索化还是“全”线索化(前驱后继都要);三是只有空指针处才能加线索。

二叉树的二叉线索链表表示:

typedef structBiThrNode{

EelemTypedata;

structBiThrNode *lchild,*rchild; //左、右孩子指针

int ltag,rtag;

}BiThrNode, *BiThrTree

2、对二叉树进行线索化的算法

前驱线索化:

voidPreorderThread(BiThrTree p)

//初始时,p指向根结点T,pre的初值为NULL

{if (p)

{if (pre!=null&& pre->rtag==1)pre->rchild=p;//结点p的前驱作后继线索化

if (p->lchild==null){p->ltag=1;p->lchild=pre;}//前驱线索化

if (p->rchild==null)p->rtag=1;//置后序线索标志

pre=p; //修改,使指向新的当前结点的前驱

if (p->ltag==0)PreorderThread(p->lchild);//左子树线索化

PreorderThread(p->rchild)//右子树线索化

}//if

}// PreorderThread

中序线索化:

voidInorderThread(BiThrTree p)

//初始时,p指向根结点T,pre的初值为NULL

{if (p)

{InorderThread(p->lchild);//左子树线索化

if (pre!=null&& pre->rtag==1)pre->rchild=p;// 结点p的前驱作后继线索化

if (p->lchild==null){p->ltag=1;p->lchild=pre;}//前驱线索化

if (p->rchild==null)p->rtag=1;//置后序线索标志

pre=p; //修改,使指向新的当前结点的前驱

InorderThread(p->rchild)//右子树线索化

}//if

}// InorderThread

后序线索化:

voidPostorderThread(BiThrTree p)

//初始时,p指向根结点T,pre的初值为NULL

{if (p)

{PostorderThread(p->lchild);//左子树线索化

PostorderThread(p->rchild)//右子树线索化

if (pre!=null&& pre->rtag==1)pre->rchild=p;// 结点p的前驱作后继线索化

if (p->lchild==null){p->ltag=1;p->lchild=pre;}//前驱线索化

if (p->rchild==null)p->rtag=1;//置后序线索标志

pre=p; //修改,使指向新的当前结点的前驱

}//if

}// PostorderThread

3、在线索二叉树上查找前驱和后继

(1) 前序前驱: 若结点的ltag=1,lchild指向其前驱;否则,求前驱很困难;

前序后继: 若ltag=0,lchild指向其后继;否则,rchild指向其后继。

(2) 中序前驱:若结点的ltag=1,lchild指向其前驱;否则,该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。

中序线索二叉树中求中序前驱结点的算法:

InorderPre(BiThrTreep)

{// 在中序线索二叉树中找结点p的中序前驱结点

BiThrTree *q;

if(p->ltag= =1) //结点的左子树为空

return(p->lchild)//结点的左指针域为左线索,指向其前驱

else

{q=p->lchild; //p结点左子树中最右边结点是P结点的中序前驱

while (q->rtag )q=q->rchild;

return(q);

}// if

} // InorderPre

中序后继: 若rtag=1,rchild指向其后继;否则,该结点的后驱是以该结点为根的右子树上按中序遍历的第一个结点。

InorderNext(BiThrTreep)

{// 在中序线索二叉树中找结点p的中序后继结点

BiThrTree*q;

if(p->rtag= =1) //结点的右子树为空

return(p->rchild)//结点的右指针域为右线索,指向其后继

else

{q=p->rchild; //p结点的右子树中最左边结点是P结点的中序后继

while (q->ltag )q=q->lchild;

return(q);

}// if

线索二叉树 线索二叉树有什么优点

} // InorderNext

(3)后序后继:在后序线索二叉树中查找结点的前驱和后继要知道其双亲的信息,要使用栈,所以说后序线索二叉树是不完善的。

后序前驱: 若rtag=0,rchild指向其前驱,否则,lchild指向其前驱。

PostPre (BiThrTreep)

{// 在后序线索二叉树中找结点p的后序前驱结点

if(p->rtag==0)return (p->rchild);

elsereturn(p->lchild);

}// PostPre

4、对线索二叉树进行中序遍历的算法

void InorderTraverseThr(BiThrTreep)

{ // 遍历中序线索二叉树 p

while(p) // 二叉树非空

{ while (p->ltag==0)p=p->lchild; //找中序序列的开始结点

printf(p->data);

while(p &&p->rtag==1)

{p=p->rchild;printf(p-data);}//找P的中序后继结点

p=p->rchild;

}//while

} // InorderTraverseThr

}

5、对线索二叉树的插入算法

(1)y无右子树

x->ltag=1;x->rtag=1;

x->lchild=y;x->rchild=y->rchild;

y->rchild=x;

y->rtag=0;

(2)y有右子树

x->rchild=y->rchild;

x->ltag=1;

x->lchild=y;

y->rchild=x;

if(p->ltag==1)p->lchild=x//p是y的右子树上按中序遍历的第1个结点

  

爱华网本文地址 » http://www.413yy.cn/a/25101016/315710.html

更多阅读

安全二维码是干什么的 二维码能干什么

安全二维码是干什么的——简介安全二维码用于对二维码进行安全检测,以确保二维码信息中不含有病毒或其它垃圾信息。360推出安全二维码,可直接扫描或读出二维码,同时对其进行安全扫描,保护手机不受安全威胁。下面就来看一下360如何应用安

二维码是什么有什么用 精 高精度二维码

二维码是什么有什么用 精——简介二维码又叫做二维条形码,是利用黑白相间的图形记录数据符号信息的,使用电子扫描设备自动识读以实现信息自动处理。相信大家对二维码有了初步的认识,那么这些二维码到底有什么用呢,下面就跟小编一起来看

理科二本大学有哪些 上海二本大学有哪些

理科二本大学有哪些——简介很快就要到了高考的时刻了,高考是人生中比较重要的一个时刻,但是还有一个比较重要的时刻就是我们选择高校。高校使我们的目标,为之拼搏和奋斗了几年的目标,如何选择一个合适自己的院校是非常重要的。本次经验

二维码是什么 手机怎么扫描二维码

二维码是什么——简介现在到处可见二维码图案,大街小巷和互联网上,二维码似乎占据着生活的各个角落。二维码是什么,你知道吗?什么是二维码?本篇经验就给大家介绍,希望能帮助到不了解的朋友们!二维码是什么——工具/原料手机一部能上网电

达摩易筋经十二式图解 易筋经十二式有什么用

“达摩易筋经”是我国一种健身的好方法,此功使神、体、气三者, 即人的精神,形体和气息有效的结合起来,经过循序渐进,持之以恒地认真锻炼,从而使五脏六腑、十二经脉、奇经八脉及全身经脉得到充分的调理,进而达到保健强身,防病治病,抵御早衰,延

声明:《线索二叉树 线索二叉树有什么优点》为网友青果学霸分享!如侵犯到您的合法权益请联系我们删除