【数据结构】如何解决二叉树在遍历查找前驱与后继的问题？线索二叉树来帮您……

导读

大家好，很高兴又和大家见面啦！！！

经过前面的介绍，相信大家对二叉树的基本操作有了更深的理解了。

在二叉树的基本操作中，遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

在介绍二叉树的遍历时，我们介绍了两种实现方式——通过递归实现二叉树的先序、中序和后序遍历和借助栈来实现非递归的先序、中序和后序遍历。

从二叉树的遍历的实现来看，不管是递归还是通过栈来实现，当我们遍历到最左侧的叶结点时，如果我们需要继续往后遍历，我们都需要借助该结点的父结点完成后续遍历，如下所示：

上图中的二叉树的最左侧的叶子结点为结点6，我们通过三种遍历方式对后续结点的访问情况如下：

• 在先序遍历中，第一次通过左子树回归，找到父结点后，才能访问右子树；
• 在中序遍历中，第一次通过左子树回归，找到父结点后，才能访问父结点；
• 在后序遍历中，第一次通过左子树回归，找到父结点后，才能访问右子树；

对于结点6而言，它的后继结点的访问始终绕不开父结点。那我们能不能做到不借助父结点直接找到其后继结点呢？这里我们以中序遍历为例来说明，如下所示：

该二叉树的中序遍历序列为：

6 8 9 10 11 13 16 19 20 25 28 29 30 32 34 39 40 48

从遍历序列中我们可以直观的看到结点6的直接后继为结点8。而对于结点6而言，结点8作为其父亲结点，我们是无法直接访问的，我们能够访问的只有结点6的左右孩子。

在这种情况下，如果我们要访问结点6的父亲结点，我们要么通过函数回归的方式，要么通过栈存储其父结点的方式完成访问。

如果我们能够优化这一访问过程，即在访问完结点6后，直接访问结点8，那我们的访问效率是不是就可以大幅度提升呢？如果优化这一访问过程，这就是我们今天要提到的线索二叉树……

一、线索二叉树的定义

二叉树的线索化又称为线索二叉树。这是一种对普通二叉树进行优化的数据结构，通过利用空指针存储遍历顺序下的前驱或后继节点信息，从而提升遍历效率。

1.1 三叉链表

我们在完成二叉树的遍历时，不管是通过递归完成还是通过栈来完成，实际上都是为了能够在访问完孩子结点后还能够正常访问父结点。

传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱和后继。那如果我能够在访问完一个结点后不仅能够找到他的直接前驱和直接后继，那么是不是就不需要再消耗额外的空间来记录父亲结点了呢？

这里有个典型的例子——三叉链表。

在三叉链表的结点中，通过三个指针域分别指向结点的父结点与左右孩子。在这种结构下，我们确实是不需要再消耗额外的空间来记录父亲结点，通过这种结构来提高遍历的效率是一种可行的方式，

1.2 线索二叉树的功能

为了能够让普通的二叉树也能够像三叉链表一样可以直接访问该结点的前驱与后继，因此我们引入了线索二叉树。

线索二叉树就是为了加快找到结点的前驱和后继的速度。

二、线索二叉树的结点

2.1 二叉树中的空指针数

从二叉树的定义中我们可以获取一个信息：

• 利用空指针存储遍历顺序下的前驱或后继节点信息

那么对于一棵二叉树而言，它又有多少空指针呢？

在上图中我们可以看到

• 每个度为0的结点都有2个空指针（如结点32）
• 每个度为1的结点都有1个空指针（如结点13）
• 每个度为2的结点都有0个空指针（如结点20）

因此空指针的总数为：$2\times n_0+1\times n_1+0\times n_2=2n_0+n_1$

又因为：$n_0=n_2+1$

所以空指针总数为 $n_0+n_1+n_0=n_0+n_1+n_2+1=n+1$。

如果我们将这些空指针利用起来，那么我们确实不再需要额外的存储空间来存放父结点的信息。为了更好的利用这些空指针，我们应该对二叉树的结点做出哪些改动呢？

2.2 线索二叉树的结点结构

规定：

