线索化二叉树的遍历

二叉树线索化其实质是将二叉树的操作线性化，线索化的二叉树相当于一个双向链表，有指向前驱的指针和指向后继的指针，区别在于转化为双向链表时需要对树中的头结点和尾结点作一些处理：在二叉线索树链表上添加一个头结点，令头结点的lchild指向二叉树的根结点，rchild指向中序遍历访问的最后一个结点；而令中序遍历输出的第一个结点的lchild指针和最后一个结点的rchild指针指向头结点，如图1所示。

图1 增加头结点的线索二叉树

这样就使线索二叉树成为了一个封闭的双向链表，既可以从第一个结点起沿后继进行遍历，也可以从最后一个结点起沿前驱进行遍历。

前面学习了二叉树的线索化，那么，增加一个头结点，生成一个带有头结点的线索二叉树也比较容易，我们可以利用6.8.2节已经实现的InThreading ()函数来实现增加头结点的二叉树的线索化，代码实现如下所示：

//中序线索化，增加头结点
BiThrNode* InOrderThreading(BiThrTree T)
{
    BiThrNode *Thrt = NULL;

    Thrt = (BiThrNode *)malloc(sizeof(BiThrNode)); //建头结点 
    if (Thrt == NULL)
    {
        return NULL;
    }
    memset(Thrt, 0, sizeof(BiThrNode));

    Thrt->LTag = 0;                                  //左孩子为孩子指针
    Thrt->RTag = 1;                                 //右孩子为线索化的指针
    Thrt->rchild = Thrt;                             // 右指针回指，步骤②和④
    if (T == NULL) // 若二叉树空,则左指针回指 
    {
        Thrt->lchild = Thrt;                         //步骤①和③
    }
    else
    {
        Thrt->lchild = T;                            //步骤① 
        pre = Thrt;
        InThreading(T);                                // 中序遍历进行中序线索化 
        pre->rchild = Thrt;                            //步骤④
        pre->RTag = 1;                                //最后一个结点线索化 
        Thrt->rchild = pre;                            //步骤②
    }
    return Thrt;
} 

以上代码使用6.8.2节中实现的InThreading ()函数来实现二叉树的线索化，此算法传入一个普通二叉树，返回一个中序线索化的二叉树，它增加了头结点，使线索化的二叉树成为一个封闭的双向链表。图6-69中的①②③④步骤在算法中都有体现。

二叉树线索化后更易于遍历，其遍历方式和遍历双向链表相同，都是通过指针顺序查找下一个结点，其代码实现如下所示：

/* 中序遍历二叉线索树T(头结点)的非递归算法 */
int InOrderTraverse_Thr(BiThrNode* T)
{
    BiThrNode* p;
    p = T->lchild; /* p指向根结点 */
    while (p != T)
    {
        /* 空树或遍历结束时,p==T */
        while (p->LTag == 0)
            p = p->lchild;
        printf("%c ", p->data);

        //如果中序遍历的最后一个结点的 右孩子 == T 说明到最后一个结点 ,遍历结束..
        while (p->RTag == 1 && p->rchild != T)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        p = p->rchild;
    }
    return 0;
}

线索二叉树充分利用了指针域空间，同时保证在创建时一次遍历就可以在以后的使用中方便地获取当前结点的前驱和后继，既节省了空间，又节省了时间。在实际开发应用中，省时省空间的运算往往是最重要的，所以学习线索化二叉树的思想方法其意义要大于写代码。