5.3.2 线索二叉树

二叉链表有 $n+1$ 个空指针，可利用它们指向某种遍历序列中的前驱或后继。必须增加 ltag/rtag 区分孩子指针与线索：0 表示孩子，1 表示线索。线索化不能覆盖真实子树。

手工推演

中序序列为 D-B-E-A-C。D 无左孩子，左线索为空前驱；D 的右线索指 B；E 的左线索指 B、右线索指 A；C 的左线索指 A。寻找中序后继：若 rtag=1 直接取右线索，否则进入右子树并一路走真实左孩子。

结构与代码

线索化时维护 prev 指向刚访问的结点。在中序访问当前 p 时，若 p->left==NULL 建前驱线索；若 prev 的右指针为空，为 prev 建后继线索；再令 prev=p。

错解反馈

不检查 tag 就沿线索递归会形成循环；把先序线索规则套到中序；认为有线索后任意前驱后继都必为 $O(1)$，实际沿子树找最左/最右可能需多步。

迁移练习

给中序序列 DBEAC，写 E、A 的前后继。E 前驱 B、后继 A；A 前驱 E、后继 C。验收要求区分哪条是线索、哪条是真孩子边。