线索二叉树

在本文中，我们将详细了解线索二叉树。

线索二叉树是什么意思？

在二叉树的链式表示中，超过一半的链接字段包含 NULL 值，这导致存储空间的浪费。如果一个二叉树包含 n 个节点，那么 n+1 个链接字段包含 NULL 值。因此，为了有效地管理空间，Perlis 和 Thornton 设计了一种方法，其中 NULL 链接被替换为称为线索的特殊链接。这种带有线索的二叉树称为线索二叉树。线索二叉树中的每个节点都包含指向其子节点的链接或指向树中其他节点的线索。

线索二叉树的类型

线索二叉树有两种类型

• 单向线索二叉树
• 双向线索二叉树

单向线索二叉树

在单向线索二叉树中，线索将出现在节点的右链接字段或左链接字段中。如果它出现在节点的右链接字段中，那么它将指向执行中序遍历时将出现的下一个节点。这种树称为右线索二叉树。如果线索出现在节点的左字段中，那么它将指向节点的中序前驱。这种树称为左线索二叉树。 左线索二叉树的使用频率较低，因为它们没有右线索二叉树的最后一个优点。在单向线索二叉树中，最后一个节点的右链接字段和第一个节点的左链接字段包含 NULL。为了将线索与普通链接区分开来，它们用虚线表示。

上图显示了这棵二叉树的中序遍历结果是 D, B, E, A, C, F。当这棵树表示为右线索二叉树时，叶子节点 D 的右链接字段（包含 NULL 值）被替换为一个指向节点 B 的线索，节点 B 是节点 D 的中序后继。同样，其他右链接字段中包含值的节点将包含 NULL 值。

双向线索二叉树

在双向线索二叉树中，包含 NULL 值的节点的右链接字段被一个指向节点中序后继的线索替换，包含 NULL 值的节点的左链接字段被一个指向节点中序前驱的线索替换。

上图显示了这棵二叉树的中序遍历结果是 D, B, E, G, A, C, F。如果我们考虑双向线索二叉树，节点 E 的左字段包含 NULL，被一个指向其中序前驱（即节点 B）的线索替换。类似地，对于节点 G，其右链接字段和左链接字段包含 NULL 值，被线索替换，使得右链接字段指向其中序后继，左链接字段指向其中序前驱。同样，其他链接字段中包含 NULL 值的节点也被线索填充。

在上面双向线索二叉树的图中，我们注意到第一个节点不可能有左线索，最后一个节点不可能有右线索。这是因为它们分别没有中序前驱和中序后继。这由指向空白的线索表示。因此，为了保持线索的统一性，我们维护一个特殊的节点，称为头节点。头节点不包含任何数据部分，其左链接字段指向根节点，其右链接字段指向自身。如果这个头节点包含在双向线索二叉树中，那么这个节点就成为第一个节点的中序前驱和最后一个节点的中序后继。现在，第一个节点的左链接字段和最后一个节点的右链接字段的线索将指向头节点。

线索二叉树中序遍历算法

说明

在上面的例子中，我们创建了一个线索二叉树用于各种操作。

输出

线索二叉树的优点

• 在线索二叉树中，节点在树中的遍历是线性和快速的，因此不需要栈。如果使用栈，则会消耗大量内存和时间。
• 它更通用，因为可以通过简单地沿着线索和链接有效地确定任何节点的后继和前驱。它几乎就像一个循环链表。

线索二叉树的缺点

• 当实现时，线索二叉树需要为每个节点维护额外的信息，以指示每个节点的链接字段是指向普通节点还是节点的后继和前驱。
• 线索二叉树的插入和删除操作更耗时，因为需要同时维护线索和普通链接。