线索二叉树

定义

线索二叉树指在结点上加上了线索的二叉树，而按照某种遍历次序将普通二叉树改造成线索二叉树的过程称为线索化^[1]。在通常采用的链式存储中，若某结点没有左子树，就让它空的左指针指向该结点在遍历序列中的前驱；若没有右子树，就让它空的右指针指向后继，这些被重新利用起来的指针就是线索^[2]。

按照所用遍历次序的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树，其中中序线索二叉树最为常用^[3]。线索化的目的，是加快查找某结点前驱与后继的速度，使遍历不必再依赖递归过程或人工设置的栈^[2]。

原理

一棵含有 n 个结点的二叉树，其二叉链表中一共有 2n 个指针域，除根结点外每个结点都有 1 个指针被父结点占用，因此非空指针只有 n-1 个，剩下 n+1 个指针是空的^[2]。线索化正是把这批空闲指针利用起来，在中序遍历等过程中顺手记录前驱和后继，从而把一棵非线性的树改造得接近线性的双向链表。

为了区分某个指针指向的是孩子还是线索，结点结构中要增设两个标志位，通常记作 ltag 与 rtag。当 ltag 为 0 时左指针指向左孩子，为 1 时指向该结点的前驱；rtag 为 0 时右指针指向右孩子，为 1 时指向后继^[1]。标志位只占一个二进制位，因此额外的空间开销很小^[4]。

结点结构可以表示为：$[lchild, ltag, data, rtag, rchild]$。线索化的实质就是遍历二叉树并在访问结点时改写空指针，实现时用一个指针 pre 始终记录刚刚访问过的结点，便于把当前结点与它的前驱互相连接^[1]。为了方便从两个方向遍历，还可以在根结点之上增加一个头结点，让首结点的左指针和末结点的右指针都指向它。

在中序线索二叉树中查找后继时，若该结点的右标志为 1，则右指针本身就是后继；否则后继是其右子树中序遍历时最先访问的那个结点，即右子树里最靠左下的结点^[5]。查找前驱的规则与之对称^[6]。

发展历程

1960 年，艾伦·佩利斯(Alan J. Perlis)与查尔斯·桑顿(Charles Thornton)在《Communications of the ACM》上发表了题为《Symbol Manipulation by Threaded Lists》的论文，提出用链表空指针充当线索的方法，这被视为线索思想的起点^[7]。此后线索二叉树被引入数据结构教材，成为二叉树遍历一章的常规内容^[8]。

早期的线索树主要针对中序线索，只设置右线索，用于免栈的中序遍历^[9]。随后的教材与文献把线索扩展到左、右两个方向，并推广到前序、后序和中序 3 种形式^[1]。也有研究提出重新定义标志位或改进结点结构，使前序、后序遍历的效率高于经典方案，但这些改进多数停留在教学与理论讨论层面^[10]。

应用

线索二叉树最直接的用途是免栈遍历：中序遍历可以从最左下的结点出发，反复沿右线索跳到后继，整个过程不需要递归也不需要辅助栈，时间复杂度仍为 O(n)，额外空间降为常数级^[5]。在线索化结构上按前驱和后继顺序推进，与扫描一个双向链表类似。

由于不必显式保存父结点指针或栈，线索结构适合栈空间紧张或无法分配父指针的场合^[2]。在嵌入式系统、编译器中对语法树的中序遍历，以及数据库索引的遍历优化中，都有人采用这类思路^[11]。此外，线索化二叉搜索树也被用作实现迭代器、以及快速求结点前驱和后继的基础^[12]。

局限

线索二叉树的主要代价在插入和删除：结点增减之后必须同步修改相关线索，否则线索链会错乱，因此这两种操作比普通二叉树更麻烦、更慢，线索化的子树也难以被多棵二叉树共用。当树结构经常变动时，维护线索的额外开销可能抵消遍历带来的收益^[13]。

线索对遍历的帮助并不均衡。前序和中序线索可以方便地找到任意结点在相应次序下的后继，后序线索则很难直接给出后序后继^[2]。因此后序线索二叉树通常需要配合其他手段才能完成遍历。

线索化的实现还需要正确维护标志位与指针的一致性，一旦某次改写指针却忘记同步标志位，遍历时就会把线索误当作子树入口，导致越界访问或死循环^[14]。有观点认为，由于实际项目中真正需要这种结构的场合有限，部分教材已在讨论其理论价值与实际地位的差别^[10]。

参见

• 二叉树 —— 线索二叉树是在其链式存储结构上改造而成的变体。

• 二叉链表 —— 线索化所利用的空指针域正出自这种存储方式。

• 二叉树遍历 —— 线索化的次序与遍历次序一一对应。

• 二叉搜索树 —— 线索化的思路常被用于加速其迭代遍历。

• 栈 —— 线索二叉树以线索取代了遍历中辅助栈的作用。