线索二叉树的优点

二叉树是一种可以使用数组或链表表示的数据结构。当使用链表表示二叉树时，列表的节点不存储在相邻的内存地址中。它们通过与树相关的父子关系相互链接。

在此表示中，每个节点包含三个不同的组件

1. 一个指向左节点的指针，
2. 一个指向右节点的指针，以及
3. 一个数据元素。

如果二叉树中的节点没有左子节点或右子节点，或者是一个叶节点，那么缺失的子节点将由一个 NULL 指针表示。

让我们以以下二叉树为例。

图 1。二叉树

上图表明，树中有许多节点在其左子节点指针或右子节点指针中包含 NULL 值。我们可以利用这些 NULL 值占用的空间来存储某种有价值的信息。

利用此空间的一种可行方法是使用一个特殊指针指向树中的上方节点（即祖先）。这些特殊指针称为线索，包含此类指针的二叉树称为穿线二叉树。

穿线二叉树是普通二叉树的一种变体，它可以实现更快的树遍历，并且不需要堆栈或递归。它通过将叶节点的空指针指向其后续节点（in-order successor）或前序节点（in-order predecessor）来减少内存浪费。

在接下来的教程中，我们将学习穿线二叉树的优点。但在开始之前，让我们简要了解一下穿线二叉树及其类型。

理解穿线二叉树

穿线二叉树是一种二叉树，其中所有左子节点指针为 NULL 的节点指向其后续节点（in-order predecessor），所有右子节点指针为 NULL 的节点指向其前序节点（in-order successor）。

此外，穿线二叉树的最左边和最右边的子节点指针始终指向 NULL，因为它们没有后续节点或前序节点。

让我们以穿线二叉树的以下示例来理解上述陈述。

图 2。穿线二叉树

在上图中，我们可以看到节点值 7 的右指针指向 9。

1. 现在我们将检查节点 9 的左指针，如果它是 NULL，我们将将其地址修改为节点的后续节点，即 7。
2. 然后我们将检查右指针，如果它为 NULL，我们将将其引用修改为前序节点，即 11。因此，它将指向 11。
3. 如上图所示，我们使用线索（由虚线表示）指向左/右指针中的后续节点/前序节点，这就是它被称为穿线二叉树的原因。
4. 此外，该树的最左边指针（即节点值 3 的左指针）和最右边指针（即节点值 19 的右指针）将指向 NULL。

创建此类结构的主要目标是，在不借助额外数据结构（如辅助堆栈）或内存的情况下，实现二叉树的中序和前序遍历的快速进行。

理解穿线二叉树的类型

穿线二叉树有两种类型

1. 单穿线二叉树
2. 双穿线二叉树

让我们简要了解一下前面提到的类型。

单穿线二叉树

单穿线二叉树是一种穿线二叉树，其中只有右侧的 NULL 指针被设置为指向后续节点（in-order successor）。

单穿线二叉树中节点的结构

穿线二叉树中节点的结构与普通二叉树非常相似；但是，有一些调整。在穿线二叉树中，我们使用额外的布尔变量来表示节点结构。对于单穿线二叉树，我们只使用一个变量来表示右线索。

让我们以 C++ 语言中的一个代码片段为例，来说明节点的结构。

语法

现在让我们看一张描绘单穿线二叉树示例的图。

图 3。单穿线二叉树

在上图中，我们可以看到节点值 10 不包含任何子节点。因此，节点值 10 的右指针为 null；因此，它通过线索指向其后续节点，即节点值 20。同样，该树中其他具有右侧空指针的节点也指向其后续节点，如图所示。

双穿线二叉树

双穿线二叉树是一种穿线二叉树，其中左侧和右侧的 NULL 指针都被设置为分别指向后续节点（in-order predecessor）和前序节点（in-order successor）。（在此，左线索支持树的反向中序遍历。）
双穿线二叉树中节点的结构

我们将使用两个布尔变量来表示双穿线二叉树的左线索和右线索。

让我们以 C++ 语言中的一个代码片段为例，来说明节点的结构。

语法

在上面的代码片段中，布尔变量 left_thread 和 right_thread 帮助我们区分左/右指针存储的是后续节点/前序节点还是左/右子节点。

现在让我们看一张描绘单穿线二叉树示例的图。

图 4。双穿线二叉树

上图是双穿线二叉树的表示。在这里，我们可以看到节点值 30 没有左子节点和右子节点。因此，其左指针指向其后续节点，即节点值 20，其右指针指向其前序节点，即节点值 40。类似地，该树中其他具有左/右空指针的节点通过线索指向其后续节点/前序节点。

理解穿线二叉树的优点

与非穿线二叉树相比，穿线二叉树有许多优点。其中一些列在下面

1. 使用穿线二叉树的第一个优点是，遍历操作比非穿线二叉树快得多，因为穿线二叉树支持非递归实现，可以执行得更快，并且不需要堆栈管理。
2. 使用穿线二叉树的第二个优点是，我们可以有效地确定从任何节点开始的后续节点和前序节点。然而，在非穿线二叉树的情况下，这项活动非常耗时且繁琐，因为它使用堆栈来提供树中的向上指向信息。在穿线二叉树中，可以通过线索而不是使用堆栈机制来完成同样的事情。
3. 穿线二叉树的另一个优点是可以从一个节点访问另一个节点。线索通常是向上的，而链接是向下的。因此，在一个穿线树中，您可以沿其方向移动，并且其节点是循环链接的。这在非穿线二叉树中是不可能的，因为我们只能从根节点开始向下移动。
4. 使用穿线二叉树的另一个优点是它减少了内存浪费。当普通二叉树的左/右指针为 NULL 时，会浪费内存。然而，可以通过穿线二叉树存储其后续节点/前序节点来克服这个问题。
5. 还可以使用双穿线二叉树执行反向遍历。
6. 穿线二叉树的中序遍历速度很快，因为我们可以在 O(1) 时间内获得下一个节点，而普通二叉树需要 O(height) 时间。但是，穿线二叉树中的插入和删除等操作需要更多时间。

理解穿线二叉树的一些缺点

现在让我们讨论一下穿线二叉树的一些缺点。

1. 穿线二叉树的主要缺点是其复杂的插入和删除操作。这些操作变得更加耗时，并且其过程非常复杂，因为它需要存储具有空左/右指针的节点的后续节点/前序节点。
2. 为了区分线索和普通链接，还需要额外的内存，即用于左线索和右线索的变量。（但有更有效的方法来区分线索和普通链接。）

结论

上述教程向我们介绍了穿线二叉树及其类型。我们还讨论了穿线二叉树的各种优点和一些缺点。