线索二叉树

概念

线索二叉树（threaded binary tree）是在二叉链表的基础上，把原本为空的 n + 1 个指针域利用起来，令其指向该结点在某种遍历序列下的前驱或后继，这些指针称为线索（thread）。

为了区分"这个指针到底指向孩子还是指向线索"，每个结点必须增设两个标志位：

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

一句话理解：线索二叉树 = 普通二叉树 + 把空闲指针改成"前一个是谁 / 后一个是谁"的快捷通道。

它的价值：遍历时不必用栈也不必递归，顺着线索就能走完整个序列。

原理

为什么恰好有 n + 1 个空指针

n 个结点的二叉链表有 2n 个指针域，其中指向孩子的有效指针恰为 n − 1 个（每条边一个），故空指针 = 2n − (n − 1) = n + 1。这些空位是纯粹的浪费，线索化就是回收它们。

线索化的过程

线索化 = 按某种遍历顺序走一遍，遇到空指针就把它改成指向当前访问结点的前驱/后继。

以中序线索化为例，需要两个变量：

• pre：指向"刚刚访问过的那个结点"（即当前结点的前驱）
• 当前结点 p

规则（中序递归过程中对 p 的处理）：

1. 若 p->lchild == NULL：令 p->lchild = pre，p->ltag = 1。
2. 若 pre != NULL 且 pre->rchild == NULL：令 pre->rchild = p，pre->rtag = 1。
3. 令 pre = p，继续递归。

注意第 2 步处理的是 pre 而非 p——因为 p 的后继要等到下一次访问才知道，得"回头补"。

头结点：让首尾也有线索

为方便遍历，通常增设一个头结点（哨兵），令：

• 头结点的 lchild 指向根，ltag = 0
• 头结点的 rchild 指向遍历序列的最后一个结点，rtag = 1
• 序列第一个结点的 lchild 指向头结点
• 序列最后一个结点的 rchild 指向头结点

这样整棵线索树构成一个双向链表环，遍历时"从第一个结点走到头结点"即终止。

三种线索树找前驱/后继的规律（最常考）

线索树	找后继	找前驱
中序	若 rtag=1，右指针即后继；否则为右子树的最左下结点	若 ltag=1，左指针即前驱；否则为左子树的最右下结点
先序	若 rtag=1，右指针即后继；否则：有左孩子则取左孩子，否则取右孩子	无法直接找到（需双亲指针或从头遍历）
后序	无法直接找到（需双亲指针）	若 ltag=1，左指针即前驱；否则：有右孩子则取右孩子，否则取左孩子

原因很直觉：先序是"根左右"，根的后继就在自己的子树里，但根的前驱在上一层的某处；后序是"左右根"，前驱在自己的子树里，后继要到上一层去找。判断能不能直接找，就看目标方向是不是在自己子树内。

示例

例：把一棵树中序线索化

二叉树如图所示（中序序列为 D B E A C F），画出其中序线索。

            A
          /   \
         B     C
        / \     \
       D   E     F

完整推导过程：

第一步，写出中序序列：D B E A C F。

第二步，逐个考察每个结点的空指针：

结点	空指针	中序前驱	中序后继	线索化结果
D	左、右	无（序列首）	B	lchild → 头结点，rchild → B，ltag=rtag=1
E	左、右	B	A	lchild → B，rchild → A，ltag=rtag=1
B	无（左右都有孩子）	D	E	保持指向 D、E，ltag=rtag=0
C	左	E	F	lchild → E，ltag=1；右指针指向 F，rtag=0
F	左、右	C	无（序列尾）	lchild → C，rchild → 头结点，ltag=rtag=1
A	无	E	C	保持指向 B、C，ltag=rtag=0

第三步，核对数量：空指针共 n + 1 = 6 + 1 = 7 个，上表中 D(2) + E(2) + C(1) + F(2) = 7，吻合。

结论：线索化后从 D 出发沿右线索走：D → B（B 的右指针是孩子，需下到其右子树 E）→ E → A → C → F，正好得到完整中序序列。

C 语言：中序线索二叉树的构造与遍历

#include <stdio.h>
#include <stdlib.h>

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

ThreadNode *pre = NULL;             /* 全局变量：指向刚访问过的结点 */

void inThread(ThreadTree p) {
    if (!p) return;
    inThread(p->lchild);            /* 1. 线索化左子树 */

    if (!p->lchild) {               /* 2. 左空指针 → 前驱线索 */
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre && !pre->rchild) {      /* 3. 前驱的右空指针 → 后继线索（回头补） */
        pre->rchild = p;
        pre->rtag = 1;
    }
    pre = p;                        /* 4. 更新 pre */

    inThread(p->rchild);            /* 5. 线索化右子树 */
}

