线索二叉树

在计算机科学中，引線二元樹（或稱引线二叉树）是添加了直接指向节点的前驱和后继的指针的二叉树。

定义

 

这是一个线索二叉树，有着指向父节点的特殊指针（图中虚线所示）

线索二叉树 的定义如下:

“一个二叉树通过如下的方法“穿起来”：所有原本为空的右子節點指针改为指向该节点在中序序列中的后继，所有原本为空的左子節點指针改为指向该节点的中序序列的前驱。”^[1]

线索二叉树能线性地遍历二叉树，从而比递归的中序遍历更快。使用线索二叉树也能够方便的找到一个节点的父节点，这比显式地使用父亲节点指针或者栈效率更高。这在栈空间有限，或者无法使用存储父节点的栈时很有作用（对于通过深度优先搜索来查找父节点而言）。 考虑这样的例子：一个节点k有一个右子節點r，那么r的左指针可能是指向一个子節點节点，或是一个指回k的线索。如果r有左子節點，这个左子節點同样也应该有一个左子節點或是指回k的线索。对于所有的左子節點同理。因此沿着这些从r发出的左指针，我们最终会找到一个指回k的线索。这种特性是对称的：当q是p的左子節點时，我们可以沿着q的右子節點找到一个指回p的线索。

传统的二叉树一般都是以链式存储的结构来表示。这样，二叉树中的每个节点都可以用链表中的一个链节点来存储，每个链节点就包含了若干个指针。但是，这种传统的链式存储结构只能表现出二叉树中节点之间的父子关系，而且不能利用空余的指针来直接得到某个节点的在特定的遍历顺序（先序，中序，后序）中的直接前驱和直接后继。通过分析传统的二叉树链式存储结构表示的二叉树中，存在大量的空闲指针。若能利用这些空指针域来存放指向该节点的直接前驱或是直接后继的指针，则可以进行某些更方便的运算。这些被重新利用起来的空指针就被称为线索，加上了这些线索的二叉树就是线索二叉树。

线索化

对二叉树以某种遍历顺序进行扫描并为每个节点添加线索的过程称为二叉树的线索化，进行线索化的目的是为了加快查找二叉树中某节点的前驱和后继的速度。 那么在有N个节点的二叉树中需要利用N+1个空指针添加线索。这是因为在N个节点的二叉树中，每个节点有2个指针，所以一共有2N个指针，除了根节点以外每一个节点都有一个指针从它的父节点指向它，所以一共使用了N-1个指针。所以剩下2N-(N-1)个空指针。

参考文献

1. Van Wyk, Christopher J. Data Structures and C Programs, Addison-Wesley, 1988, p. 175. ISBN 978-0-201-16116-8.