线索二叉树

利用空指针加速遍历

n 个结点的二叉树有 n+1 个空指针（2n 个指针域中只有 n-1 条边用掉了）。线索二叉树的思路是废物利用：把这些空指针改为指向前驱或后继的"线索"，让遍历不再需要栈或递归，直接沿线索走就行。

408 考研中，线索二叉树是二叉树章节的独立考点：n+1 个空指针的计算、ltag/rtag 的含义、中序线索化的代码实现、找前驱后继的方法——每年几乎必考其中至少一项。

核心思想

线索二叉树在普通二叉链表的基础上，为每个结点增加两个标志位 ltag 和 rtag：

标志	值为 0	值为 1
ltag	lchild 指向左孩子	lchild 指向前驱（线索）
rtag	rchild 指向右孩子	rchild 指向后继（线索）

结点结构定义：

typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 0: 孩子  1: 线索
} ThreadNode, *ThreadTree;

规则总结：

• 若结点有左孩子，则 lchild 指向左孩子，ltag = 0；否则 lchild 指向其前驱，ltag = 1
• 若结点有右孩子，则 rchild 指向右孩子，rtag = 0；否则 rchild 指向其后继，rtag = 1

标志位 ltag / rtag 含义图解

判断规则：

• 标志位为 0 → 指针指向孩子结点（正常的树结构指针）
• 标志位为 1 → 指针指向前驱或后继（线索，利用了空指针域）

交互可视化

通过下方的交互动画，你可以逐步观察线索二叉树的执行过程：

加载可视化中...

操作详解

线索化的目的

线索化的本质是：对二叉树进行一次遍历，在遍历过程中检查每个结点的左右指针域是否为空，若为空则将其改为指向前驱或后继的线索。

线索化后的好处：

• 无需栈或递归即可遍历二叉树，空间复杂度降为 O(1)
• 可以直接找到任意结点在遍历序列中的前驱和后继
• 充分利用了 n+1 个空指针域，不浪费存储空间

中序线索化过程

中序线索化需要一个全局指针 pre，始终指向当前访问结点的前一个结点（即中序遍历中刚访问过的结点）。

关键步骤：

1. 递归线索化左子树
2. 处理当前结点：
   • 若当前结点的 lchild == NULL，令 lchild = pre，ltag = 1（前驱线索）
   • 若 pre 不为空且 pre->rchild == NULL，令 pre->rchild = 当前结点，pre->rtag = 1（后继线索）
3. 更新 pre = 当前结点
4. 递归线索化右子树

ThreadNode *pre = NULL;  // 全局指针，指向刚访问过的结点

void InThread(ThreadTree T) {
    if (T == NULL) return;
    InThread(T->lchild);          // 递归线索化左子树
    // 处理当前结点
    if (T->lchild == NULL) {      // 左孩子为空，建立前驱线索
        T->lchild = pre;
        T->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {  // 前驱的右孩子为空，建立后继线索
        pre->rchild = T;
        pre->rtag = 1;
    }
    pre = T;                      // 更新 pre
    InThread(T->rchild);          // 递归线索化右子树
}

// 中序线索化入口
void CreateInThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {
        InThread(T);
        // 处理最后一个结点的后继
        pre->rchild = NULL;
        pre->rtag = 1;
    }
}

找前驱与后继

在中序线索二叉树中找结点 p 的后继：

• 若 p->rtag == 1：后继就是 p->rchild（直接通过线索找到）
• 若 p->rtag == 0：p 有右子树，后继是其右子树中最左下的结点

// 找以 p 为根的子树中，最左下的结点
ThreadNode* Firstnode(ThreadNode *p) {
    while (p->ltag == 0)
        p = p->lchild;
    return p;
}

// 找中序后继
ThreadNode* Nextnode(ThreadNode *p) {
    if (p->rtag == 0)
        return Firstnode(p->rchild);  // 右子树最左下结点
    else
        return p->rchild;             // 直接返回线索
}

在中序线索二叉树中找结点 p 的前驱：

• 若 p->ltag == 1：前驱就是 p->lchild（直接通过线索找到）
• 若 p->ltag == 0：p 有左子树，前驱是其左子树中最右下的结点

// 找以 p 为根的子树中，最右下的结点
ThreadNode* Lastnode(ThreadNode *p) {
    while (p->rtag == 0)
        p = p->rchild;
    return p;
}

// 找中序前驱
ThreadNode* Prenode(ThreadNode *p) {
    if (p->ltag == 0)
        return Lastnode(p->lchild);   // 左子树最右下结点
    else
        return p->lchild;             // 直接返回线索
}

利用上述函数，可以实现不用栈的中序遍历：

void InOrder(ThreadTree T) {
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
        visit(p);
}

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

中序线索化最常考，但 408 也考过前序和后序线索化的特殊性质（2010、2013 真题）。三种线索化的建立方法完全相同（只是遍历顺序不同），区别在于找前驱和后继的难度不同。

前序线索二叉树

前序遍历顺序：根 → 左 → 右

找前序后继——简单，不需要线索就能找到：

• 若结点有左孩子 → 后继就是左孩子
• 若结点无左孩子但有右孩子 → 后继就是右孩子
• 若结点是叶子 → rtag=1，rchild 直接指向后继（线索）

找前序前驱——困难，线索二叉树中无法高效完成：

• 若 ltag=1，lchild 直接指向前驱（线索）
• 若 ltag=0（有左孩子），前驱不在其子树中（前序先访问根，再访问子树），必须回溯到双亲结点才能确定前驱
• 普通二叉链表没有双亲指针，无法回溯 → 需要三叉链表（增加 parent 指针）或从头遍历