• 二叉树的结点若无左子树，则令其左孩子指针Lchild指向其前驱结点
• 二叉树的结点若无右子树，则令其右孩子指针Rchild指向其后继结点
• 为了区别左右孩子指针的指向对象，还需增加2个标志域
• 通过标志域判断当前指针指向的是孩子结点还是前驱/后继结点

在线索二叉树中，指针域的指向无非就两种情况：

• 指向该结点的左/右孩子结点
• 指向该结点的前驱/后继结点

既然如此，我们不妨通过0/1来对其进行标记：

• 标志域为0：该指针指向该结点的左/右孩子结点
  • ltag == 0：左指针指向左孩子
  • rtag == 0：右指针指向右孩子
• 标志域为1：该指针指向该结点的前驱/后继结点
  • ltag == 1：左指针指向前驱
  • rtag == 1：右指针指向后继

三、线索二叉树的存储结构

明确了线索二叉树的结点结构后，我们就可以通过C语言完成结点的定义：

typedef int ElemType;//数据的数据类型
typedef bool TagType;//标志的数据类型
typedef struct ThreadNode {
	ElemType data;//数据域
	struct ThreadNode* lchild, * rchild;//指针域
	TagType ltag, rtag;//标志域
}ThreadNode, * ThreadTree;

以这种结点构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。

3.1 线索与孩子的区别

在线索二叉树中，我们需要区分线索与孩子的区别，如下所示：

在上图中的这棵中序线索二叉树中，数据在逻辑上是满足的树形结构，即：

• 元素之间满足一对多的关系

因此我们可以认为所有的结点都存在一个指向其孩子结点的指针：

但是对于这些孩子为空的指针，我们则引入了线索，就好比它在逻辑上比原先多了一个线索指针：

从上图中我们可以很直观的看到，并不是每一个指针都引入了一个线索指针，只有那些原先是空结点的指针才引入了线索指针。

我们不难发现，这些空指针不仅没有什么实质性的作用，而且还会消耗内存空间，我们完全可以通过是否引入了线索指针来判断该指针的孩子情况：

• 引入了线索指针，则该结点的孩子指针为空指针
• 未引入线索指针，则该结点的孩子指针指向其孩子结点

基于这种条件，我们就可以将线索指针与空孩子指针进行合并：

而对于一个指针来说，它不可能存在两个指向，因此我们可以认为，孩子指针与线索指针合并后的指针空间实际指向的是其线索结点（前驱结点/后继结点），同时它还虚拟指向其孩子结点（空结点）。

那我们就可以得到以下结论：

• 线索二叉树中，一个结点的孩子指针一定会指向其孩子结点，但不一定指向其前驱/后继；
• 线索二叉树中，一个结点的线索指针对应的孩子指针一定为空指针；

这两个结论是我们能否理解线索指针与孩子指针的关键，大家一定要仔细琢磨一下。

3.2 线索二叉树的空指针

对于非线性的二叉树而言，其遍历序列是一个线性结构：

• 除了首元素和尾元素以外，其余的每个元素都只有唯一的前驱与唯一的后继
• 首元素只有唯一的后继结点
• 尾元素只有唯一的前驱结点

因此引入了线索的线索二叉树，会存在两个空指针：

• 首元素的前驱指针
• 尾元素的后继指针

可以看到，一棵引入了线索的二叉树，其空指针由原先的 $n+1$ 个，缩减到了 $2$ 个，这样不仅大大提高了空间的利用率，也提高了二叉树的遍历效率。

结语

在今天的内容中我们介绍了线索二叉树的相关概念：

• 线索：指向前驱结点和后继结点的指针
• 线索二叉树：引入了线索的二叉树

为了区分一个结点的指针域指向的是线索还是孩子，我们通过在结点中增加标志域进行判断：

• 标志域为0：该指针指向的是孩子结点
• 标志域为1：该指针指向的是线索结点

我们之所以要引入线索二叉树，是为了：

• 提高二叉树的查找前驱结点与后继结点的速度

今天的内容到这里就全部结束了，在下一篇内容中我们将会介绍《二叉树的线索化》，大家记得关注哦！

如果大家喜欢博主的内容，可以点赞、收藏加关注支持一下博主，当然也可以转发将博主的内容给身边需要的朋友。最后感谢各位朋友的支持，咱们下一篇再见！！！