遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化操作，使得每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。
当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。
那么，如果有一个需要大量查询前驱后继的程序，对于每次都遍历，时间成本过大，我们便需要能快速查找前驱后继的办法。最简单的方法，每个结点加两个存储前驱后继的变量，但是这样却浪费大量的空间。
另一种方法，对于n个结点的二叉链表中必定存在n+1个空链域，由此，可以利用这些空链域来存放结点的前驱和后继的信息。
规定如下：若结点有左子树，则其lchild域指示其左孩子。否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。（为了避免混淆，尚需改变结点结构，增加两个标志域，用来区分其左右孩子指针到底指向的是子树还是前驱后继）。
更改为这种结构的二叉链表作为二叉树的存储结构叫做线索链表，其中指向结点前驱和后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空时为止。
在后序线索树中招结点后继较为复杂些，可分为3种情况：
- 若结点x是二叉树的根，则其后继为空
- 若结点x使其双亲的右孩子或左孩子且其双亲没有右子树，则其后继即为双亲结点
- 若结点x是其双亲的最孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点
为方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，病令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；反之，灵感二叉树中序序列中的第一个结点的l迟来的域指针和最后一个结点rchild域的指针均指向头结点。
这好比为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
以双向线索链表为存储结构是对二叉树进行遍历的算法：
Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType)) {
// T指向头结点，头结点的左链lchild指向根结点，头结点的右链lchild指向
// 中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T，
// 对每个数据元素调用函数Visit。
BiThrTree p;
p = T->lchild; // p指向根结点
while (p != T) { // 空树或遍历结束时，p==T
while (p->LTag==Link) p = p->lchild;
if (!Visit(p->data)) return ERROR; // 访问其左子树为空的结点
while (p->RTag==Thread && p->rchild!=T) {
p = p->rchild; Visit(p->data); // 访问后继结点
}
p = p->rchild; // p进至其右子树根
}
return OK;
} // InOrderTraverse_Thr
线索化
由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继是信息是只有在遍历的时候才能得到，因此，线索化的过程即为在遍历的过程中修改空指针的过程。
为记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则per指向他的前驱。由此，可得中序遍历建立中序线索化链表的算法：
Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { // 算法6.6
// 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。
if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
Thrt->LTag = Link; Thrt->RTag =Thread; // 建头结点
Thrt->rchild = Thrt; // 右指针回指
if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指
else {
Thrt->lchild = T; pre = Thrt;
InThreading(T); // 算法6.7：中序遍历进行中序线索化
pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化
Thrt->rchild = pre;
}
return OK;
} // InOrderThreading
更多基础介绍：线索二叉树概要
