线索二叉树的原理及创建

二十二画程序员 等级 310 1 0

【系列推荐阅读】

1. 为什么要用到线索二叉树?

我们先来看看普通的二叉树有什么缺点。下面是一个普通二叉树(链式存储方式):

线索二叉树的原理及创建

乍一看,会不会有一种违和感?整个结构一共有 7 个结点,总共 14 个指针域,其中却有 8 个指针域都是空的。对于一颗有 n 个结点的二叉树而言,总共会有 n+1 个空指针域,这个规律使用所有的二叉树。

这么多的空指针域是不是显得很浪费?我们学习数据结构和算法的重点就是在想法设法地提高时间效率和空间利用率。这么多的指针域就这么白白浪费了,太败家了!

所以我们要想法子好好利用它们,利用它们来帮助我们更好地使用二叉树这个数据结构。

那么如何利用呢?

前面已经强调过很多次了,遍历二叉树的实质是将二叉树中非线性结构的结点转化为线性的序列,然后才能方便我们遍历。

比如上图的中序遍历序列为:DBGEACF。

对于一个线性序列(线性表)来说,它有直接前驱直接后继的概念(在【什么是线性表?】中介绍过)。比如在中序遍历序列中,B 的直接前驱为 D,直接后继为 G。

我们之所以能知道 B 的直接前驱和直接后继,是因为我们按照中序遍历的算法,把二叉树的中序遍历序列写出来了,然后根据这个顺序序列说谁的前驱是谁、后继是谁。

直接前驱和直接后继是不能完全直接通过二叉树得到的,因为二叉树中只有双亲和孩子结点之间的直接关系,即二叉树的结点指针域中只存储了其孩子结点的地址。

现在的需求是,我想能直接从二叉树上得到某结点在中序遍历方式下的直接前驱和直接后继。

这时候就需要用到线索二叉树了。

2. 什么是线索二叉树?

当然,我们肯定需要借助结点的指针域来保存直接前驱和直接后继的地址。

其实,在上图的普通二叉树中(以中序遍历得到的序列),部分结点(指针域不为空的结点)是可以找到其直接前驱或后继的,比如结点 E 的左孩子 G 就是结点 E 的直接前驱;结点 A 的右孩子 C 就是结点 A 的直接后继。

但部分结点(指针域为空)是行不通的,比如结点 G 的直接后继是 E,直接前驱是 B,但在二叉树中却不能得出这样的结论。怎么办呢?我们注意到,结点 G 的两个指针域都为 NULL,并未被利用,那么我们使用这两个指针,分别指向其前驱和后继不就好了吗?

线索二叉树的原理及创建

实在是两全其美,天作之合!但是问题并没有解决!

因为我们是利用空指针域来指向前驱或后继的,对于那些指针域不为空的结点,这样是矛盾的,比如结点 E 和结点 B。

既然有矛盾,那么我们就发现产生矛盾的根源,解决矛盾。

产生矛盾的根源是:结点的指针域为空和不为空时,指针的指向矛盾。即,指针不为空时指向孩子指针为空时指向前驱或后继之间的矛盾。

那么我们对症下药,把指针域为空和不为空给区分出来,清晰地告诉指针:不为空时指向孩子,为空时指向前驱或后继。这就需要我们给两个指针各添加一个标志位。

线索二叉树的原理及创建

并约定以下规则:

  • left_flag == 0 时,指针 left_child 指向左孩子
  • left_flag == 1 时,指针 left_child 指向直接前驱
  • right_flag == 0 时,指针 right_child 指向右孩子
  • right_flag == 1 时,指针 right_child 指向直接前驱

二叉树的结点要有所变化:

/*线索二叉树的结点的结构体*/
typedef struct Node {
    char data; //数据域
    struct Node *left_child; //左指针域
    int left_flag; //左指针标志位
    struct Node *right_child; //右指针域
    int right_flag; //右指针标志位
} TTreeNode;

有了标志位,一切就能理清了。我们称指向直接前驱和后继的指针为线索。标志位为 0 的指针是指向孩子的指针,标志位为 1 的指针是线索。

