线索二叉树

2026 大纲 四（二）4 线索二叉树的基本概念和构造，本篇独立承载这一整条。

动机：那 $n+1$ 个空指针白占着

遍历完一棵二叉树，每个结点都有确定的前驱和后继。可惜这些信息只在遍历的动态过程中存在，遍历一结束就丢了；下次想知道某个结点的后继是谁，还得重新遍历一遍。

而二叉链表里恰好有一批指针域既不存数据也不指向任何东西。含 $n$ 个结点的二叉链表共 $2n$ 个指针域，其中指向孩子的只有 $n-1$ 个（与树中的 $n-1$ 条边一一对应），所以

$$\text{空指针数}=2n-(n-1)=n+1$$

两件事凑在一起，办法就出来了：

用那 $n+1$ 个空指针域，把遍历得到的前驱 / 后继信息保存下来。

指向前驱或后继的指针叫线索（thread），加了线索的二叉树叫线索二叉树。

要说清楚线索化真正省的是什么：不是结点空间（那些空指针本来就占着），而是遍历时的那个栈——普通二叉链表遍历要 $O(h)$ 的栈，线索树上遍历只要一个指针、$O(1)$；查某个结点的前驱后继，从"重新遍历一遍 $O(n)$"降到 $O(1)$ 或 $O(h)$。

中序线索化会用掉 $n+1$ 个空指针中的 $n-1$ 个——中序序列的第一个结点没有前驱、最后一个结点没有后继，这两个空指针留着。所以线索化后恰好剩 2 个空指针（带头结点的做法可以降到 0，见下文）。

结点结构：多两位标志

直接把空的 lchild 改成指向前驱会立刻出问题：拿到一个非空的 lchild，分不清它指的是左孩子还是前驱。所以每个结点要加两个标志位：

标志	值为 0	值为 1
ltag	lchild 指向左孩子（该结点有左子树）	lchild 指向前驱（线索，该结点无左子树）
rtag	rchild 指向右孩子（该结点有右子树）	rchild 指向后继（线索，该结点无右子树）

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

两位标志理论上只需 2 bit，写成 int 实际会占 8 字节，但这仍然远小于"给每个结点再加两个指针域存前驱后继"的做法——那要 $2n$ 个指针，且原来的 $n+1$ 个空指针照样浪费。线索化的性价比正来自"复用已有的空指针 $+$ 只加两位标志"。

上图左侧是一棵中序线索二叉树（虚线箭头即线索），右侧是它在内存中的线索链表。结点格式为 leftChild | ltag | data | rtag | rightChild。这棵树的中序序列是 B D A E C：结点 B 是序列第一个，没有前驱，所以它的 lchild 为空且 ltag = 1；结点 C 是序列最后一个，rchild 为空且 rtag = 1；结点 D 两侧都是线索（1 D 1），分别指向前驱 B 和后继 A。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 5.28 中序线索二叉树及其二叉链表表示，p211

先看一眼

加载可视化中...

中序线索化：靠一个 pre 指针延迟一拍

线索化就是"在遍历的过程中修改空指针"。建立线索必须同时知道当前结点 $T$ 和它的前驱，因此需要一个贯穿递归的指针 pre，始终指向中序序列中刚访问过的结点。对当前结点做两件事：

• 回头看：若 T->lchild == NULL，$T$ 的前驱正是 pre，建立前驱线索；
• 回头补：若 pre != NULL 且 pre->rchild == NULL，pre 的后继正是 $T$，建立后继线索。

后继线索为什么要"回头补"：处理 $T$ 的时候还不知道它的后继是谁。但轮到 $T$ 的后继时，pre 恰好就是 $T$——每个结点的后继线索由它的后继替它补上。这个"延迟一拍"的写法是线索化代码的关键。

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

void InThread(ThreadTree T) {
    if (T == NULL) return;
    InThread(T->lchild);                  // ① 递归线索化左子树
    if (T->lchild == NULL) {              // ② 左孩子为空 → 建立指向前驱的线索
        T->lchild = pre;
        T->ltag = 1;
    } else {
        T->ltag = 0;
    }
    if (pre != NULL) {
        if (pre->rchild == NULL) {        // 前驱的右孩子为空 → 替它补上后继线索
            pre->rchild = T;
            pre->rtag = 1;
        } else {
            pre->rtag = 0;
        }
    }
    pre = T;                              // ③ 当前结点成为下一个结点的前驱
    InThread(T->rchild);                  // ④ 递归线索化右子树
}

void CreateInThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {
        InThread(T);
        pre->rchild = NULL;               // 最后一个结点没有后继
        pre->rtag = 1;
    }
}

三处值得想清楚的地方：

1. 中序线索化不会"沿线索转圈"。 递归 InThread(T->lchild) 发生在修改 T->lchild 之前（第 ① 步在第 ② 步之前），所以递归进去的一定是真正的左子树。同理，执行 InThread(T->rchild) 时 T->rchild 还没被任何人改成线索——改它的是 $T$ 的后继，而那件事发生在这次递归调用返回之后。次序保护了它，前序线索化就没有这层保护。

2. 判断的是 pre->rchild == NULL 而不是 pre->rtag。 pre 的右指针在此刻还没被任何人动过；每个结点在整个线索化过程中只当一次 pre，也就只有这一次机会被补上后继线索。

3. 最后那两行不能漏。 递归结束后 pre 指向中序序列的最后一个结点，它没有后继。把 rchild 置空、rtag 置 1，表示"这里是线索，但指向空"，遍历循环走到它时会自然得到 NULL 而终止。漏掉这两行，遍历会在最后一个结点处读到未初始化的指针。

中序线索化逐步走一遍（想手动模拟时展开）

中序序列 D B E A C F：

        A
       / \
      B   C
     / \   \
    D   E   F

处理次序（中序）	T	T->lchild 是否为空	建立的前驱线索	pre 的 rchild 是否为空	建立的后继线索	处理后 pre
1	D	是	D.lchild → NULL（pre 为空，D 无前驱）	pre 为 NULL，跳过	—	D
2	B	否（左孩子 D）	—	是（D 的 rchild 为空）	D.rchild → B	B
3	E	是	E.lchild → B	否（B 有右孩子 E）	—	E
4	A	否（左孩子 B）	—	是（E 的 rchild 为空）	E.rchild → A	A
5	C	是	C.lchild → A	否（A 有右孩子 C）	—	C
6	F	是	F.lchild → C	否（C 有右孩子 F）	—	F
收尾	—	—	—	—	F.rchild → NULL，rtag = 1	—

剩余空指针恰为 2 个（D 的左、F 的右），与前面的推导一致。

在中序线索树上找前驱与后继

rtag == 1 时 p->rchild 就是后继（$O(1)$）；rtag == 0 时 $p$ 有右子树，而遍历一棵子树时第一个被访问的是它最左下的结点，所以后继 $=$ 右子树中最左下的结点。找前驱完全对称：ltag == 1 取线索，否则取左子树中最右下的结点。

// 以 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->ltag == 0 而不是 p->lchild != NULL。 线索化之后，lchild 非空并不代表有左孩子——它可能是一条指向前驱的线索。写成判空会顺着线索往回跑。这是本篇最典型的实现错误。

有了这两个函数，中序遍历退化成一个 for 循环，时间 $O(n)$、空间 $O(1)$（只用一个指针，没有栈也没有递归）：

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

时间为什么是 $O(n)$ 而不是 $O(nh)$：单次 Nextnode 最坏 $O(h)$，但整趟遍历的总代价仍是 $\mathrm{\Theta }(n)$——用摊还的眼光看，Firstnode 里"一路向左"走过的每条边、以及每次 Nextnode 走过的边，在整趟遍历中每条边最多被走两次（一次向下、一次通过线索跳回），总边数 $n-1$。把它算成 $O(nh)$ 是把单次最坏乘以次数，那是明显的高估。

反向遍历也成立：从最右下的结点出发反复调用 Prenode（对称写法：ltag == 0 时取左子树最右下，否则取线索），可以 $O(n)$ 时间、$O(1)$ 空间地逆中序遍历——这是普通二叉链表做不到的。

带头结点的线索链表：教材的规范做法（题目给了头结点时展开）

上面的版本里，中序第一个结点的 lchild 和最后一个结点的 rchild 都是空的。教材的规范做法是增设一个头结点 Thrt，把这两头接起来：Thrt->lchild 指向根（ltag = 0），Thrt->rchild 指向中序最后一个结点（rtag = 1）；中序第一个结点的 lchild 与最后一个结点的 rchild 都指向 Thrt。

