1. 引言二叉树中的隐形浪费在学习二叉树的时候我们习惯于关注节点中的数据域和孩子指针却很少思考一个问题那些指向nullptr的空指针到底浪费了多少空间答案是惊人的一棵有 n 个节点的二叉树恰好存在 n1 个空指针域。例如一棵有 10 个节点的二叉树就有 11 个指针是空的。这些空指针不仅白白占用内存更在遍历时成为死胡同——每次递归到底都不得不原路返回。《大话数据结构》6.7 节提出了一个巧妙的思路把这些空指针利用起来存储前驱和后继节点的地址。这样一来二叉树就被改造成了一个线性结构中序遍历不再需要递归或栈只需要沿着指针一路走下去即可。这就是线索二叉树Threaded Binary Tree的核心思想。一句话总结线索二叉树 普通二叉树 利用空指针存储遍历序列中的前驱和后继信息。2. 为什么需要线索二叉树回顾普通二叉树的中序遍历通常有两种实现方式递归实现代码简洁但递归深度受限于树的高度存在栈溢出风险且空间复杂度为 O(h)。非递归实现栈模拟需要显式维护一个栈最坏情况下空间复杂度为 O(n)。这两种方式都有一个共同的问题每次遍历都需要重新走一遍整棵树。如果某个应用场景需要频繁地在中序序列中前后移动比如数据库索引的 B 树叶子节点之间的跳转那么每次都要从头遍历效率极低。线索二叉树的优势在于中序遍历的空间复杂度降为 O(1)只需要几个辅助指针。可以在 O(1) 时间内找到任意节点的前驱或后继无需重新遍历。遍历过程变成了沿着链表走逻辑更清晰也更适合迭代器模式。3. 节点结构改造增加两个标志位线索二叉树的关键在于区分一个指针到底是指向孩子节点还是指向前驱/后继线索。为此每个节点需要增加两个标志位LTag和RTagLTag 0Linklchild指向左孩子LTag 1Threadlchild指向前驱RTag 0Linkrchild指向右孩子RTag 1Threadrchild指向后继改造后的节点结构如下enum PointerTag { Link, Thread }; // Link 0 指向孩子Thread 1 指向线索 struct BiThrNode { int data; // 数据域 BiThrNode *lchild, *rchild; // 左右指针 PointerTag LTag, RTag; // 左右标志位 // 构造函数默认初始化为指向孩子 BiThrNode(int d) : data(d), lchild(nullptr), rchild(nullptr), LTag(Link), RTag(Link) {} };注意构造函数的默认值新节点创建时两个标志位都设为Link表示指针默认指向孩子。线索化过程中才会根据实际情况将标志位改为Thread。4. 中序线索化的核心实现线索化的本质是在中序遍历的过程中顺便把空指针补上。具体来说当访问到某个节点发现它的lchild为空 → 把lchild指向前驱节点即刚刚访问过的节点。当发现前驱节点的rchild为空 → 把前驱的rchild指向当前节点即后继。这里需要一个全局指针pre来始终记录刚刚访问过的节点BiThrNode* pre nullptr; // 全局变量始终指向当前节点的前驱 void InThreading(BiThrNode* p) { if (p nullptr) return; // 第一步递归处理左子树 InThreading(p-lchild); // 第二步线索化处理 if (p-lchild nullptr) { // 左孩子为空 → 指向前驱 p-LTag Thread; p-lchild pre; } if (pre pre-rchild nullptr) { // 前驱的右孩子为空 → 指向后继 pre-RTag Thread; pre-rchild p; } pre p; // 更新前驱 // 第三步递归处理右子树 InThreading(p-rchild); }重点理解这段代码的执行顺序它是在中序遍历的访问节点环节插入线索化逻辑。由于中序遍历的顺序是「左 → 根 → 右」所以当代码执行到线索化处理部分时左子树已经全部处理完毕pre正好指向当前节点在中序序列中的前驱。这就是为什么线索化必须放在递归调用之间。4.1 带头节点的完整线索化《大话数据结构》中推荐使用头节点来简化边界处理。头节点不存储实际数据只是作为遍历的哨兵void InOrderThreading(BiThrNode* head, BiThrNode* T) { // 创建头节点 head new BiThrNode(0); head-LTag Link; head-RTag Thread; head-rchild head; // 右指针先指向自己 if (T nullptr) { // 空树情况 head-lchild head; return; } // 头节点的左孩子指向根节点 head-lchild T; pre head; // 中序线索化整棵树 InThreading(T); // 处理最后一个节点中序序列的最后一个节点 pre-RTag Thread; pre-rchild head; // 最后一个节点的后继指向头节点 // 头节点的右孩子指向最后一个节点 head-rchild pre; }头节点的作用非常巧妙头节点的lchild指向根节点方便从根开始遍历。头节点的rchild指向中序序列的最后一个节点形成一个双向循环结构。最后一个节点的后继指向头节点遍历到头节点时就知道结束了。5. 利用线索进行中序遍历线索化完成后中序遍历就变成了纯指针操作不再需要递归或栈void InOrderTraverse_Thr(BiThrNode* head) { BiThrNode* p head-lchild; // p 指向根节点 while (p ! head) { // 回到头节点时结束 // 第一步找到最左下的节点中序序列的第一个节点 while (p-LTag Link) { p p-lchild; } // 第二步访问当前节点 cout p-data ; // 第三步沿着后继线索一路访问 while (p-RTag Thread p-rchild ! head) { p p-rchild; cout p-data ; } // 第四步转向右子树 p p-rchild; } }遍历过程可以总结为四个步骤的循环向左走到底找到当前子树中最左下的节点即中序序列的起点。访问节点输出当前节点数据。沿后继线索走如果右标志是Thread说明右指针是后继线索直接跳过去访问。转向右子树如果右标志是Link说明右指针指向真正的右孩子进入右子树重复上述过程。核心理解线索化后的中序遍历本质上就是在一个双向链表中来回穿梭。向左走到底找到起点然后不断沿着后继指针前进遇到断点右孩子就进入右子树继续找起点。6. 线索二叉树的图示理解假设有如下二叉树1 / \ 2 3 / \ \ 4 5 6中序遍历序列为4 → 2 → 5 → 1 → 3 → 6线索化之前每个节点的左右指针状态如下表节点lchild是否为空rchild是否为空1指向 2否指向 3否2指向 4否指向 5否3nullptr是指向 6否4nullptr是nullptr是5nullptr是nullptr是6nullptr是nullptr是7 个节点空指针数量 7 1 8 个表中标是的单元格完全符合 n1 的规律。线索化之后这些空指针被重新赋值节点lchild线索化后LTagrchild线索化后RTag1指向 2孩子Link指向 3孩子Link2指向 4孩子Link指向 5孩子Link3指向 1前驱Thread指向 6孩子Link4指向头节点前驱Thread指向 2后继Thread5指向 2前驱Thread指向 1后继Thread6指向 3前驱Thread指向头节点后继Thread注意观察原本的 8 个空指针现在全部变成了有意义的线索。中序遍历时从节点 4 开始沿着后继线索可以一路走到节点 6最后回到头节点形成一个完整的闭环。7. 深度分析线索化 vs 普通遍历下面从几个关键维度对比普通二叉树中序遍历和线索二叉树中序遍历对比维度普通二叉树中序遍历线索二叉树中序遍历空间复杂度O(h) 递归栈 或 O(n) 显式栈O(1)仅使用几个辅助指针查找前驱/后继需要重新遍历或借助父指针O(1) 直接通过线索获取插入节点简单只需修改指针较复杂需要同步维护线索删除节点简单只需修改指针较复杂需要同步维护线索适用场景通用场景树结构频繁变化需要频繁遍历且树结构相对稳定遍历本质深度优先搜索DFS链表式线性遍历关键结论线索二叉树的核心价值在于用空间换时间的逆向思维——它并没有额外分配空间而是把原本就存在的空指针域废物利用从而将遍历的时间效率提升到了极致。付出的代价是插入和删除操作变复杂了因为每次修改树结构都要同步更新线索。8. 完整代码示例下面给出一个完整的、可直接运行的 C 示例包含树的构建、线索化、遍历和内存释放#include iostream using namespace std; enum PointerTag { Link, Thread }; struct BiThrNode { int data; BiThrNode *lchild, *rchild; PointerTag LTag, RTag; BiThrNode(int d) : data(d), lchild(nullptr), rchild(nullptr), LTag(Link), RTag(Link) {} }; BiThrNode* pre nullptr; // 中序线索化 void InThreading(BiThrNode* p) { if (p nullptr) return; InThreading(p-lchild); if (p-lchild nullptr) { p-LTag Thread; p-lchild pre; } if (pre pre-rchild nullptr) { pre-RTag Thread; pre-rchild p; } pre p; InThreading(p-rchild); } // 创建带头节点的线索二叉树 void InOrderThreading(BiThrNode* head, BiThrNode* T) { head new BiThrNode(0); head-LTag Link; head-RTag Thread; head-rchild head; if (T nullptr) { head-lchild head; return; } head-lchild T; pre head; InThreading(T); pre-RTag Thread; pre-rchild head; head-rchild pre; } // 线索化中序遍历 void InOrderTraverse_Thr(BiThrNode* head) { BiThrNode* p head-lchild; while (p ! head) { while (p-LTag Link) p p-lchild; cout p-data ; while (p-RTag Thread p-rchild ! head) { p p-rchild; cout p-data ; } p p-rchild; } cout endl; } int main() { // 手动构建二叉树 // 1 // / \ // 2 3 // / \ \ // 4 5 6 BiThrNode* root new BiThrNode(1); root-lchild new BiThrNode(2); root-rchild new BiThrNode(3); root-lchild-lchild new BiThrNode(4); root-lchild-rchild new BiThrNode(5); root-rchild-rchild new BiThrNode(6); BiThrNode* head nullptr; InOrderThreading(head, root); cout 中序遍历结果; InOrderTraverse_Thr(head); // 输出4 2 5 1 3 6 return 0; }运行这段代码输出为4 2 5 1 3 6正是二叉树的中序遍历序列。整个过程没有使用递归也没有显式维护栈完全依靠线索指针驱动遍历。9. 扩展前序线索化与后序线索化中序线索化是最常用的因为中序遍历的前驱和后继关系最直观。但线索化的思想同样可以应用于前序和后序遍历前序线索化在前序遍历的访问节点环节插入线索化逻辑。前序线索化后可以沿后继线索实现前序遍历但查找前驱比较困难因为前序序列中一个节点的前驱可能是其父节点或兄弟节点关系复杂。后序线索化在后序遍历的访问节点环节插入线索化逻辑。后序线索化后可以沿后继线索实现后序遍历但查找后继比较困难因为后序序列中一个节点的后继同样关系复杂。这也是为什么中序线索二叉树是最实用的——它的前驱和后继关系在树结构上都比较直观查找起来自然方便。10. 总结与思考线索二叉树的精髓可以归纳为三点废物利用不额外分配空间而是把 n1 个空指针域变成有意义的线索。空间换时间用两个标志位的微小代价换取了 O(1) 空间遍历和 O(1) 查找前驱/后继的能力。结构转换把非线性结构树转换成了线性结构双向链表让遍历变得像链表一样简单。在实际应用中线索二叉树的思想被广泛借鉴。例如MySQL 的 InnoDB 存储引擎中B 树的叶子节点之间就通过类似线索的指针串联起来以实现高效的范围查询和顺序扫描。理解了线索二叉树再去理解 B 树叶子节点的链表结构会发现它们有着异曲同工之妙。学习建议建议读者亲手用纸笔画出第 6 节中的示例二叉树然后按照中序线索化的步骤一步步把空指针改成线索再用眼睛沿着线索走一遍中序遍历。这个过程比看十遍代码都管用。参考资料《大话数据结构》程杰 著第 6 章第 7 节「线索二叉树」。