|
以二叉链表作为存储结构时,只能找到左、右子树信息,不能直接得到结点在任一序列中的前驱和后继信息,最简单的方法是每个结点上增加两个指针域,但有点浪费。其实,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的右子树中"最左下"的结点。其算法如下:
|
|
|
|