void InOrderThreading(ThreadTree *Thrt, ThreadTree T) {
    *Thrt = (ThreadNode *)malloc(sizeof(ThreadNode));
    (*Thrt)->ltag = 0;                  // 头结点的左指针指向根，是"孩子"不是线索
    (*Thrt)->rtag = 1;
    (*Thrt)->rchild = *Thrt;
    if (T == NULL) {
        (*Thrt)->lchild = *Thrt;        // 空树：左指针也指向自己
    } else {
        (*Thrt)->lchild = T;
        pre = *Thrt;                    // pre 初值为头结点，于是首结点的前驱线索指向头结点
        InThread(T);
        pre->rchild = *Thrt;            // 尾结点的后继线索指向头结点
        pre->rtag = 1;
        (*Thrt)->rchild = pre;
    }
}

收益：整个结构变成一个循环双向链表——顺着后继遍历全表、顺着前驱逆序遍历全表；空指针数变为 0；遍历的终止条件统一成"回到头结点"，不必判 NULL。

前序与后序：根在哪一头，哪一头就难找

中序两头都好找，前序和后序各难一头。这条规律不用背，能推——看"根"在遍历序列中的位置：

• 前序（根在最前）：根排在整棵子树的所有结点之前，所以从根往后走一步一定还在子树内部（看得见），往前走一步必然跳出子树、落到祖先方向（看不见）→ 好找后继、难找前驱；
• 后序（根在最后）：完全镜像 → 好找前驱、难找后继；
• 中序（根在中间）：往前一步落在左子树里、往后一步落在右子树里，两侧都在自己的子树内部 → 两头都好找。

	找后继	找前驱
中序线索	简单：rtag=1 直接取；rtag=0 取右子树最左下	简单：ltag=1 直接取；ltag=0 取左子树最右下
前序线索	简单：有左孩子取左孩子，否则取右孩子 / 线索	困难：有左孩子时需要双亲信息
后序线索	困难：需要双亲信息，分四种情形	简单：有右孩子取右孩子，否则取左孩子 / 线索

后序线索树上找后继的四种情形（rtag == 1 时直接取线索，否则）：

情形	条件	后继
1	$p$ 是整棵树的根	后继为空（后序中根最后访问）
2	$p$ 是双亲的右孩子	后继是双亲
3	$p$ 是双亲的左孩子，且没有右兄弟	后继是双亲
4	$p$ 是双亲的左孩子，且有右兄弟	后继是双亲的右子树按后序遍历的第一个结点

情形 2 值得单独记成一句口诀：后序线索树中，右孩子的后继恒为双亲。 理由就是后序"左右根"的固定节奏——访问完一个右孩子，下一步必然是回到双亲访问"根"。

情形 4 那个"后序第一个结点"怎么找：从双亲的右子树根出发，能往左就往左、不能往左就往右，直到叶结点。

四种情形全部需要双亲信息，而二叉链表里没有双亲指针——这不是"算法难写"，而是信息不足。 教材给的补救办法是："在先序线索化树上找前驱或在后序线索化树上找后继时都比较复杂，此时若需要，可直接建立含 4 个指针的线索链表。"另一条路是改用三叉链表（加 parent 指针），每结点多一个指针但能回溯。

前序线索化的"转圈"问题与代码（要默写前序线索化时展开）

前序线索化的代码顺序是"先处理当前结点、再递归左右子树"，于是递归左子树时 T->lchild 可能已经在上一步被改成了前驱线索。若不加判断就递归下去，会沿着线索跑回祖先，形成死循环。

void PreThread(ThreadTree T) {
    if (T == NULL) return;
    if (T->lchild == NULL) {          // 先处理当前结点：建立前驱线索
        T->lchild = pre;
        T->ltag = 1;
    } else {
        T->ltag = 0;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = T;
        pre->rtag = 1;
    }
    pre = T;
    if (T->ltag == 0)                 // ← 必须判断！ltag=1 说明 lchild 是线索不是孩子
        PreThread(T->lchild);
    if (T->rtag == 0)                 // 右侧同理
        PreThread(T->rchild);
}

