一、 概念

二叉树按照先序、中序、后续遍历的方法形成一个线性序列后，每个结点（除第一个和最后一个外），都有且仅有一个直接前驱和直接后继。但是，当二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这个信息只在遍历的过程中才能得到。因此引入线索二叉树来保存这些在遍历过程中得到的前驱和后继的信息。

虽然可以在每个结点中增加两个指针域来存放在遍历时得到的有关前驱和后继信息，但这样做使得存储密度大大降低。由于有n个结点的二叉链表中必定存在n+1个空链域，因此可以充分利用这些空链域来存放结点的前驱和后继信息。

Tip：
证明：n个结点的二叉链表中必定存在n+1个空链域
含有n个结点的二叉链表中，每个结点都有两个链域，因此一共有2n个链域。
除了根结点以外的每个点都有一个父结点，所以一共有n-1结点需要使用一个链域来指向父结点。
所以一共有2n-(n-1)=n+1个链域是空的。

为此做如下规定：当结点的左指针为空（即无左子树）时，令该指针指向该结点的前驱结点；当结点的右指针为空（即无右子树）时，令该指针指向该结点的后继结点；为了避免混淆，还需要增加两个标志位来区分指针指向的是其孩子还是前驱及后继。

image.png

typedef struct BiThrNode  
{  
   TelemTpye data;  
   struct BiThrNode *lchild,*rchild;      /*左右孩子指针*/  
   int LTag,RTag;               /*左右标志*/  
} BiThrNode,*BiThrTree; 

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。

对二叉树以某种次序遍历使其变成线索二叉树的过程叫做线索化。

二、建立线索二叉树

线索化的过程就是遍历二叉树的过程。在遍历的过程中，检查当前结点的左、右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。

二叉树的中序序列a+b*c-d-e/f，形成的中序线索链表，如下图所示：

image.png

以结点为根的中序线索化算法：

void InThreading(BiThrTree p) {  
    //pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
    if (p) {  
        InThreading(p->lchild);            /*左子树递归线索化*/  
        if(!p->lchild) {                      /*p的左孩子为空*/  
            p->LTag=1;                     /*给p加上左线索*/  
            p->lchild=pre;                 /*p的左孩子指针指向pre(前驱)*/  
        }  
        else {  
            p->LTag=0;  
        }  
        if(!pre->rchild) {                  /*pre的右孩子为空*/  
            pre->RTag=1;                  /*给pre加上右线索*/  
            pre->rchild=p;                /*pre的右孩子指针指向p(后继)*/  
        }  
        else {
            pre->RTag=0;  
        }  
        pre=p;                            /*保持pre指向p的前驱*/  
        InThreading(p->rchild);           /*右子树递归线索化*/  
     }  
}  

三、遍历线索二叉树

由于有了结点的前驱和后继信息，线索二叉树的遍历和在指定次序下查找结点的前驱和后继算法都变得简单。因此，若需经常查找结点的前驱和后继，就可以采用线索链表作为存储结构。

1、 在中序线索二叉树中查找
A、 查找p指针所指结点的前驱：
若p->LTag = 1，则p的左链指示其前驱（/ 的前驱是e）
若p->LTag = 0，则说明p有左子树，结点的前驱是遍历左子树时最后访问的一个结点（* 的前驱是b）
B、 查找p指针所指结点的后继：
若p->RTag = 1，则p的右链指示其后继。（b的后继为）
若p->RTag = 0，则说明p有右子树。结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。（查找的后继时，首先沿右指针找到其右子树的根结点-，然后顺其左指针往下直至其左标志为1的结点，即为结点*的后继，是结点c。）

2、 在先序线索二叉树中查找（以下图为例：先序遍历为1 2 4 8 9 5 10 11 3 6 12 7）
A、 查找p指针所指结点的前驱：
若p->LTag = 0，则说明p有左子树，此时p的前驱有两种情况：若p是其双亲的左孩子，则其前驱为其双亲结点（4结点，因为有左孩子8，所以p->LTag = 0，而4又是双亲2的左孩子，所以4的前驱是其双亲2），否则应是其双亲的左子树上先序遍历最后访问到的结点（5结点，因为有左孩子10，所以p->LTag = 0，而5又是其双亲2的右孩子，所以他的前驱为双亲2的左子树先序遍历最后访问的结点9）
B、 查找p指针所指结点的后继：
若p->RTag = 0，则说明p有右子树， p的后继必为其左子树根(若存在)或右子树根。（2结点有右子树，所以p->RTag = 0，而2又有左子树，所以2的后继为左子树的根4，如果没有6,12这两个结点，3结点有右子树，所以p->RTag = 0，但3没有左子树，所以3的后继为右子树的根7）

image.png

3、 在后序线索二叉树中查找 （以上图为例：后序遍历为8 9 4 10 11 5 2 12 6 7 3 1）
A、 查找p指针所指结点的前驱：
若p->LTag = 0，当p->RTag也为0时，则p的右链指示其前驱（结点4有左右两个孩子，因此p->LTag = 0， p->RTag = 0，4的前驱为右链9）；若p->LTag=0，而p->RTag=1，则p的左链指示其前驱（结点6只有左孩子，因此p->LTag = 0， p->RTag = 1，6的前驱为左链12）。
B、 查找p指针所指结点的后继情况比较复杂，分以下情况讨论：
以下图为例：后序遍历为：A B C D E F G H
若p是二叉树的根，则后继为空。
若p是其双亲的右孩子，则后继为双亲结点。（B的后继为C，结点C的后继为D）
若p是其双亲的左孩子，且p没有右兄弟，则其后继为双亲结点。（结点F的后继为G）
若p是其双亲的左孩子，且p有右兄弟，则其后继为双亲的右子树上按后序遍历列出的第一个结点(即右子树中“最左下”的叶结点) 。（结点D的后继为E）

image.png