线索二叉树

线索二叉树产生背景

• 解决空间浪费
• 为了寻找某个结点的前驱和后继的时候更加简单快捷，利用有限的空间进行线索化的处理

线索二叉树

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

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

这种指向前驱和后继的指针称为线索。将一棵普通二叉树以某种(前序、中序、后序)次序遍历，它们的遍历次序就知道了，然后添加线索的过程称为线索化。

图1 线索二叉树.png
图中黑色点画线为指向后继的线索，紫色虚线为指向前驱的线索。

可以看出通过线索化，既解决了空间浪费问题，又解决了前驱后继的记录问题。

线索化带来新问题

可以将一棵二叉树线索化为一棵线索二叉树，那么新的问题产生了。我们如何区分一个结点的lchild指针是指向左孩子还是前驱结点呢？例如：对于 图3 所示的结点E，如何区分其lchild的指向的结点J是其左孩子还是前驱结点呢？

为了解决这一问题，现需要添加标志位 ltag，rtag。并定义规则如下：

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

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

图2 添加标志线索二叉树结点.png
图1 所示线索二叉树转变为 图3 所示的二叉树。
图3 添加标志位的钱索二叉材.png

线索二叉树结点数据结构

//#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;  

中序遍历建立线索二叉树

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

//中序遍历进行中序线索化
BitThrTree pre; // 全局变量 - 始终指向刚刚访问的结点
void inThreading(ThrBiTree T, ThrBiTree &pre){  // pre -> 全局变量,始终指向刚刚访问的结点
    if(T){  
        inThreading(T->lchild, pre);//左子树线索化  
  
        if(!T->lchild){//当前结点的左孩子为空  
            T->lTag = Thread;  
            T->lchild = pre;  
        }else{  
            T->lTag = Link;  
        }  
  
        if(!pre->rchild){//前驱结点的右孩子为空  
            pre->rTag = Thread;  
            pre->rchild = T;  
        }else{  
            pre->rTag = Link;  
        }  
        pre = T;          
        inThreading(T->rchild, pre);//右子树线索化  
    }  
}  

加上头结点，遍历线索二叉树

加上线索的二叉树结构是一个双向链表结构，为了便于遍历线索二叉树，我们为其添加一个头结点，头结点左孩子指向原二叉树的根结点，右孩子指针指向中序遍历的最后一个结点。同时，将第一个结点左孩子指针指向头结点，最后一个结点的右孩子指针指向头结点。
图3 所示线索二叉树添加头结点后如 图4 所示：

图4 帯有头结点的线索ニ叉树.png

带有头结点的线索二叉树遍历代码如下：

//T指向头结点，头结点的lchild链域指针指向二叉树的根结点  
//中序遍历打印二叉线索树T（非递归算法）  
void inOrderTraversePrint(ThrBiTree T){  
    ThrBiNode *p = T->lchild;//p指向根结点  
      
    while(p != T){//空树或遍历结束时，p == T  
        while(p->lTag == Link){  
            p = p->lchild;  
        }  
        //此时p指向中序遍历序列的第一个结点（最左下的结点）  
  
        printf("%c ", p->data);//打印（访问）其左子树为空的结点  
  
        while(p->rTag == Thread && p->rchild != T){  
            p = p->rchild;  
            printf("%c ", p->data);//访问后继结点  
        }  
        //当p所指结点的rchild指向的是孩子结点而不是线索时，p的后继应该是其右子树的最左下的结点，即遍历其右子树时访问的第一个节点  
        p = p->rchild;  
    }  
    printf("\n");  
}  

线索二叉树总结

由于充分利用了空指针域的空间（等于节省了空间），又保证了创建时的一次遍历就可以终生受用后继的信息（意味着节省了时间）。所以在实际问题中，如果所用的二叉树需要经过遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。