产生背景

现有一棵结点数目为n的二叉树，采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域，而结点为n的二叉树一共有n-1条有效分支路径。那么，则二叉链表中存在2n-(n-1)=n+1个空指针域。那么，这些空指针造成了空间浪费。
例如：下图所示一棵二叉树一共有10个结点，空指针^有11个。

此外，当对二叉树进行中序遍历时可以得到二叉树的中序序列。例如：上图所示二叉树的中序遍历结果为HDIBJEAFCG，可以得知A的前驱结点为E，后继结点为F。但是，这种关系的获得是建立在完成遍历后得到的，那么可不可以在建立二叉树时就记录下前驱后继的关系呢，那么在后续寻找前驱结点和后继结点时将大大提升效率。

线索化

现将某结点的空指针域指向该结点的前驱后继，定义规则如下：

若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。
若结点的右子树为空，则该结点的右孩子指针指向其后继结点。

这种指向前驱和后继的指针称为线索。将一棵普通二叉树以某种次序遍历，并添加线索的过程称为线索化。

图中黑色点画线为指向后继的线索，紫色虚线为指向前驱的线索。
可以看出通过线索化，既解决了空间浪费问题，又解决了前驱后继的记录问题。

线索化带来新问题

经过前面讲解后，可以将一棵二叉树线索化为一棵线索二叉树，那么新的问题产生了。我们如何区分一个结点的lchild指针是指向左孩子还是前驱结点呢？例如：对于上图所示的结点E，如何区分其lchild的指向的结点J是其左孩子还是前驱结点呢？
为了解决这一问题，现需要添加标志位ltag，rtag。并定义规则如下：

ltag为0时，指向左孩子，为1时指向前驱
rtag为0时，指向右孩子，为1时指向后继

添加ltag和rtag属性后的结点结构如下：

添加标志位的线索二叉树

线索二叉树结点数据结构

//#define Link 0//指针标志  
//#define Thread 1//线索标志  
typedef char TElemType;   
//中序线索二叉树  
typedef enum PointerTag {Link, Thread};//结点的child域类型，link表示是指针，指向孩子结点，thread表示是线索，指示前驱或后继结点  
//定义结点数据结构
typedef struct ThrBiNode{  
    TElemType data;  
    ThrBiNode *lchild, *rchild;//左右孩子指针  
    PointerTag lTag, rTag;//左右标志  
}ThrBiNode, *ThrBiTree;  

中序遍历建立线索二叉树

中序遍历的方法已经在第一篇二叉树基础中讲解过，那么实现线索化的过程就是在中序遍历同时修改结点空指针的指向。
采用中序遍历的访问顺序实现一棵二叉树的线索化过程代码如下：

//中序遍历进行中序线索化
void inThreading(ThrBiTree T, ThrBiTree &pre){  
    if(T){  
        inThreading(T->lchild, pre);//左子树线索化  
  
        if(!T->lchild...

课后习题

【2014年真题】若对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分别是 （）

A．e、c         B．e、a         C．d、c         D．b、a 

参考答案：D
答案解析：线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点， 所以先写出二叉树的中序遍历序列：edbxac，中序遍历中在 x 左边和右边的字符，就是它在 中序线索化的左、右线索，即 b、a，选 D。 

【2013年真题】若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是（）
A. X 的父结点                 B. 以 Y 为根的子树的最左下结点 
C. X 的左兄弟结点 Y         D. 以 Y 为根的子树的最右下结点 

参考答案：A
答案解析：根据后续线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后续遍历的方式可知 X 结点的后继是其父结点，即其右线索指向的是父结点。 

【2010年真题】下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）

参考答案：D
答案解析：考查线索二叉树的基本概念和构造。
题中所给二叉树的后序序列为 dbca 。结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b 无左子树，左链域指向其前驱结点 d；结点 c 无左子树，左链域指向其前驱结点 b，无右子树，右链域指向其后继结点 a。