线索二叉树

问题由来：

1.观察下面的二叉树结构，可以发现其叶子节点有许多的空指针域：

2.当遍历一个二叉树的时候，比如中序遍历，得到HDIBEJAFCG这样的字符序列，遍历过后，我们可以知道，结点I的前驱是D，后继是B，结点F的前驱是A，后继是C。但是对这个序列，我们在遍历之前是不知道的，要知道某个节点的前驱和后继只有在遍历时才会发现。

所以，由上面的两点发现，可以借助这些空指针域来存放一些节点的前驱和后继 。还是以中序遍历为例，我们把节点的空左孩子指向该节点的前驱，而把节点的空右孩子指向该节点的后继，像这样：             这样就形成了线索二叉树。

对于这样的线索二叉树，问题是对于某一节点，如何知道该节点的左指针指向的是其左孩子节点还是其前驱，如何指导右指针指向的时其右孩子或是后继？比如I节点，其左右两个指针指向的都是其前驱和后继；而E节点，其左指针指向的是左孩子J，右指针指向后继。

对上面的问题，可以为每个节点设置左右两个标签Tag，lTag和rTag, tag的值为link表示指针指向的是孩子节点，值为thread表示指针指向的是该节点的前驱或后继。

struct biThrNode;
typedef struct biThrNode* BiThrTree;
typedef struct biThrNode* Thrnode;

//link表示指向指针指向的是孩子节点，thread表示指向的是前驱或后继
typedef enum{link,thread} Tag;  

//二叉线索树结构
struct biThrNode
{
	int value;      
	Thrnode lchild;
	Thrnode rchild;
	Tag ltag;
	Tag rtag;
};

所以以中序遍历为例，遍历过程就是为这些空指针域设置前驱或后继的过程：

void InThreading(BiThrTree p)
{
    if (p)
    {
        
        InThreading(p->lchild);    

        
        if (!p->lchild)
       {
            
            p->LTag = Thread;      

            
            p->lchild = pre;       
        }

        
        if (!pre->rchild)          
        {

            
            pre->RTag = Thread;    

            
            pre->rchild = p;       
        }

        
        pre = p;                   

        
        InThreading(p->rchild);    

    }

}            

if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值给了pre，所以可以将pre赋值给p->lchild，并修改p->LTag=Thread（也就是定义为1）以完成前驱结点的线索化。

后继就要稍稍麻烦一些。因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是pre->rchild=p，并且设置pre->RTag=Thread，完成后继结点的线索化。

完成前驱和后继的判断后，别忘记将当前的结点p赋值给pre，以便于下一次使用。