在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。

(1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。

(2)任意一个结点都能直接找到它的前驱和后继结点。

(1)结点的插入和删除麻烦，且速度也较慢。

(2)线索子树不能共用。

线索二叉树中的线索能记录每个结点前驱和后继信息。为了区别线索指针和孩子指针，在每个结点中设置两个标志ltag和rtag。

当ltag和rtag为0时，leftChild和rightChild分别是指向左孩子和右孩子的指针；否则，leftChild是指向结点前驱的线索(pre)，rightChild是指向结点的后继线索(suc)。由于标志只占用一个二进位，每个结点所需要的存储空间节省很多。

现将二叉树的结点结构重新定义如下：

其中：ltag=0 时lchild指向左儿子；ltag=1 时lchild指向前驱；rtag=0 时rchild指向右儿子；rtag=1 时rchild指向后继。

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。

另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

下面是建立中序二叉树的递归算法，其中pre为全局变量。

进行中序线索化的算法：

线索二叉树查找前驱和后继：

（1）中序线索二叉树：若结点的ltag=1，lchild指向其前驱；否则，该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。若rtag=1，rchild指向其后继；否则，该结点的后继是以该结点为根的右子树上按中序遍历的第一个结点。

求后继的算法如下：

求前驱的算法如下：

（2） 后序线索二叉树：

在后序线索二叉树中查找结点*p的前驱：若结点*p无左子树，则p->lchild指向其前驱；否则，若结点*p有左子树，当其右子树为空时，其左子树的根（即p->lrchild）为其后序前驱。当其右子树非空时，其右子树的根（即p->rchild）为其后序前驱。

在后序线索二叉树中查找结点*p的后继：若结点*p为根，则无后继；若结点*p为其双亲的右孩子，则其后继为其双亲；若结点*p为其双亲的左孩子，且双亲无右子女，则其后继为其双亲；若结点*p为其双亲的左孩子，且双亲有右子女，则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。所以，求后序线索二叉树中结点的后继要知道其双亲的信息，要使用栈，所以说后序线索二叉树是不完善的。

（3）先序线索二叉树：

在先序线索二叉树中查找结点的后继较容易，而查找前驱要知道其双亲的信息，要使用栈，所以说先序线索二叉树也是不完善的。