一个二叉链表树,结点结构如上,我们将所有空指针都变为线索,这样的二叉树就是二叉线索树。

3. 如何创造线索二叉树?

在普通二叉树中,我们想要获取某个结点在某种遍历次序下的直接前驱或后继,每次都需要遍历获取到遍历次序之后才能知道。而在线索二叉树中,我们只需要遍历一次(创造线索二叉树时的遍历),之后,线索二叉树就能“记住”每个结点的直接前驱和后继了,以后都不需要再通过遍历次序获取前驱或后继了。

我们按照某种遍历方式,把普通二叉树变为线索二叉树的过程被称为二叉树的线索化

接下来,我们用中序遍历的方式,将下面的二叉树线索化为线索二叉树

线索二叉树的原理及创建

将标志位为 1 的指针,按照中序遍历序列,使其指向前驱或后继:

线索二叉树的原理及创建

其中,结点 D 没有直接前驱,结点 F 没有直接后继,故指针为 NULL

到此,我们算是解决了拥有 n 个结点的二叉树存在 n+1 个空指针域所造成的浪费,解决方式是给每个结点的指针增加一个标志位,以此来利用空指针域。标志位中存储的是 0 或 1 的布尔值,与浪费的空指针域相比,是相对比较划算的。而且使二叉树具有了一种新特性——二叉树中能保存在某种遍历次序下的结点之间的前驱和后继关系。

4. 线索化的实现

请注意一点,线索二叉树是由普通二叉树得来的,而且是按某种遍历顺序得来的。因为线索是在知道某个结点的前驱和后继的情况下才能设置,而前驱和后继关系不能通过二叉树直接体现,只能通过遍历二叉树得到的线性序列得出关系。所以要通过某种遍历方式得到具有前驱和后继关系的序列后,才能修改结点的空指针,进而设置线索。

即:线索化的实质是在按照某种遍历次序进行遍历二叉树的过程中修改结点的空指针,使其指向其在该遍历次序下的直接前驱或直接后继的过程

我们在【二叉树的遍历原理】【二叉树的遍历实现】分别介绍了二叉树四种遍历方式的原理及代码实现。当时我们是以打印为例来介绍遍历的。但遍历不止做打印的事,还可以做线索化的事。

所以,代码的大体结构还是一样的,我们只需把遍历代码中的打印代码换成线索化的代码,并作出一些其他改变即可。

下面以下图为例,分别介绍三种线索化:

一颗未线索化的二叉树,其所有标志位均默认为 0.

线索二叉树的原理及创建

4.1. 中序线索化

按照中序遍历次序线索化后,可得下图:

线索二叉树的原理及创建

我们先再次明确以下内容:

  • 我们是在遍历二叉树的过程中进行线索化的。

  • 中序遍历的顺序为:左子树 >> 根 >> 右子树。

  • 线索化修改两个东西:空指针域和其对应的标志位。

  • 如何修改?将空指针域置为直接前驱或后继。

所以我们的问题变成了:

  1. 找到所有空指针域。
  2. 找到空指针域所属结点,在先序次序下的直接前驱和直接后继。
  3. 修改空指针域的内容,及其标志位,使该指针称为线索。

说明:我们在遍历二叉树时,使用到了递归,所以在进行线索化的时候,也会使用它。

具体代码如下:

//全局变量 prev 指针,指向刚访问过的结点
TTreeNode *prev = NULL;

/**
 * 中序线索化
 */
void inorder_threading(TTreeNode *root)
{
    if (root == NULL) { //若二叉树为空,做空操作
        return;
    }
    inorder_threading(root->left_child);
    if (root->left_child == NULL) {
        root->left_flag = 1;
        root->left_child = prev;
    }
    if (prev != NULL && prev->right_child == NULL) {
        prev->right_flag = 1;
        prev->right_child = root;
    }
    prev = root;
    inorder_threading(root->right_child);
}

4.2. 先序线索化

按照先序顺序线索化后,可得下图:

线索二叉树的原理及创建

具体代码如下:

