16. 线索二叉树：让遍历不再依赖递归
说到二叉树遍历，你肯定写过递归或非递归的代码。递归简单，但函数调用栈有开销；非递归用栈模拟，内存占用也不小。有没有一种办法，能像链表一样直接“走”完一棵树？
嗯，线索二叉树就是干这个的。我个人觉得，它是“空间换时间”的经典案例——利用那些空指针，把遍历路径提前存好。
16.1 线索二叉树的原理
先看一个普通二叉树。每个节点有两个指针域（left 和 right），但叶子节点和部分内部节点的指针是空的。统计一下：n 个节点的二叉树，总共有 2n 个指针，实际用了 n-1 个（根节点没有父指针），剩下 n+1 个是空的。
这些空指针，说白了就是浪费。线索二叉树的想法很简单：
- 如果左指针为空，就让它指向前驱节点（遍历顺序中的前一个）
- 如果右指针为空，就让它指向后继节点（遍历顺序中的下一个）
这样，遍历时就不需要递归或栈了，直接沿着线索走就行。
但问题来了：我怎么知道一个指针是原来的孩子指针，还是线索？
解决办法是加两个标志位：
| 标志位 | 含义 |
|---|---|
| ltag = 0 | left 指向左孩子 |
| ltag = 1 | left 指向前驱（线索） |
| rtag = 0 | right 指向右孩子 |
| rtag = 1 | right 指向后继（线索） |
节点结构就变成了：
typedef struct ThreadNode {
int data;
struct ThreadNode *left, *right;
int ltag, rtag; // 0:孩子, 1:线索
} ThreadNode, *ThreadTree;你想想看，这个结构只比普通二叉树多了两个 int，但换来了 O(1) 空间复杂度的遍历。值不值？我在项目中处理过百万节点的树，递归遍历直接栈溢出，换成线索二叉树后，问题就解决了。
16.2 线索化：如何把普通树变成线索树
线索化本质上是一次遍历，在遍历过程中把空指针改成线索。我习惯用中序遍历来做，因为中序线索树用得最多。
核心思路：
- 用一个全局指针 pre 记录上一个访问的节点
- 访问当前节点 p 时，检查 p->left 是否为空，为空则让它指向 pre
- 检查 pre->right 是否为空，为空则让它指向 p
- 更新 pre = p
看代码：
void InThread(ThreadTree &p, ThreadTree &pre) {
if (p == NULL) return;
InThread(p->left, pre); // 线索化左子树
if (p->left == NULL) { // 左指针为空，指向前驱
p->left = pre;
p->ltag = 1;
}
if (pre != NULL && pre->right == NULL) { // 前驱的右指针为空，指向当前
pre->right = p;
pre->rtag = 1;
}
pre = p; // 更新前驱
InThread(p->right, pre); // 线索化右子树
}
void CreateInThread(ThreadTree T) {
ThreadTree pre = NULL;
if (T != NULL) {
InThread(T, pre);
// 处理最后一个节点
pre->right = NULL;
pre->rtag = 1;
}
}注意最后一步：遍历结束后，pre 指向最后一个节点，它的右指针要置为 NULL 并标记为线索。我曾经漏掉这一步，结果遍历时一直死循环——嗯，血的教训。
16.3 遍历线索二叉树
线索化之后，遍历就变得非常直接了。不需要栈，不需要递归，只需要一个循环。
中序遍历线索二叉树的步骤：
- 找到最左边的节点（一直往左走，直到 ltag == 1）
- 访问该节点
- 如果右指针是线索（rtag == 1），直接跳到后继
- 如果右指针是孩子（rtag == 0），则转到右子树，再找最左边节点
- 重复直到回到 NULL
代码实现：
void InOrderTraverse(ThreadTree T) {
ThreadTree p = T;
while (p != NULL) {
// 找到最左边的节点
while (p->ltag == 0) {
p = p->left;
}
printf("%d ", p->data); // 访问节点
// 沿着线索走
while (p->rtag == 1 && p->right != NULL) {
p = p->right;
printf("%d ", p->data);
}
p = p->right; // 转到右子树
}
}这个遍历的时间复杂度是 O(n)，空间复杂度是 O(1)。你想想看，同样的功能，递归版本需要 O(n) 的栈空间，非递归版本也需要 O(h) 的栈空间（h 是树高）。线索二叉树在空间上完胜。
16.4 知识体系图
下面这张图总结了线索二叉树的核心逻辑：
16.5 避坑指南
- 线索化时忘记处理最后一个节点的右指针，导致遍历越界
- 在已经线索化的树上再次线索化，造成指针混乱——线索化只能做一次
- 插入/删除节点后没有更新线索，导致遍历结果错误。线索二叉树不适合频繁修改的场景
说实话，线索二叉树在实际工程中用得不算特别多。但如果你遇到以下情况，它绝对是利器：
- 内存非常有限（比如嵌入式系统）
- 需要频繁遍历，但很少修改树结构
- 遍历时不能使用递归（栈深度受限）
我个人建议：把中序线索二叉树作为首选掌握，前序和后序线索化用得少，但原理相通。你只要理解了“用空指针存遍历顺序”这个核心思想，其他变种一看就懂。
公众号:蓝海资料掘金营，微信deep3321