线索二叉树
在计算机科学中，二叉树添加了直接指向节点的前驱和后继的指针的二叉树称为线索二叉树。
线索二叉树(引线二元树) 的定义如下:
“一个二叉树通过如下的方法“穿起来”：所有应该为空的右孩子指针指向该节点在中序串行中的后继，所有应该为空的左孩子指针指向该节点的中序串行的前驱。”
线索二叉树能线性地遍历二叉树，从而比递归的 中序遍历更快。使用线索二叉树也能够方便的找到一个节点的父节点，这比显式地使用父亲节点指针或者栈效率更高。这在栈空间有限，或者无法使用存储父节点的栈时很有作用（对于通过深度优先搜索来查找父节点而言)。 考虑这样的例子：一个节点k有一个右孩子r，那幺r的左指针可能是指向一个孩子节点，或是一个指回k的线索。如果r有左孩子，这个左孩子同样也应该有一个左孩子或是指回k的线索。对于所有的左孩子同理。因此沿着这些从r发出的左指针，我们最终会找到一个指回k的线索。这种特性是对称的：当q是p的左孩子时，我们可以沿着q的右孩子找到一个指回p的线索。