双向线索二叉树详解（包含C语言实现代码）

双向线索二叉树的概念

??在遍历使用中序序列创建的线索二叉树时，对于其中的每个结点，即使没有线索的帮助

下，也可以通过中序遍历的规律找到直接前趋和直接后继结点的位置。也就是说，建立的线索二叉链表可以从两个方向对结点进行中序遍历。线索二叉链表可以从第一个结点往后逐个遍历。但是起初由于没有记录中序序列中最后一个结点的位置，所以不能实现从最后一个结点往前逐个遍历。双向线索链表的作用就是可以让线索二叉树从两个方向实现遍历。

双向线索二叉树的实现过程

??在线索二叉树的基础上，额外添加一个结点。此结点的作用类似于链表中的头指针，数据域不起作用，只利用两个指针域（由于都是指针，标志域都为0 ）。左指针域指向二叉树的树根，确保可以正方向对二叉树进行遍历；同时，右指针指向线索二叉树形成的线性序列中的最后一个结点。

??这样，二叉树中的线索链表就变成了双向线索链表，既可以从第一个结点通过不断地找后继结点进行遍历，也可以从最后一个结点通过不断找前趋结点进行遍历。

代码实现

/**

 * @Description: 建立双向线索链表

 * @Param: BiThrTree *h 结构体指针数组 BiThrTree t 结构体指针

 * @Return: 无

 * @Author: Carlos

 */

void InOrderThread_Head(BiThrTree *h, BiThrTree t)

{

    //初始化头结点

    (*h) = (BiThrTree)malloc(sizeof(BiThrNode));

    if ((*h) == NULL)

    {

        printf("申请内存失败");

        return;

    }

    (*h)->rchild = *h;

    (*h)->Rtag = Link;

    //如果树本身是空树

    if (!t)

    {

        (*h)->lchild = *h;

        (*h)->Ltag = Link;

    }

    else

    {

        //pre 指向头结点

        pre = *h;        

        //头结点左孩子设为树根结点 

        (*h)->lchild = t; 

        (*h)->Ltag = Link;

        //线索化二叉树，pre 结点作为全局变量，线索化结束后，pre 结点指向中序序列中最后一个结点

        InThreading(t); 

        //链接最后一个节点（最右下角G节点）和头结点

        pre->rchild = *h;

        pre->Rtag = Thread;

        //将头结点的右指针指向中序序列最后一个节点

        (*h)->rchild = pre;

    }

}

双向线索二叉树的遍历

??双向线索二叉树遍历时，如果正向遍历，就从树的根结点开始。整个遍历过程结束的标志是：当从头结点出发，遍历回头结点时，表示遍历结束。

/**

 * @Description: 中序正向遍历双向线索二叉树

 * @Param: BiThrTree h 二叉树的结构体指针

 * @Return: 无

 * @Author: Carlos

 */

void InOrderThraverse_Thr(BiThrTree h)

{

    BiThrTree p;

    //p 指向根结点

    p = h->lchild; 

    while (p != h)

    {

        //当ltag = 0 时循环到中序序列的第一个结点。

        while (p->Ltag == Link) 

        {

            p = p->lchild;

        }

        //显示结点数据，可以更改为其他对结点的操作

        printf("%c ", p->data); 

        //如果当前节点经过了线索化，直接利用该节点访问下一节点

        while (p->Rtag == Thread && p->rchild != h)

        {

            p = p->rchild;

            printf("%c ", p->data);

        }

        //如果没有线索化或者跳出循环，说明其含有右子树。p 进入其右子树

        p = p->rchild; 

    }

}

??逆向遍历线索二叉树的过程即从头结点的右指针指向的结点出发，逐个寻找直接前趋结点，结束标志同正向遍历一样：

/**

 * @Description: 中序逆方向遍历线索二叉树 和正向的区别在于 p = p->rchild 。逆向遍历我们要一直访问到右子树的最后一个。

 * @Param: BiThrTree h 二叉树的结构体指针

 * @Return: 无

 * @Author: Carlos

 */

void InOrderThraverse_Thr(BiThrTree h)

{

    BiThrTree p;

    p = h->rchild;

    while (p != h)

    {

        while (p->Rtag == Link)

        {

            p = p->rchild;

        }

        printf("%c", p->data);

        //如果lchild 为线索，直接使用，输出

        while (p->Ltag == Thread && p->lchild != h)

        {

            p = p->lchild;

            printf("%c", p->data);

        }

        p = p->lchild;

    }

}

??完整代码如下

/*

 * @Description: 双向线索二叉树的遍历

 * @Version: V1.0

 * @Autor: Carlos

 * @Date: 2020-06-01 20:46:38

 * @LastEditors: Carlos

 * @LastEditTime: 2020-06-01 21:17:23

 */

#include#include//宏定义，结点中数据域的类型

#define TElemType char 

//枚举，Link 为0，Thread 为1

typedef enum

{

    Link,

    Thread

} PointerTag;

//结点结构构造

typedef struct BiThrNode

{

    //数据域

    TElemType data;    

    //左孩子，右孩子指针域                

    struct BiThrNode *lchild, *rchild; 

    //标志域，枚举类型

    PointerTag Ltag, Rtag;             

} BiThrNode, *BiThrTree;

BiThrTree pre = NULL;

/**

 * @Description: 采用前序初始化二叉树  中序和后序只需改变赋值语句的位置即可

 * @Param: BiThrTree *tree 二叉树的结构体指针数组

 * @Return: 无

 * @Author: Carlos

 */