// 全局变量 prev 指针,指向刚访问过的结点
TTreeNode *prev = NULL;

/**
 * 先序线索化
 */
void preorder_threading(TTreeNode *root)
{
    if (root == NULL) {
        return;
    }
    if (root->left_child == NULL) {
        root->left_flag = 1;
        root->left_child = prev;
    }
    if (prev != NULL && prev->right_child == NULL) {
        prev->right_flag = 1;
        prev->right_child = root;
    }
    prev = root;
    if (root->left_flag == 0) {
        preorder_threading(root->left_child);
    }
    if (root->right_flag == 0) {
        preorder_threading(root->right_child);
    }
}

4.3. 后序线索化

按照后序遍历次序线索化后,可得下图:

线索二叉树的原理及创建

具体代码如下:

//全局变量 prev 指针,指向刚访问过的结点
TTreeNode *prev = NULL;

/**
 * 后序线索化
 */
void postorder_threading(TTreeNode *root)
{
    if (root == NULL) {
        return;
    }
    postorder_threading(root->left_child);
    postorder_threading(root->right_child);
    if (root->left_child == NULL) {
        root->left_flag = 1;
        root->left_child = prev;
    }
    if (prev != NULL && prev->right_child == NULL) {
        prev->right_flag = 1;
        prev->right_child = root;
    }
    prev = root;
}

5. 总结

线索二叉树充分利用了二叉树中的空指针域,给予二叉树一个新特性——通过一次遍历进行线索化后,二叉树中就能保存其结点之间的前驱和后继关系。

所以,如果我们需要频繁遍历二叉树,查找某个结点的直接前驱或后继结点,使用线索二叉树是非常合适的。

此外,由于代码涉及到递归,初次接触可能不好理解,我们可以借助断点进行调试,细致观察线索化的整个过程来帮助理解。

以上就是线索二叉树的原理及创建

完整代码请移步至 GitHub | Gitee 获取。

如有错误,还请指正。

如果觉得写的不错,可以点个赞和关注。后续会有更多数据结构和算法相关文章。

线索二叉树的原理及创建

收藏
评论区

相关推荐