前序线索化代码需要特别注意转圈问题：递归 PreThread(T->lchild) 前，必须检查 T->ltag == 0，否则 lchild 可能已被修改为前驱线索，会导致递归进入前驱而非左子树，形成死循环。

void PreThread(ThreadTree T) {
    if (T == NULL) return;
    if (T->lchild == NULL) {      // 建立前驱线索
        T->lchild = pre;
        T->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = T;
        pre->rtag = 1;
    }
    pre = T;
    if (T->ltag == 0)             // 必须判断！避免沿线索转圈
        PreThread(T->lchild);
    PreThread(T->rchild);
}

后序线索二叉树

后序遍历顺序：左 → 右 → 根

找后序前驱——简单，不需要线索就能找到：

• 若结点有右孩子 → 前驱就是右孩子
• 若结点无右孩子但有左孩子 → 前驱就是左孩子
• 若结点是叶子 → ltag=1，lchild 直接指向前驱（线索）

找后序后继——困难，需要分三种情况：

1. 若结点是整棵树的根 → 后继为空（后序遍历中根最后访问）
2. 若结点是其双亲的右孩子，或是其双亲的左孩子且双亲无右子树 → 后继是其双亲
3. 若结点是其双亲的左孩子且双亲有右子树 → 后继是双亲右子树中按后序遍历第一个访问的结点（右子树最左下的叶子）

情况 2 和 3 都需要知道双亲结点的信息。普通二叉链表做不到 → 需要三叉链表。

三种线索化对比

	找后继	找前驱	难点
中序线索	简单（rtag=1 直接找；rtag=0 找右子树最左下）	简单（ltag=1 直接找；ltag=0 找左子树最右下）	无
前序线索	简单（有左孩子→左孩子；否则→右孩子/线索）	困难（有左孩子时需要双亲信息）	找前驱需三叉链表
后序线索	困难（需要双亲信息，分3种情况）	简单（有右孩子→右孩子；否则→左孩子/线索）	找后继需三叉链表

记忆口诀：中序两头都好找；前序好找后继、难找前驱；后序好找前驱、难找后继。规律是——遍历顺序中"根"的位置决定了难点：前序根在最前（前驱方向回溯难），后序根在最后（后继方向回溯难）。

复杂度分析

操作	时间复杂度	说明
中序线索化	O(n)	对每个结点访问一次
找后继（有线索）	O(1)	直接通过线索指针
找后继（无线索）	O(h)	需走到右子树最左下，h 为树高
找前驱（有线索）	O(1)	直接通过线索指针
找前驱（无线索）	O(h)	需走到左子树最右下，h 为树高
中序遍历（线索树）	O(n)	不需要栈，空间 O(1)

空间复杂度：线索化过程需要 O(n) 递归栈空间；线索化完成后，遍历只需 O(1) 辅助空间。

考研高频考点

• ⭐ n 个结点的二叉链表中有 n+1 个空指针域（选择题/填空题高频）
• ⭐ ltag/rtag 标志位的含义及结点结构（概念题必考）
• ⭐ 中序线索化的过程与算法实现（代码题/算法题）
• ⭐ 在中序线索二叉树中找前驱和后继的方法（选择题/简答题高频）
• ⭐ 线索二叉树遍历不需要栈的原因（概念题）
• ⭐ 前序线索二叉树找前驱需要三叉链表（选择题，2010 考过）
• ⭐ 后序线索二叉树找后继需要三叉链表（选择题，2013 考过）
• ⭐ 三种线索化中，只有中序线索能同时高效找前驱和后继（对比题）
• 线索二叉树 vs 普通二叉树的空间利用率对比

易错：线索二叉树中需要用 ltag/rtag 标志位区分指针是指向孩子还是指向前驱/后继：tag=0 表示指向孩子，tag=1 表示是线索。忘记设置 tag 是代码实现中最常见的错误。

易错：中序线索二叉树的第一个结点（中序序列第一个）没有前驱线索，最后一个结点没有后继线索。如果要方便遍历，通常会增加一个头结点，让第一个结点的 lchild 指向头结点，最后一个结点的 rchild 也指向头结点。

易错：前序线索化时必须先判断 ltag 再递归左子树（if (T->ltag == 0) PreThread(T->lchild)），否则 lchild 可能已被修改为前驱线索，递归会沿线索走而不是走左子树，导致死循环。中序和后序线索化没有这个问题（递归在线索建立之前/之后）。

易错：408 常考"二叉树在线索化后，仍不能有效求解的问题"——答案是后序线索二叉树中求后序后继。因为后序中根最后访问，某结点的后继可能是其祖先，而二叉链表中没有双亲指针，只能借助三叉链表。

相关知识

• 中序遍历 —— 线索化最常基于中序遍历
• 前序遍历 —— 前序线索二叉树找前驱需要借助栈或三叉链表
• 二叉排序树 —— BST + 中序线索 = 有序链表

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 由遍历序列构造二叉树
• 线索二叉树
• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 红黑树
• 哈夫曼树
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习

相关真题（3题）

2014Q4选择题2分

可视化详解

线索二叉树：中序遍历序列中结点的前驱后继线索指向

线索二叉树

2013Q5选择题2分

可视化详解

后序线索二叉树：线索指向的分析

线索二叉树

2010Q3选择题2分

可视化详解

后序线索二叉树：线索结构的特征分析

线索二叉树