线索二叉树
普通二叉链表里，大量 left / right 为空。线索二叉树（Threaded Binary Tree）利用这些空指针，指向某种遍历次序下的前驱或后继，从而在不借助递归栈或显式栈的情况下完成遍历。
最常见的是中序线索二叉树。
本文解决什么问题
- 线索要解决什么痛点
- 左 / 右线索分别存什么
- 现代工程中如何定位这一结构
基本想法
为每个指针增加一个标志位（或用枚举）：
| 指针 | 若指向孩子 | 若为空（线索化后） |
|---|---|---|
left | 左孩子 | 中序前驱 |
right | 右孩子 | 中序后继 |
lflag == 0: left 是孩子
lflag == 1: left 是前驱线索
rflag 同理
建线索的过程，本质上是在中序遍历时，把「上次访问的结点」与「当前结点」互相穿线。
中序线索下的遍历直觉
找到中序第一个结点（从根一路向左，考虑线索规则），然后反复：
- 若有右线索，直接走到后继
- 否则进入右子树，再一路沿左孩子走到头
这样可以用 额外空间走完整棵树（不计输出）。
价值与定位
| 角度 | 说明 |
|---|---|
| 教学 | 帮助理解遍历中的前驱 / 后继 |
| 历史 / 教材 | 经典数据结构内容 |
| 现代工程 | 更常用递归、显式栈、父指针或迭代器；线索树相对少见 |
本篇以建立概念为目标。完整「建线索 + 遍历」代码可作为选做：务必画图，标志位与孩子指针很容易写混。
和遍历篇的关系
先熟练 二叉树的遍历，再看线索，会更容易理解「前驱后继从哪来」。
小结
线索 = 空指针改存前驱 / 后继信息。知道它在优化「遍历辅助空间」上的动机，即可；工程实现优先用更常见的栈式 / 递归遍历。
下一篇：二叉搜索树。