线索二叉树

为什么需要线索二叉树

对于一棵有 n 个结点的二叉树，采用二叉链表存储时共有 2n 个指针域，其中只有 n-1 个用于指向孩子结点，剩余 n+1 个指针域为空（NULL）。这些空指针白白浪费了存储空间。

另一方面，二叉树的遍历本质上是将树中结点排成一个线性序列（如中序序列），但普通二叉链表无法直接找到某个结点在该序列中的前驱和后继，每次都需要重新遍历，效率低下。

线索二叉树的思路：利用这些空指针域，存放结点在某种遍历序列中的前驱和后继信息，从而加速遍历过程。

核心思想

线索二叉树在普通二叉链表的基础上，为每个结点增加两个标志位 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，始终指向当前访问结点的前一个结点（即中序遍历中刚访问过的结点）。

关键步骤：

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

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);
}

复杂度分析

操作	时间复杂度	说明
中序线索化	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 标志位的含义及结点结构（概念题必考）
⭐ 中序线索化的过程与算法实现（代码题/算法题）
⭐ 在中序线索二叉树中找前驱和后继的方法（选择题/简答题高频）
⭐ 线索二叉树遍历不需要栈的原因（概念题）
前序/后序线索二叉树找前驱后继的局限性（前序找前驱、后序找后继可能需要借助栈或三叉链表）
线索二叉树 vs 普通二叉树的空间利用率对比

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

线索二叉树 ​

为什么需要线索二叉树 ​

核心思想 ​

标志位 ltag / rtag 含义图解 ​

交互可视化 ​

操作详解 ​

线索化的目的 ​

中序线索化过程 ​

找前驱与后继 ​

复杂度分析 ​

考研高频考点 ​

相关文章