408

数据结构

DS-04-04 线索二叉树

---

一、定位信息

项目	内容
圈层	核心层（大纲考点）
前置知识	二叉树的链式存储、中序遍历（递归与非递归）、空指针域的利用
知识网络定位	线索二叉树是二叉树遍历的优化方案，利用空指针域存储前驱/后继信息，实现高效遍历
考点热度	H级（高频重点）：近5年出现≥3次，常考线索化过程及线索遍历

---

二、知识点讲解

2.1 线索二叉树的概念

$n$ 个节点的二叉链表中有 $n+1$ 个空指针域，线索二叉树利用这些空指针域存放遍历序列中的前驱和后继信息。

规定：

• 若节点有左子树，则 lchild 指向左孩子；否则 lchild 指向该节点在指定遍历序列中的前驱
• 若节点有右子树，则 rchild 指向右孩子；否则 rchild 指向该节点在指定遍历序列中的后继

为区分指针是指向孩子还是指向前驱/后继，增加两个标志域：

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;            // 标志域：0表示指向孩子，1表示指向前驱/后继
} ThreadNode, *ThreadTree;

标志位含义：

• ltag = 0：lchild 指向左孩子
• ltag = 1：lchild 指向前驱
• rtag = 0：rchild 指向右孩子
• rtag = 1：rchild 指向后继

2.2 中序线索二叉树的构造

构造过程：对二叉树进行中序遍历，在遍历过程中修改空指针域。

// 中序线索化
// 全局变量 pre 指向当前访问节点的前驱
ThreadNode *pre = NULL;

// 中序线索化主函数
void CreateInThread(ThreadTree T) {
    pre = NULL;                // 初始化前驱为空
    if (T != NULL) {
        InThread(T);           // 中序遍历并线索化
        pre->rchild = NULL;    // 处理最后一个节点的后继
        pre->rtag = 1;         // 最后一个节点无后继，线索指向空
    }
}

// 中序遍历并线索化（递归）
void InThread(ThreadTree p) {
    if (p == NULL) return;     // 空节点返回
    
    InThread(p->lchild);       // 1. 线索化左子树
    
    // 2. 处理当前节点 p
    if (p->lchild == NULL) {   // p 没有左孩子
        p->ltag = 1;           // 标记为线索
        p->lchild = pre;       // 左指针指向前驱
    }
    if (pre != NULL && pre->rchild == NULL) {  // 前驱没有右孩子
        pre->rtag = 1;         // 标记为线索
        pre->rchild = p;       // 前驱的右指针指向当前节点（后继）
    }
    pre = p;                   // 更新前驱为当前节点
    
    InThread(p->rchild);       // 3. 线索化右子树
}

算法步骤详解：

1. 对左子树递归线索化
2. 处理当前节点：若左孩子为空，建立前驱线索；若前驱的右孩子为空，建立后继线索
3. 更新前驱指针为当前节点
4. 对右子树递归线索化

2.3 中序线索二叉树的遍历

// 在中序线索二叉树中找到以 p 为根的子树中，中序遍历的第一个节点
// 即"最左下的节点"
ThreadNode *FirstNode(ThreadNode *p) {
    // 沿左孩子指针一直走到最左
    while (p->ltag == 0) {     // ltag==0 表示有左孩子
        p = p->lchild;
    }
    return p;                  // 最左下的节点就是中序第一个
}

// 在中序线索二叉树中找到节点 p 的后继
ThreadNode *NextNode(ThreadNode *p) {
    if (p->rtag == 1) {        // rtag==1 表示有后继线索
        return p->rchild;      // 直接返回后继
    } else {                   // rtag==0 表示有右子树
        return FirstNode(p->rchild);  // 右子树的最左下节点
    }
}

// 中序线索二叉树的中序遍历（无栈、无递归）
void InOrder_Thread(ThreadTree T) {
    for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) {
        visit(p);              // 访问节点
    }
}

核心优势：线索二叉树的遍历不需要栈和递归，只需要沿着线索指针移动即可，空间复杂度降为 $O(1)$。

2.4 前序线索二叉树与后序线索二叉树

前序线索化：按先序遍历的顺序建立前驱/后继线索。线索化过程中只需将中序遍历改为先序遍历。

后序线索化：按后序遍历的顺序建立前驱/后继线索。

注意：后序线索二叉树的遍历较为复杂，因为后序中节点的后继可能不直接可见，需要借助栈或三叉链表。

2.5 三种线索二叉树对比

对比项	前序线索二叉树	中序线索二叉树	后序线索二叉树
线索依据	先序序列	中序序列	后序序列
找第一个节点	根节点	最左下节点	最左下节点
找后继	较简单	规则清晰	较复杂，需栈
遍历实现	较简单	经典、规则清晰	最复杂
实际使用	较少	最常用	较少
考频	低	高	低

---

三、记忆与理解辅助

技巧1：线索化的核心口诀

"空指针不浪费，左指向前驱，右指向后继；标志0是孩子，标志1是线索"

技巧2：中序线索遍历的"最左下"法则