前端学数据结构与算法:二叉树的四种遍历方式及其应用
前言 上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS),最后的层序遍历也叫广度优先遍历(BFS),理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这
JavaScript 中的二叉树以及二叉搜索树的实现及应用
接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:) (https://imghelloworld.osscnbe
从中断机制看 React Fiber 技术
带你了解计算机的中断机制(操作系统心脏)是如何提在 React Fiber 中应用及提高了页面渲染性能和用户体验。 前言 React 16 开始,采用了 Fiber 机制替代了原有的同步渲染 VDOM 的方案,提高了页面渲染性能和用户体验。Fiber 究竟是什么,网上也有很多优秀的技术揭秘文章,本篇主要想从计算机的中断机制来聊聊 React Fiber 技术
DevOps与CICD的区别 及 docker、k8s的CICD思路
1\. DevOps简介DevOps 就是开发(Development)、测试(QA)、运维(Operations)这三个领域的合并。image.png为什么要合并这三个领域?主要是开发和运维的脱节。DevOps是一种思想、一组最佳实践、以及一种文化。DevOps落地实施,从组织架构、设计人员、流程、人员分工、人员技能到工具,变化
11个基于vue的UI框架_U.R.M.L
Element UI 来自中国,由与 Mint UI 相同的开发者所创建。Element UI 是用于 Web 和桌面应用程序的桌面 UI 工具包,如果你需要开发 Electron 应用,这个库会是你的理想之选。 iView 是一个 UI 工具包,其中包含简洁又设计优雅的小部件和各种组件。iView 团队维护非常及时,最近一次的更新在19年3
Mysql中MVCC的使用及原理详解
数据库默认隔离级别:RR(Repeatable Read,可重复读),MVCC主要适用于Mysql的RC,RR隔离级别 创建一张存储引擎为testmvcc的表,sql为:CREATE TABLE testmvcc ( id int(11) DEFAULT NULL, name varchar(11) DEFAULT NULL) ENGINE\InnoDB
一文看懂二叉树的概念和原理
系列文章推荐阅读 0. 前言到目前为止,我们已经讲述了、、、四种数据结构,它们有一个共同的特点,就是它们都是线性表,换句话来说,它们都是线性结构,像一根绳子一样。在文章已经介绍过线性表的定义了,即由若干元素按照线性结构(一对一的关系)组成的有限序列。关键词是一对一的关系。显然,在复杂的现实社会中,这种一对一的关系是不能较好的满足我们的需求的。比如
安利一些强无敌的 NPM 软件包
实用工具 Lodashlodash是一套现代 JavaScript 实用程序库,提供模块化、性能与多种附加功能。可提供关于 JavaScript 数组、对象及其他数据结构的多种实用功能。 安装及示例yarn add lodash 不要滥用,尽量使用 ES 自带方法 。我常用的一些方法如下// 深度比较两个对象的值是否全相等 import isEqu
线索二叉树的原理及创建
【系列推荐阅读】 1. 为什么要用到线索二叉树?我们先来看看普通的二叉树有什么缺点。下面是一个普通二叉树(链式存储方式):乍一看,会不会有一种违和感?整个结构一共有 7 个结点,总共 14 个指针域,其中却有 8 个指针域都是空的。对于一颗有 n 个结点的二叉树而言,总共会有 n+1 个空指针域,这个规律使用所有的二叉树。这么多的空指针域是不
人工智能数学基础-线性代数5:行列式求解线性方程组和拉普拉斯定理
一、逆序及逆序数在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。也就是说,对于n个不同的元素,先规定各元素之间有一个标准次序(例如n个 不同的自然数,可规定从小到大为标准次序),于是在这n个元素的任一排列中,当某两个元素的实际先后次序与标准次序不同时,就说有1个逆序
Ubuntu20.04安装、配置、卸载QT5.9.9与QT creator以及第一个编写QT程序
一、下载与安装QT选择qtopensourcelinuxx645.9.9.run,如果是Chrome点击以后没有反应建议换个浏览器尝试,比如Firefox下载完毕开始安装先使用命令改变qt安装包的权限,以便于后续操作bashchmod +x qtopensourcelinuxx645.9.9.run或者bashchmod u+x qtopensourceli
nodeJS与MySQL实现分页数据以及倒序数据
大家在做项目时肯定会遇到列表类的数据,如果在前台一下子展示,速度肯定很慢,那么我们可以分页展示,比如说100条数据,每10条一页,在需要的时候加载一页,这样速度肯定会变快了。那么这里我给大家介绍如何在nodejs环境中用mysql实现分页。 前面一些必要的配置我先不详细说了,这里主要说的是地址池的配置// 数据库信息var connection mysq
【排序算法动画解】排序介绍及冒泡排序
本文为系列专题的第 12 篇文章。1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 本文先简单介绍一下什么是排序,然后再结合动画介绍暴力排序和冒泡排序。 1. 什么是排序?排序在日常生活中无处不在。比如考试成绩的排名、体育课的从低到高的队形、网购时按价格升序排列或降序排列等等。| 姓名 | 学号 | 班级 | 成绩 || | | |
直接裂开!京东二面被问SpringBoot整合MongoDB,我不会啊
开始进入正题 一、技术介绍@ MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是可以应用于各种规模的企业、各个行业以及各类应用程序的开源数据库。作为一个适用于敏捷开发的数据库,MongoDB的数据模式可以随着应用程序的发展而灵活地更新。与此同时,它也为开发人员 提供了传统数据库的功能:二级索引,完整的查询系统以及严格一致性等等。
JAVA回调机制(CallBack)之小红是怎样买到房子的??
JAVA回调机制CallBack 序言最近学习java,接触到了回调机制(CallBack)。初识时感觉比较混乱,而且在网上搜索到的相关的讲解,要么一言带过,要么说的比较单纯的像是给CallBack做了一个定义。当然了,我在理解了回调之后,再去看网上的各种讲解,确实没什么问题。但是,对于初学的我来说,缺了一个循序渐进的过程。此处,将我对回调机制的个人理解,按