4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

传统的链式存储技能体现一种父子关系,不能直接得到结点在遍历中的前驱或后继,通过观察,我们发现在二叉链表表示的二叉树中存在大量的空指针,若利用这些空链域存放指向其直接前驱或后继的指针,则可以更方便地运用某些二叉树操作算法,引入线索二叉树是为了加快查找结点前驱和后继的速度。

前面提到,在有N个结点的二叉树中,有N+1个空指针。这是因此每一个叶结点有2个空指针,而在每一个度为1的结点有1个空指针,总的空指针为2N0+N1,又有N0=N2+1,所以总的空指针为N0+N1+N2+1=N+1。

在二叉树线索化时,通常规定,若无左子树,另lchild指向其前驱结点;若无右子树,令rchild指向其后继结点。还需要整个两个标志域表明当前指针域所指对象是指向左(右)子结点还是直接前驱(后继)。

ltag

lchild

data

rchild

rtag

其中标志域含义如下:

ltag=0 lchild域指示结点的左孩子

ltag=1 lchild域指示结点的前驱

rtag=0 rchild域指示结点的右孩子

rtag=1 rchild域指示结点的后继

线索二叉树的存储结构描述如下:

typedef struct TheadNode{
	ElemType data;//数据元素
	struct ThreadNode *lchild,*rchild;//左,右孩子指针
	int ltag,rtag;//左右线索标志
}ThreadNode,*ThreadTree;

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

对二叉树的线索化,实质上就是遍历一次二叉树,只是在遍历的过程中,检查当前结点左右指针域是否为空,若为空,将它们改为指向前驱结点或后继结点的线索。

以中序线索二叉树的建立为例,指针pre指向中序遍历时上一个刚刚访问过的结点,用它来表示各结点的访问的前后关系。

通过中序遍历对二叉树线索化的递归算法如下:

void InThread(ThreadTree &p,Thread &pre){
//中序遍历对二叉树线索化的递归算法
	if(p!=null){
		inThread(p->lchild,pre);//递归,线索化左子树
		if(p->lchild==null){//左子树为空,建立前驱线索
			p->lchild=pre;
			p->ltag=1;
		}
		if(pre!=null&&pre->rchild==null){
			pre->rchild=p;//建立前驱结点的后继线索
			pre->rtag=1;
		}
		pre=p;//标记当前结点成为刚刚访问过的结点
		inThread(p->rchild,pre);//递归,线索化右子树
	}
}

通过中序遍历建立中序线索二叉树的主过程算法如下:

void CreateInThread(ThreadTree T){
	ThreadTree pre=null; 
	if(T!=null){
		inThread(T,pre);//非空二叉树,线索化
		pre->rchild=null;//处理遍历的最后一个结点
		pre->rtag=1;
	}
}

有时为了方便,仿照线性表的存储结构,在二叉树的线索链表上也添加一个头结点,并令其lchild域的指针指向二叉树的根结点其rchild域的指针指向中序遍历时访问的最后一个结点;反之,令二叉树中序序列的第一个结点的lchild域的指针和最后一个结点rchild域的指针均指向头结点。这好比为二叉树建立一个双向线索链表,既可以从第一个结点起顺后继进行遍历,也可从最后一个结点其顺前驱进行遍历。

3.线索二叉树的遍历

中序线索化二叉树主要是为了访问运算服务的,这种遍历不再需要借助栈,因为它的结点中隐含了线索二叉树的前驱和后继信息。利用线索二叉树,可以实现二叉树遍历和非递归算法。不含头结点的线索二叉树的遍历算法如下: 1)求中序线索二叉树中中序序列下的第一个结点

ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag==0)
		p=p-lchild;//最左下结点(不一定是叶结点)
	return p;
}

2)求中序线索二叉树中结点P在中序序列下的后继结点

ThreadNode *Nextnode(ThreadNode *p){
	if(p->ltag==0)
		return FirtNode(p->rchild);
	else
		return  p-rchild;//rtag==1直接返回后继线索
}

3)利用上面两个算法,可以写出不含头结点的中序线索二叉树的中序遍历的算法;

void inorder(ThreadNode *T){
	for(ThreadNode *p=FirstNode(T);p!=Null;p=Nextnode(p))
		visit(p);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏F_Alex

数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)

前言:前面了解了树的概念和基本的存储结构类型及树的分类,而在树中应用最广泛的种类是二叉树

11920
来自专栏编程坑太多

HashMap 源码解析

13220
来自专栏Bingo的深度学习杂货店

Q110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a hei...

29350
来自专栏C/C++基础

判断二叉树是否为平衡二叉树

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

8120
来自专栏深度学习思考者

二叉树的遍历、查找、插入以及删除

二叉树的主要存储方式是链接存储,标准存储结构也称为二叉链表。 二叉链表结点类的定义 struct Node{ Node *left, *right;...

396100
来自专栏MelonTeam专栏

ArrayList源码完全分析

导语: 这里分析的ArrayList是使用的JDK1.8里面的类,AndroidSDK里面的ArrayList基本和这个一样。 分析的方式是逐个API进行解析 ...

62890
来自专栏java闲聊

JDK1.8 ArrayList 源码解析

当运行 ArrayList<Integer> list = new ArrayList<>() ; ,因为它没有指定初始容量,所以它调用的是它的无参构造

14520
来自专栏来自地球男人的部落格

[LeetCode] 113. Path Sum II

【原题】 Given a binary tree and a sum, find all root-to-leaf paths where each pa...

22470
来自专栏null的专栏

数据结构和算法——二叉树

二叉树是使用较多的一种树形结构,如比较经典的二叉排序树,Huffman编码等,都使用到了二叉树的结构,同时,在机器学习算法中,基于树的学习算法中也大量使用到二叉...

31750
来自专栏张俊红

数据结构—树与二叉树

之前谈到的线性表、栈和队列都是一对一的数据结构,但是现实中也存在很多一对多的数据结构,这篇要写的就是一种一对多的数据结构———树。全文分为如下几部分:

15330

扫码关注云+社区

领取腾讯云代金券