找中序第一个节点：一路向左（ltag==0时一直走左孩子） 找节点p的后继：有右子树则找右子树最左下，否则右线索直接指向后继

技巧3：线索化过程与中序遍历的关系

线索化 = 中序遍历 + 修改空指针。只要你会写中序非递归遍历，线索化就是在遍历过程中多做两件事：①判断并修改空的lchild；②判断并修改前驱的空的rchild。

---

四、例题与精解

例题1（基础巩固）

题目：对以下二叉树进行中序线索化，画出线索化后的结构：

        A
       / \
      B   C
     / \
    D   E

中序序列为：D, B, E, A, C

命题意图：考查中序线索化的具体过程和结果。

审题分析：需要找出每个节点的前驱和后继，然后用线索替代空指针。

解题思路：先写出中序序列，然后确定每个节点的前驱后继，修改空指针域。

完整步骤：

Step 1：中序序列：D → B → E → A → C

Step 2：确定每个节点的前驱和后继：

节点	前驱	后继	左孩子	右孩子
D	无	B	无（空）	无（空）
B	D	E	D	E
E	B	A	无（空）	无（空）
A	E	C	B	C
C	A	无	无（空）	无（空）

Step 3：修改空指针域：

• D：lchild → NULL（前驱为空，ltag=1），rchild → B（后继，rtag=1）
• E：lchild → B（前驱，ltag=1），rchild → A（后继，rtag=1）
• C：lchild → A（前驱，ltag=1），rchild → NULL（后继为空，rtag=1）

Step 4：线索化后的结构：

        A
       / \
      B   C
     / \
    D   E

线索关系：
D.lchild = NULL (前驱为空)
D.rchild = B (后继)
E.lchild = B (前驱)
E.rchild = A (后继)
C.lchild = A (前驱)
C.rchild = NULL (后继为空)

答案：如上所示，D、E、C 的空指针域被线索替代。

方法反思：线索化的关键步骤是：①写中序序列 ②找每个节点的前驱后继 ③用线索替代空指针。

例题2（中等提升）

题目：在中序线索二叉树中，编写算法求指定节点 $p$ 在中序遍历中的前驱节点。

命题意图：考查对中序线索二叉树结构的理解和算法设计能力。

审题分析：需要分两种情况讨论：$p$ 有左子树和 $p$ 没有左子树。

解题思路：

• 若 p->ltag == 1，则 p->lchild 直接指向前驱
• 若 p->ltag == 0，则前驱是 $p$ 的左子树中"最右下的节点"

完整步骤：

// 求中序线索二叉树中节点 p 的前驱
// 分两种情况：
//   情况1：p 有左子树 → 前驱是左子树的最右下节点
//   情况2：p 无左子树 → lchild 直接指向前驱
ThreadNode *PriorNode(ThreadNode *p) {
    if (p->ltag == 1) {        // 情况2：左指针是线索
        return p->lchild;      // 直接返回前驱
    }
    // 情况1：有左子树，找左子树的最右下节点
    ThreadNode *q = p->lchild; // 进入左子树
    while (q->rtag == 0) {     // 沿右孩子指针一直走到最右下
        q = q->rchild;
    }
    return q;                  // 最右下节点就是前驱
}

方法反思：

1. 中序遍历中，节点 $p$ 的前驱是其左子树的"最右下"节点
2. 中序遍历中，节点 $p$ 的后继是其右子树的"最左下"节点
3. 这两个规则是对称的，记住一个即可推导另一个

---

五、考情分析

项目	内容
考查频次	近5年约3-4次，是高频考点
常见题型	选择题（判断线索指向、求遍历结果）、大题（线索化算法、遍历算法）
分值占比	选择题2分 + 大题5-8分
命题趋势	中序线索二叉树是考查重点，特别是线索化过程和基于线索的遍历算法。近年倾向于考查"求前驱/后继"的算法
典型考点	①中序线索化过程 ②线索遍历（无栈无递归）③求前驱/后继 ④标志域的含义

---

六、易错点提醒

易错点1

• 错误表现：混淆 ltag/rtag 的含义，以为 0 表示线索
• 错误原因：记忆不清
• 正确理解：0 表示指向孩子（正常指针），1 表示指向前驱/后继（线索）

易错点2

• 错误表现：线索化时忘记处理最后一个节点的 rchild
• 错误原因：最后一个节点的后继为空，需要特殊处理
• 正确理解：CreateInThread 函数最后需要将 pre->rchild = NULL 和 pre->rtag = 1，表示最后一个节点无后继

易错点3

• 错误表现：在前序线索化中，当 p->ltag==0 时对左孩子递归线索化，但可能破坏已建立的线索
• 错误原因：前序线索化中，先处理当前节点再递归，可能导致递归时线索已改变
• 正确理解：前序线索化需要在递归前先保存左右孩子指针，或者使用非递归方式实现

易错点4

• 错误表现：认为线索二叉树的遍历仍需要栈
• 错误原因：没有理解线索化的目的
• 正确理解：线索化的核心目的就是消除递归/栈，实现 $O(1)$ 空间的遍历

---

七、来源标注

• 依据2026考研统考408大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据《数据结构》王道考研辅导讲义