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

线索二叉树的前驱后继查找三张流程图彻底掌握三种遍历规则准备数据结构面试或研究生考试时线索二叉树的前驱后继查找是个高频考点。很多同学在面对先序、中序、后序三种不同遍历方式下的查找规则时容易混淆。本文将用最直观的流程图解法帮你彻底理清思路不再死记硬背。1. 线索二叉树的核心概念线索二叉树本质上是对普通二叉树的优化通过利用原本为空的指针域来存储遍历顺序信息。理解以下三个关键点至关重要空指针利用率n个结点的二叉树有n1个空指针线索化就是利用这些空指针存储前驱/后继信息标志位含义ltag0左指针指向左孩子ltag1左指针指向前驱rtag0右指针指向右孩子rtag1右指针指向后继存储结构typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; } ThreadNode, *ThreadTree;注意线索化过程本质上是将遍历序列的线性关系编码到二叉树结构中这使得我们能够高效地查找前驱和后继。2. 中序线索二叉树最直观的案例中序线索化是最容易理解的因为中序遍历序列与二叉搜索树的排序结果一致。查找规则可以用以下流程图概括开始 ↓ 当前结点rtag是否为1 → 是 → 右指针即后继 ↓否 右子树的最左下结点就是后继前驱查找对称同理。来看几个典型场景有右子树的情况后继必定在右子树的最左下角例在下图的中序线索树中结点B的后继是EA / \ B C \ D / E无右子树的情况直接通过rtag1的线索找到后继例上图中E的后继是A真题示例2014年统考真题中问结点x的左右线索指向。正确答案是D(b,a)这正是中序遍历序列中x的前驱和后继。3. 先序线索二叉树注意陷阱情况先序遍历的顺序是根左右这导致查找后继时有特殊场景开始 ↓ 当前结点rtag是否为1 → 是 → 右指针即后继 ↓否 是否有左孩子 → 是 → 左孩子即后继 ↓否 右孩子即后继特别注意当某结点是父结点的右孩子且没有自己的左孩子时它的后继不是简单的右孩子而是需要回溯到父结点的后继。这也是先序线索树不如中序直观的原因。记忆口诀有左取左有左孩子时左孩子就是后继无左取右没有左孩子时右孩子是后继无孩看线索没有孩子时通过rtag线索找表格对比先序与中序的区别特征中序线索树先序线索树后继查找右子树的最左下优先左孩子次选右孩子前驱查找左子树的最右下必须借助父指针或栈完全线索化可以右子树特殊情况无法完全4. 后序线索二叉树最复杂的场景后序遍历(左右根)的特性使得查找后继最为复杂经常需要三叉链表存储父指针开始 ↓ 当前结点rtag是否为1 → 是 → 右指针即后继 ↓否 是否是父结点的右孩子 → 是 → 父结点即后继 ↓否 是父结点的左孩子 → 是 → 父结点的右子树的最左下结点关键点只有知道父结点信息才能准确找到后继叶结点的后继通常是其父结点根结点没有后继实战技巧遇到后序线索树问题时先画出完整的树结构标出父子关系再按步骤分析。真题示例2013年统考题考察叶结点X有左兄弟Y时右线索指向正确答案是A(X的父结点)这正是后序遍历的特性决定的。5. 综合对比与解题策略将三种遍历方式的前驱后继查找规则总结如下表遍历方式前驱查找规则后继查找规则需要额外信息中序左子树的最右下结点右子树的最左下结点无先序无法直接获取(需父指针)优先左孩子无左则取右孩子无后序优先右孩子无右则取左孩子通常为父结点需要父指针解题四步法判断题目问的是哪种遍历方式确认是查找前驱还是后继检查ltag/rtag标志位根据对应遍历的流程图逐步推导最后记住这个万能口诀0孩1驱中序最顺先序看左后序找爸。掌握了这套方法线索二叉树的面试题就变成了按图索骥的过程再也不用死记硬背各种特殊情况了。