二叉树的线索化

有 n 个结点的二叉链表中，其二叉链表的 n 个结点中共有 2n 个指针域，在这 2n 个指针域中，真正用于指向后件（左子结点或右子结点）的指针域只有 n-1 个，而另外的 n+1 个指针域都是空的。这样就利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为 " 线索 "），这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树 (ThreadedBinaryTree) 。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

线索链表的结点结构

线索链表中的结点结构为：
ltag 和 rtag 是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。

---

二叉树的线索化

线索化和线索化实质

将二叉树变为线索二叉树的过程称为线索化 。按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指针。

二叉树的中序线索化

算法与中序遍历算法类似，只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。
a). 若上次访问到的结点的右指针为空，则将当前访问到的结点地址填入，并置右标志域为 1
b). 若当前访问到的结点的左指针为空，则将上次访问到的结点地址填入，并置左标志域为 1

---

如何使用二叉线索树

在中序线索二叉树中，查找结点 *p 的中序后继结点分两种情形：
a). 若 *p 的右子树空 ( 即 p->rtag 为 Thread) ，则 p->rchild 为右线索，直接指向 *p 的中序后继。
b). 若 *p 的右子树非空 ( 即 p->rtag 为 Link) ，则 *p 的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p 的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是 *p 的右子树中 “ 最左下 ” 的结点，即 *P 的中序后继结点。
具体算法如下：

BinThrNode *Inorderpre(BinThrNode *p)  
{   //在中序线索树中找结点*p的中序前趋，设p非空  
    BinThrNode *q；  
    if (p->ltag==Thread) //*p的左子树为空  
        return p->lchild； //返回左线索所指的中序前趋  
    else{  
        q=p->lchild； //从*p的左孩子开始查找  
        while (q->rtag==Link)  
            q=q->rchild； //右子树非空时，沿右链往下查找  
        return q； //当q的右子树为空时，它就是最右下结点  
    } //end if  
}  

---