当前位置：首页 > news >正文

线索二叉树

news 2026/3/26 19:00:11

线索二叉树（Threaded Binary Tree） 是对普通二叉树的一种优化。在普通的二叉树链式存储中，会有大量的空指针，线索二叉树正是利用这些空指针来存放指向节点在某种遍历序列下的“前驱”和“后继”的记录。

1. 为什么需要线索二叉树？

在含有 $n$ 个结点的二叉链表中，共有 $2n$ 个指针域（每个结点有左右两个）。而有效指针（连接子结点的）只有 $n-1$ 条。因此，会有 $n+1$ 个空指针域 被浪费了。

线索化（Threading） 的目的就是：

利用空指针： 让原本指向 NULL 的左指针指向其前驱（Predecessor），右指针指向其后继（Successor）。
提高遍历效率： 可以在不使用递归和栈的情况下，像遍历链表一样线性地遍历二叉树。

2. 线索二叉树的结构

为了区分一个节点的 left 和 right 指针指向的是“孩子”还是“线索”，我们需要在节点结构中增加两个标志位（Tags）：

ltag:
- 0: left 指向左孩子。
- 1: left 指向前驱。
rtag:
- 0: right 指向右孩子。
- 1: right 指向后继。

C++ 节点定义

C++

struct ThreadNode {int data;ThreadNode *left, *right;int ltag, rtag; // 0: 孩子, 1: 线索ThreadNode(int val) : data(val), left(nullptr), right(nullptr), ltag(0), rtag(0) {}
};

3. 中序线索二叉树 (In-order Threaded Tree)

最常见的是中序线索二叉树。它的线索化过程是按照中序遍历（左-根-右）的顺序进行的。

[Image comparing a normal binary tree and its in-order threaded version with dotted lines for threads]

核心算法：中序线索化

线索化的本质是在遍历的过程中，用一个全局变量 pre 记录当前节点的前一个节点。

C++

ThreadNode* pre = nullptr; // 全局变量，记录刚刚访问过的节点void createInThread(ThreadNode* curr) {if (curr == nullptr) return;// 1. 递归线索化左子树createInThread(curr->left);// 2. 处理当前节点// 如果左孩子为空，建立前驱线索if (curr->left == nullptr) {curr->left = pre;curr->ltag = 1;}// 如果 pre 的右孩子为空，建立后继线索if (pre != nullptr && pre->right == nullptr) {pre->right = curr;pre->rtag = 1;}pre = curr; // 更新 pre// 3. 递归线索化右子树createInThread(curr->right);
}

4. 遍历线索二叉树

线索化完成后，遍历二叉树就不再需要递归或栈了，效率接近线性链表。

寻找中序后继的逻辑：

如果 rtag == 1，则 right 直接就是后继。
如果 rtag == 0，说明有右子树，后继则是右子树中最左下角的节点。

C++

// 寻找以 p 为根的子树中，中序遍历的第一个节点
ThreadNode* firstNode(ThreadNode* p) {while (p->ltag == 0) p = p->left;return p;
}// 寻找节点 p 的中序后继
ThreadNode* nextNode(ThreadNode* p) {if (p->rtag == 0) return firstNode(p->right);else return p->right; // rtag == 1，直接返回后继线索
}// 中序遍历整个线索树
void inorderTraversal(ThreadNode* root) {for (ThreadNode* p = firstNode(root); p != nullptr; p = nextNode(p)) {cout << p->data << " ";}
}