数据结构面试必考：线索二叉树的前驱后继查找，一张图搞定三种遍历方式

线索二叉树的前驱后继查找：三张流程图彻底掌握三种遍历规则

准备数据结构面试或研究生考试时，线索二叉树的前驱后继查找是个高频考点。很多同学在面对先序、中序、后序三种不同遍历方式下的查找规则时容易混淆。本文将用最直观的流程图解法，帮你彻底理清思路，不再死记硬背。

1. 线索二叉树的核心概念

线索二叉树本质上是对普通二叉树的优化，通过利用原本为空的指针域来存储遍历顺序信息。理解以下三个关键点至关重要：

• 空指针利用率：n个结点的二叉树有n+1个空指针，线索化就是利用这些空指针存储前驱/后继信息
• 标志位含义：
  • ltag=0：左指针指向左孩子
  • ltag=1：左指针指向前驱
  • rtag=0：右指针指向右孩子
  • rtag=1：右指针指向后继
• 存储结构：

  typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; } ThreadNode, *ThreadTree;

注意：线索化过程本质上是将遍历序列的线性关系编码到二叉树结构中，这使得我们能够高效地查找前驱和后继。

2. 中序线索二叉树：最直观的案例

中序线索化是最容易理解的，因为中序遍历序列与二叉搜索树的排序结果一致。查找规则可以用以下流程图概括：

开始 ↓ 当前结点rtag是否为1？ → 是 → 右指针即后继 ↓否 右子树的最左下结点就是后继

前驱查找对称同理。来看几个典型场景：

1. 有右子树的情况：

   • 后继必定在右子树的最左下角
   • 例：在下图的中序线索树中，结点B的后继是E

     A / \ B C \ D / E

2. 无右子树的情况：

   • 直接通过rtag=1的线索找到后继
   • 例：上图中E的后继是A

真题示例：2014年统考真题中，问结点x的左右线索指向。正确答案是D(b,a)，这正是中序遍历序列中x的前驱和后继。

3. 先序线索二叉树：注意"陷阱"情况

先序遍历的顺序是"根左右"，这导致查找后继时有特殊场景：

开始 ↓ 当前结点rtag是否为1？ → 是 → 右指针即后继 ↓否 是否有左孩子？ → 是 → 左孩子即后继 ↓否 右孩子即后继

特别注意：当某结点是父结点的右孩子且没有自己的左孩子时，它的后继不是简单的右孩子，而是需要回溯到父结点的后继。这也是先序线索树不如中序直观的原因。

记忆口诀：

• 有左取左：有左孩子时左孩子就是后继
• 无左取右：没有左孩子时右孩子是后继
• 无孩看线索：没有孩子时通过rtag线索找

表格对比先序与中序的区别：

4. 后序线索二叉树：最复杂的场景

后序遍历("左右根")的特性使得查找后继最为复杂，经常需要三叉链表存储父指针：

开始 ↓ 当前结点rtag是否为1？ → 是 → 右指针即后继 ↓否 是否是父结点的右孩子？ → 是 → 父结点即后继 ↓否 是父结点的左孩子？ → 是 → 父结点的右子树的最左下结点

关键点：

1. 只有知道父结点信息才能准确找到后继
2. 叶结点的后继通常是其父结点
3. 根结点没有后继

实战技巧：遇到后序线索树问题时，先画出完整的树结构，标出父子关系，再按步骤分析。

真题示例：2013年统考题考察叶结点X有左兄弟Y时右线索指向，正确答案是A(X的父结点)，这正是后序遍历的特性决定的。

5. 综合对比与解题策略

将三种遍历方式的前驱后继查找规则总结如下表：

解题四步法：

1. 判断题目问的是哪种遍历方式
2. 确认是查找前驱还是后继
3. 检查ltag/rtag标志位
4. 根据对应遍历的流程图逐步推导

最后记住这个万能口诀："0孩1驱，中序最顺，先序看左，后序找爸"。掌握了这套方法，线索二叉树的面试题就变成了按图索骥的过程，再也不用死记硬背各种特殊情况了。