线索二叉树
2023-02-18 16:34:55 时间
一、线索二叉树的原理
通过考察各种二叉链表,不管儿叉树的形态如何,空链域的个数总是多过非空链域的个数。
n各结点的二叉链表共有2n个链域,非空链域为n-1个,但其中的空链域却有n+1个。如下图所示。
(除根结点以外,所有结点都有一共指向它的结点,所有非空链域为n-1,空链域为n+1)
因此,提出了一种方法,利用原来的空链域存放指针,指向树中其他结点。这种指针称为线索。
记ptr指向二叉链表中的一个结点,以下是建立线索的规则:
(1)如果ptr->lchild为空,则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱;
(2)如果ptr->rchild为空,则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继;
显然,在决定lchild是指向左孩子还是前驱,rchild是指向右孩子还是后继,需要一个区分标志的。因此,我们在每个结点再增设两个标志域ltag和rtag,注意ltag和rtag只是区分0或1数字的布尔型变量,其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。
其中:
(1)ltag=0 时指向该结点的左孩子,为1时指向该结点的前驱;
(2)rtag=0 时指向该结点的右孩子,为1时指向该结点的后继;
(3)因此对于上图的二叉链表图可以修改为下图下的样子。
二、线索二叉树结构实现
存储结构
typedef char DataType;
typedef enum{Link, Thread}PointerTag; //Link = 0表示指向左右孩子指针;Thread = 1表示指向前驱或后继的线索
struct BitNode{
DataType data;
BitNode *lchild, *rchild;
PointerTag ltag;
PointerTag rtag;
};
typedef BitNode* BitTree;
中序遍历线索化
BitTree pre;
void InThreading(BitTree p){
if(p){
InThreading(p->lchild);//递归左子树线索化
if (!p->lchild)//没有左孩子
{
p->ltag= Thread;//前驱线索
p->lchild=pre;//左孩子指向前驱
}
if (!p->rchild)//没有右孩子
{
pre->rtag= Thread;//后继线索
pre->rchild=p;//前驱右孩子指向后继
}
pre = p;
InThreading(p->rchild);
}
}
中序遍历二叉线索树表示二叉树t
int InOrderThraverse_Thr(BiTree t)
{
BiTree p;
p=t->lchild; //p指向根结点
while(p!= t) //空树或遍历结束时p == t
{
while(p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点
{
p = p->lchild;
}
cout<<p->data<<" "; //显示结点数据,可以更改为其他对结点的操作
while(p->rtag == Thread && p->rchild != t)
{
p = p->rchild;
cout<<p->data<<" ";
}
p = p->rchild; //p进入其右子树
}
return 0;
}
相关文章
- Sql Server之旅——第一站 那些给我们带来福利的系统视图
- 看看C# 6.0中那些语法糖都干了些什么(终结篇)
- 看看C# 6.0中那些语法糖都干了些什么(中篇)
- 看看C# 6.0中那些语法糖都干了些什么(上篇)
- 简单看看ThreadPool的源码以及从中看出线程间传值的另一种方法
- 最近用Timer踩了一个坑,分享一下避免别人继续踩
- 看看Parallel中高度封装的三个方法,Invoke,For和ForEach
- 简单看看这两个类 String和StringBuilder
- 看看这个超级实用的一种类型——匿名类型
- 来看看两种好玩的方法,扩展方法和分部方法
- 一个类型转换而引起的三级事件的一些思考
- 看看这个常常被初级程序员弄不懂的 “事件”
- 学C#你应该熟练使用ILDasm和Reflector【带视频教程】
- 挖一挖C#中那些我们不常用的东西之系列(5)——FlagAttribute
- 挖一挖C#中那些我们不常用的东西之系列(4)——GetHashCode,ExpandoObject
- 我也要谈谈大型网站架构之系列(4)——分布式中的异步通信
- 我也要谈谈大型网站架构之系列(3)——死了都要说的缓存
- 我也要谈谈大型网站架构之系列(2)——纵观历史演变(下)
- 我也要谈谈大型网站架构之系列(1)——纵观历史演变(上)
- 抛弃NVelocity,来玩玩Razor