void CreateTree(BiThrTree *tree)

{

    char data;

    scanf("%c", &data);

    if (data != '#')

    {

        if (!((*tree) = (BiThrNode *)malloc(sizeof(BiThrNode))))

        {

            printf("申请结点空间失败");

            return;

        }

        else

        {

            //采用前序遍历方式初始化二叉树

            (*tree)->data = data;           

            //初始化左子树

            CreateTree(&((*tree)->lchild)); 

            //初始化右子树

            CreateTree(&((*tree)->rchild)); 

        }

    }

    else

    {

        *tree = NULL;

    }

}

/**

 * @Description: 中序对二叉树进行线索化 

 * @Param: BiThrTree p 二叉树的结构体指针

 * @Return: 无

 * @Author: Carlos

 */

void InThreading(BiThrTree p)

{

    //如果当前结点存在

    if (p)

    {

        //递归当前结点的左子树，进行线索化

        InThreading(p->lchild); 

        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点pre

        if (!p->lchild)

        {

            p->Ltag = Thread;

            //pre为头结点，链接中序遍历的第一个节点（最左边的结点）与头结点

            p->lchild = pre;

        }

        //如果pre 没有右孩子，右标志位设为1，右指针域指向当前结点。

        if (pre && !pre->rchild)

        {

            pre->Rtag = Thread;

            pre->rchild = p;

        }

        //pre 指向当前结点

        pre = p;             

        //递归右子树进行线索化   

        InThreading(p->rchild); 

    }

}

/**

 * @Description: 建立双向线索链表

 * @Param: BiThrTree *h 结构体指针数组 BiThrTree t 结构体指针

 * @Return: 无

 * @Author: Carlos

 */

void InOrderThread_Head(BiThrTree *h, BiThrTree t)

{

    //初始化头结点

    (*h) = (BiThrTree)malloc(sizeof(BiThrNode));

    if ((*h) == NULL)

    {

        printf("申请内存失败");

        return;

    }

    (*h)->rchild = *h;

    (*h)->Rtag = Link;

    //如果树本身是空树

    if (!t)

    {

        (*h)->lchild = *h;

        (*h)->Ltag = Link;

    }

    else

    {

        //pre 指向头结点

        pre = *h;        

        //头结点左孩子设为树根结点 

        (*h)->lchild = t; 

        (*h)->Ltag = Link;

        //线索化二叉树，pre 结点作为全局变量，线索化结束后，pre 结点指向中序序列中最后一个结点

        InThreading(t); 

        //链接最后一个节点（最右边下角）和头结点

        pre->rchild = *h;

        pre->Rtag = Thread;

        (*h)->rchild = pre;

    }

}

/**

 * @Description: 中序正向遍历双向线索二叉树

 * @Param: BiThrTree h 二叉树的结构体指针

 * @Return: 无

 * @Author: Carlos

 */

void InOrderThraverse_Thr(BiThrTree h)

{

    BiThrTree p;

    //p 指向根结点

    p = h->lchild; 

    while (p != h)

    {

        //当ltag = 0 时循环到中序序列的第一个结点。

        while (p->Ltag == Link) 

        {

            p = p->lchild;

        }

        //显示结点数据，可以更改为其他对结点的操作

        printf("%c ", p->data); 

        //如果当前节点经过了线索化，直接利用该节点访问下一节点

        while (p->Rtag == Thread && p->rchild != h)

        {

            p = p->rchild;

            printf("%c ", p->data);

        }

        //如果没有线索化或者跳出循环，说明其含有右子树。p 进入其右子树

        p = p->rchild; 

    }

}

/**

 * @Description: 中序逆方向遍历线索二叉树 和正向的区别在于 p = p->rchild 。逆向遍历我们要一直访问到右子树的最后一个。

 * @Param: BiThrTree h 二叉树的结构体指针

 * @Return: 无

 * @Author: Carlos

 */

void InOrderThraverse_Thr(BiThrTree h)

{

    BiThrTree p;

    p = h->rchild;

    while (p != h)

    {

        while (p->Rtag == Link)

        {

            p = p->rchild;

        }

        printf("%c", p->data);

        //如果lchild 为线索，直接使用，输出

        while (p->Ltag == Thread && p->lchild != h)

        {

            p = p->lchild;

            printf("%c", p->data);

        }

        p = p->lchild;

    }

}

int main()

{

    BiThrTree t;

    BiThrTree h;

    printf("输入前序二叉树:\n");

    CreateTree(&t);

    InOrderThread_Head(&h, t);

    printf("输出中序序列:\n");

    InOrderThraverse_Thr(h);

    return 0;

}

总结

??二叉树的线索化就是充分利用了节点的空指针域。所有节点线索化的过程也就是当前节点指针和上一结点指针进行链接的过程，不断递归所有节点。线索化二叉树的访问，以中序遍历为例，首先需要访问到中序遍历的第一个节点，若当前节点进行了线索化，可以直接利用该节点进行下一节点的访问。否则，说明当前节点含有右子树，则进入右子树进行访问。双向线索二叉树的建立，其实就将头结点的左指针和树的根节点链接，头结点的右指针和中序遍历的最后一个节点的链接。这样我们就可以进行双向访问了。当从头结点出发，遍历回头结点时，表示遍历结束。

-----------------------------------