中序线索化不需要这两个判断，是因为它的递归左子树发生在修改 lchild 之前，而 rchild 被改成线索由后继完成、那时对右子树的递归早已返回。前序把"处理当前结点"提到了最前面，这层保护就没了。

考点速记

三条会被反复调用的结论：

1. 线索化复用那 $n+1$ 个空指针域，把只在遍历过程中存在的前驱 / 后继固化下来；真正省下的是遍历时的栈，空间 $O(h)\to O(1)$。
2. 判断"有没有孩子"必须看标志位，不能看指针是否为空——判空会顺着线索跑回祖先。
3. 根在哪一头，哪一头就难找：后序线索求后继、前序线索求前驱解决不了，根因是二叉链表里没有双亲信息。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）。三类，全部围绕"某个结点的线索指向谁"：

• 给一棵树，问中序线索化后某结点的左右线索指向谁。 做法固定两步：先把中序序列完整写出来，再在序列里找这个结点的前一个和后一个。注意只有"没有左孩子"时左指针才是线索、"没有右孩子"时右指针才是线索——叶结点两侧都是线索。
• 后序线索树里的后继。 典型问法："X 是后序线索树中的叶结点，且有左兄弟 Y，则 X 的右线索指向什么"——X 有左兄弟说明 X 是双亲的右孩子，套用"右孩子的后继恒为双亲"，答案是双亲。这类题不必画完整棵树，判清 X 是左孩子还是右孩子即可。
• 给四棵画好线索的图，问哪个符合某种线索树的定义。 做法是先写出该次序的遍历序列，再逐条线索比对"这个结点的前驱 / 后继是不是它指的那个"。四个选项通常只在两三条线索上有差别，找到第一条对不上的就能排除。

另外，中序遍历那一节里"中序前驱是左子树最右下、中序后继是右子树最左下"的那条性质，与本篇的 Prenode / Nextnode 是同一件事，真题里两边都考过。

易错：用 lchild != NULL 判断有没有左孩子。 线索化后必须看 ltag。

易错：以为线索化省的是结点空间。 空指针本来就占着，省的是遍历的栈。

易错：把线索化后的剩余空指针数记成 0。 不带头结点剩 2 个（首结点无前驱、尾结点无后继），带头结点才是 0。

易错：把"后序线索树找后继"和"后序线索树找前驱"记反。 后序根在最后，所以前驱好找、后继难找。

教材出处

• 线索二叉树的基本概念、"由于有 $n$ 个结点的二叉链表中必定存在 $n+1$ 个空链域，因此可以充分利用这些空链域来存放结点的前驱和后继信息"，以及 LTag / RTag 的取值规定与结点形式（图 5.15）：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p128（5.5.2 节）
• 二叉线索存储的类型定义、"指向结点前驱和后继的指针叫做线索，加上线索的二叉树称之为线索二叉树，对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化"，以及带头结点的线索链表做法（"好比为二叉树建立了一个双向线索链表"）：印刷 p129
• 中序线索化算法 5.7（InThreading，含 pre 指针的作用说明）与算法 5.8（带头结点的 InOrderThreading）：印刷 p130
• 中序线索树上查找前驱与后继的两种情形（"结点的前驱是遍历左子树时最后访问的一个结点，即左子树中最右下的结点""结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点"），先序线索树上查找前驱后继的规则，以及后序线索树上查找后继的四种情形：印刷 p131
• "在先序线索化树上找前驱或在后序线索化树上找后继时都比较复杂，此时若需要，可直接建立含 4 个指针的线索链表"，遍历中序线索二叉树的算法 5.9，以及"遍历线索二叉树的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，这是因为线索二叉树的遍历不需要使用栈来实现递归操作"：印刷 p132
• 二叉链表中空链域个数为 $n+1$ 的结论及其与线索链表的衔接：印刷 p121

相关知识

树与二叉树基本概念（$n+1$ 个空指针的推导）｜中序遍历（线索化的首选次序，前驱后继的位置性质在那篇）｜前序遍历｜后序遍历｜二叉排序树｜双向链表

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 由遍历序列构造二叉树
• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 红黑树
• 哈夫曼树
• 堆（大根堆/小根堆）
• 并查集
• 树与森林
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习

相关真题（4题）

2024Q32分2014Q42分2013Q52分2010Q32分