本身是一种非线性结构，采用任何一种遍历二叉树的方法，都可以得到树中所有结点的一个线性序列。在这个序列中，除第一个结点外，每个结点都有自己的直接前趋；除最后一个结点外，每个结点都有一个直接后继。

　　线索二叉树不需要如此，在遍历的同时，使用二叉树中空闲的内存空间记录某些结点的前趋和后继元素的位置（不是全部）。这样在算法后期需要遍历二叉树时，就可以利用保存的结点信息，提高了遍历的效率。使用这种方法构建的二叉树，即为

　　线索二叉树的结点结构如果在二叉树中想保存每个结点前趋和后继所在的位置信息，最直接的想法就是改变结点的结构，即添加两个指针域，分别指向该结点的前趋和后继。但是这种方式会降低树存储结构的存储密度。而对于二叉树来讲，其本身还有很多未利用的空间。

　　存储密度指的是数据本身所占的存储空间和整个结点结构所占的存储量之比。每一棵二叉树上，很多结点都含有未使用的指向NULL的指针域。除了度为2的结点，度为 1 的结点，有一个空的指针域；叶子结点两个指针域都为NULL。

　　链表中必定存在 n+1 个空指针域。线索二叉树实际上就是使用这些空指针域来存储结点之间前趋和后继关系的一种特殊的二叉树。

　　线索二叉树中，如果结点有左子树，则 lchild 指针域指向左孩子，否则 lchild 指针域指向该结点的直接前趋；同样，如果结点有右子树，则 rchild 指针域指向右孩子，否则 rchild 指针域指向该结点的直接后继。为了避免指针域指向的结点的意义混淆，需要改变结点本身的结构，增加两个标志域，如图 2 所示。

　　图2 线索二叉树中的结点结构LTag 和 RTag 为标志域。实际上就是两个布尔类型的变量：

　　线索化。对二叉树进行线索化将二叉树转化为线索二叉树，实质上是在遍历二叉树的过程中，将二叉链表中的空指针改为指向直接前趋或者直接后继的线索。

　　线索化的过程即为在遍历的过程中修改空指针的过程。在遍历过程中，如果当前结点没有左孩子，需要将该结点的 lchild 指针指向遍历过程中的前一个结点，所以在遍历过程中，设置一个指针（名为 pre ），时刻指向当前访问结点的前一个结点。代码实现（拿中序遍历为例）：//中序对二叉树进行线索化 void InThreading(BiThrTree p){ //如果当前结点存在 if (p) { InThreading(p-lchild);//递归当前结点的左子树，进行线索化 //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre if (!p-lchild) { p-Ltag=Thread; p-lchild=pre; } //如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。 if (!pre-rchild) { pre-Rtag=Thread; pre-rchild=p; } pre=p;//线索化完左子树后，让pre指针指向当前结点 InThreading(p-rchild);//递归右子树进行线索化 } }注意：中序对二叉树进行线索化的过程中，在两个递归函数中间的运行程序，和之前介绍的中序遍历二叉树的输出函数的作用是相同的。

　　将中间函数移动到两个递归函数之前，就变成了前序对二叉树进行线索化的过程；后序线索化同样如此。

　　使用线 中是一个按照中序遍历建立的线索二叉树。其中，实线表示指针，指向的是左孩子或者右孩子。虚线表示线索，指向的是该结点的直接前趋或者直接后继。

　　使用线索二叉树时，会经常遇到一个问题，如图 3 中，结点 b 的直接后继直接通过指针域获得，为结点 * ；而由于结点 * 的度为 2 ，无法利用指针域指向后继结点，整个链表断掉了。当在遍历过程，遇到这种问题是解决的办法就是：

　　寻找先序、中序、后序遍历的规律，找到下一个结点。在先序遍历过程中，如果结点因为有右孩子导致无法找到其后继结点，如果结点有左孩子，则后继结点是其左孩子；否则，就一定是右孩子。拿图 3 举例，结点 + 的后继结点是其左孩子结点 a ，如果结点 a 不存在的话，就是结点 * 。