void createInThread(ThreadTree t) {
    pre = NULL;
    if (t) {
        inThread(t);
        if (pre->rchild == NULL) pre->rtag = 1;   /* 收尾：最后一个结点无后继 */
    }
}

/* 中序遍历线索树：不用栈、不用递归 */
ThreadNode *firstNode(ThreadNode *p) {
    while (p->ltag == 0) p = p->lchild;     /* 一路向左到底 */
    return p;
}

ThreadNode *nextNode(ThreadNode *p) {
    if (p->rtag == 1) return p->rchild;     /* 右线索直接给出后继 */
    return firstNode(p->rchild);            /* 否则是右子树的最左下结点 */
}

void inOrderTraverse(ThreadTree t) {
    for (ThreadNode *p = firstNode(t); p; p = nextNode(p))
        printf("%c ", p->data);
}

int main(void) {
    /* 手工建树：A(B(D,E), C(,F))，所有指针初始 ltag=rtag=0 表示孩子 */
    ThreadNode *n[6];
    for (int i = 0; i < 6; i++) {
        n[i] = (ThreadNode *)malloc(sizeof(ThreadNode));
        n[i]->ltag = n[i]->rtag = 0;
        n[i]->lchild = n[i]->rchild = NULL;
    }
    char d[6] = {'A','B','C','D','E','F'};
    for (int i = 0; i < 6; i++) n[i]->data = d[i];
    n[0]->lchild = n[1]; n[0]->rchild = n[2];      /* A → B, C */
    n[1]->lchild = n[3]; n[1]->rchild = n[4];      /* B → D, E */
    n[2]->rchild = n[5];                           /* C → (空), F */

    createInThread(n[0]);
    inOrderTraverse(n[0]);   /* D B E A C F */
    printf("\n");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

class TNode:
    def __init__(self, data):
        self.data = data
        self.l = self.r = None
        self.ltag = self.rtag = 0      # 0 孩子 / 1 线索

pre = None

def in_thread(p):
    global pre
    if not p: return
    in_thread(p.l)
    if p.l is None:                    # 左空 → 前驱线索
        p.l, p.ltag = pre, 1
    if pre is not None and pre.r is None:
        pre.r, pre.rtag = p, 1         # 回头给前驱补后继线索
    pre = p
    in_thread(p.r)

def first_node(p):
    while p.ltag == 0 and p.l: p = p.l
    return p

def next_node(p):
    if p.rtag == 1: return p.r
    return first_node(p.r) if p.r else None

# A(B(D,E), C(,F))
A, B, C, D, E, F = (TNode(x) for x in "ABCDEF")
A.l, A.r = B, C
B.l, B.r = D, E
C.r = F

in_thread(A)
out, p = [], first_node(A)
while p:
    out.append(p.data)
    p = next_node(p)
print("".join(out))            # DBEACF

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背结论

• n 个结点的二叉链表有 n + 1 个空指针域，全部被线索化利用。
• 线索化的实质：遍历一次，把空指针改成前驱/后继线索；pre 是"上一个访问过的结点"。
• 中序线索树可以不用栈和递归完成遍历，空间复杂度 O(1)。

2. 三种线索树的查找能力（易混，年年有题）

线索树	找后继	找前驱
中序	可以	可以
先序	可以	不可以
后序	不可以	可以

记忆口诀：先序能找后继、后序能找前驱，中序两头都能找。

3. 易错点

• 线索化时判定"空指针"要看原始结构，不能在线索化后再判断（否则会误把线索当孩子递归下去，造成死循环）。代码里靠 ltag/rtag 区分正是为此。
• 线索树的 lchild 到底是孩子还是前驱，完全由 ltag 决定，画图题必须标出标志位。
• 线索二叉树不改变结点的逻辑关系，只是增加了访问捷径；插入/删除结点会导致线索失效，需要重新线索化。
• "线索二叉树是物理结构"——它是存储结构（链式存储的一种改进），逻辑结构仍是树形。
• 中序线索化中给 pre 补右线索这一步容易漏写，漏写会导致序列断裂。

小结

• 线索化 = 回收 n + 1 个空指针，把它们变成"前驱/后继"的快捷通道。
• 每个结点必须带 ltag/rtag 两个标志位，否则无法区分孩子与线索。
• 中序线索树最实用：既能找前驱又能找后继，遍历彻底告别栈与递归。
• 先序只能找后继、后序只能找前驱——判断依据是"目标在不在自己的子树里"。

下一篇：二叉排序树