|
|
|
以二叉链表作为存储结构时，只能找到左、右子树信息，不能直接得到结点在任一序列中的前驱和后继信息，最简单的方法是每个结点上增加两个指针域，但有点浪费。其实，n个结点的二叉链表中必定存在n+1个空链域，因此可用这些链域来存放结点的前驱和后继信息。改进后的结点结构如下。
|
|
|
|
|
|
其中，ltag=0：表示lchild域指示结点的左子树。
|
|
|
|
|
|
rtag=0：表示rchild域指示结点的左子树。
|
|
|
|
|
|
|
|
|
|
以这种结构构成的二叉链表叫作线索链表，其中指向结点前驱和后继的指针叫线索。加上线索的二叉树叫线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程叫作线索化。
|
|
|
|
对给定的线索二叉树中的某个结点p，查找结点p的后继（中序），其特点为所有叶子结点的右链直接指示了后继，所有非终端结点的后继应是其右子树中第一个中序遍历的结点。
|
|
|
|
对给定的线索二叉树中的某个结点p，查找结点p的前驱（中序），其特点为若其左标志为1，则左链为线索，指示其前驱，否则其前驱为左子树上最后遍历的一个结点。
|
|
|
|
可见，对线索二叉树进行遍历可通过线索找到相应的前驱和后继，而无须进行递归。
|
|
|
|
例如，对给定的中序线索化二叉树，查找结点*p的中序后继。在中序线索二叉树中，查找p指针的结点，其后继分为两种情况：若p->rtag=1，则p->rchild，即指向其后继结点；若p->rtag=0，则*p结点的中序后继必为其右子树中第一个中序遍历到的结点，即从*p的右子树开始，沿着左指针链向下找，直到找到一个没有左子树的结点，该结点就是*p的右子树中"最左下"的结点。其算法如下：
|
|
|
|
|
