线索二叉树是什么？它为什么能加速遍历中的前驱和后继查找？
简化版
线索二叉树利用普通二叉树中的空指针，保存某种遍历序列下的前驱或后继。比如中序线索二叉树会让空左指针指向中序前驱，空右指针指向中序后继，从而不用栈或递归也能沿线索遍历。
详细版
普通二叉树有很多空指针。n 个节点的二叉链表有 2n 个孩子指针，但只有 n-1 条真实边，因此有 n+1 个空指针。线索二叉树把这些空指针利用起来。
关键点：
- left/right 可能指向真实孩子，也可能指向前驱/后继。
- 需要额外标记区分指针类型，比如
leftTag、rightTag。 - 常见是中序线索，因为中序前驱后继很常用。
- 遍历时可以沿线索找下一个节点，减少栈空间。
它是一种偏底层和教材型的数据结构，工程中不常手写，但能帮助理解遍历序列和空指针利用。
完整版教学
一、为什么二叉树会有很多空指针
用左右孩子指针存二叉树时，每个节点有两个指针。n 个节点一共有 2n 个指针位置。真实边只有 n-1 条，因为除了根节点外，每个节点刚好有一个父边。
所以空指针数量是：
空指针数 = 2n - (n - 1) = n + 1如果有 100 个节点，就有 101 个空孩子指针。线索二叉树的想法就是：这些空位能不能存点有用信息？
二、线索存的是什么
以中序遍历为例，序列可能是：
D, B, E, A, F, C对于节点 E，它的中序前驱是 B，后继是 A。如果 E 没有右孩子，就可以把 E 的右指针指向 A，表示后继线索。如果 E 没有左孩子，就可以把左指针指向 B，表示前驱线索。
这不是改变树的父子结构，而是在空指针位置增加遍历导航信息。
三、为什么需要 tag 标记
问题来了：node.right 到底是真实右孩子，还是中序后继线索？如果不标记，遍历会把线索误当成子树边，甚至走出错误结构。
常见节点字段：
left, right
leftTag: 0 表示 left 是孩子，1 表示 left 是线索
rightTag: 0 表示 right 是孩子，1 表示 right 是线索| 指针 | tag=0 | tag=1 |
|---|---|---|
| left | 左孩子 | 遍历前驱 |
| right | 右孩子 | 遍历后继 |
tag 是线索二叉树正确性的必要部分。
四、中序后继如何查找
在线索二叉树里找中序后继分两种情况。如果 rightTag == 1，右指针直接就是后继。如果 rightTag == 0，说明有真实右子树，后继是右子树里最左的节点。
if rightTag == THREAD:
successor = right
else:
successor = leftmost(rightSubtree)这个逻辑和普通中序后继一致，只是空右指针时不用回溯找祖先，而是直接沿线索走。
五、线索化如何建立
建立中序线索通常在一次中序遍历中完成。遍历时维护前一个访问节点 prev，当前节点是 cur。
如果 cur.left 为空，cur.left = prev，leftTag = THREAD
如果 prev.right 为空，prev.right = cur，prev.rightTag = THREAD
prev = cur这相当于在中序访问顺序中，把相邻节点用空指针串起来。构建需要 O(n) 时间。
六、收益和局限
线索二叉树的收益是遍历时可以少用栈，前驱后继查找更直接。局限是节点结构更复杂，插入删除要维护线索，容易出错。
记忆钩子：线索二叉树不是多长一棵树，而是把空孩子指针改造成遍历序列里的“前后路标”。
七、常见误区与追问
- 误区：线索指针也是父子边。 线索是遍历前驱/后继，不代表树的结构边。
- 误区：不需要 tag 也能区分。 没有 tag 就无法可靠判断指针是孩子还是线索。
- 误区：线索二叉树只支持中序。 前序、后序也可以线索化，只是中序最常见。
- 追问：空指针为什么是 n+1 个？ 二叉链表有 2n 个指针，真实边 n-1 条，所以空指针是 n+1。
- 追问：插入删除为什么麻烦？ 因为不仅要改父子边，还要维护相邻节点的前驱后继线索。
八、加强记忆
线索二叉树的核心是“空指针再利用”。普通树的空 left/right 什么也不表示，线索树让它们指向遍历序列中的前驱后继，并用 tag 区分指针类型。它让遍历导航更方便，但维护成本也更高。