线索二叉树

1. 为什么需要线索二叉树

普通二叉树的结点通常包含：

• 左孩子指针
• 数据
• 右孩子指针

但在一棵有 $n$ 个结点的二叉树中，一共有 $2n$ 个指针域，连接孩子的边只有 $n-1$ 条，因此会有：

个空指针。

线索二叉树的核心思想是：

利用这些原本为空的指针，保存结点在某种遍历顺序下的前驱和后继。

2. 什么是前驱和后继

前驱和后继并不是指父结点和孩子结点，而是指结点在某种遍历序列中的前一个和后一个结点。

例如，一棵树的中序遍历结果是：

那么：

• $A$ 的中序前驱是 $E$
• $A$ 的中序后继是 $F$
• $D$ 没有中序前驱
• $G$ 没有中序后继

如果把结点的空指针指向这些前驱或后继，这个指针就称为线索。

3. 线索二叉树的基本结构

经过线索化后，一个指针可能有两种含义。

以左指针为例：

• 指向真正的左孩子
• 指向遍历序列中的前驱

因此，需要为左右指针分别增加一个标志位：

• 左标志：说明左指针指向左孩子还是前驱
• 右标志：说明右指针指向右孩子还是后继

具体使用 0 还是 1 表示线索无所谓，关键是必须能够区分：

指针是孩子指针，还是线索指针。

4. 线索化是什么意思

把普通二叉树中的空指针改造成前驱或后继线索，这个过程称为线索化。

线索化的本质是对二叉树进行一次遍历

根据采用的遍历方式，可以分为：

• 先序线索二叉树
• 中序线索二叉树
• 后序线索二叉树

其中最常见的是中序线索二叉树。

二叉树在线索化后，仍不能有效解决后续线索二叉树中求后续后继

至于为什么，我懒得去看了，当结论记下来就好了。

看网课说这个内容似乎并不太重要，近些年来都只考选择题。

四本书学完有空可以看一看代码。

那就只能美美跳过了。