【考研】数据结构——线索二叉树

本文内容源于对《数据结构（C语言版）》（第2版）、王道讲解学习所得心得、笔记整理和总结。本文针对线索二叉树，在最后的练习中，以举例子说明该排序方法，配以图文，讲解详细（含408真题）。【考研】《数据结构》知识点总结.pdf_考研-其它文档类资源-CSDN下载【2023考研】数据结构常考应用典型例题（含真题）_住在阳光的心里的博客-CSDN博客//二叉树的二又线索存储表示以这种结点结构构成的二叉链表

住在阳光的心里

5476人浏览 · 2022-09-20 17:35:43

住在阳光的心里 · 2022-09-20 17:35:43 发布

CSDN话题挑战赛第2期
参赛话题：学习笔记

前言

本文内容源于对《数据结构（C语言版）》（第2版）、王道讲解学习所得心得、笔记整理和总结。

本文针对线索二叉树，在最后的练习中，以举例子说明该排序方法，配以图文，讲解详细（含408真题）。

可搭配以下链接进行学习：

【考研】《数据结构》知识点总结.pdf_考研-其它文档类资源-CSDN下载

【2023考研】数据结构常考应用典型例题（含真题）_住在阳光的心里的博客-CSDN博客

一、基本概念

1、引入线索二叉树的原因

当二叉树以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到，为此引入线索二叉树来保存这些在动态过程中得到的有关前驱和后继的信息。

虽可在每个结点中增加两个指针域来存放在遍历时得到的有关前驱和后继信息，但这样做使得结构的存储密度大大降低。由于有 n 个结点的二叉链表中必定存在 n + 1个空链域（ 2n 个指针域），因此可以充分利用这些空链域来存放结点的前驱和后继信息。

2、线索二叉树的规定

若结点有左子树，则其 lchild 域指示其左孩子，否则令 lchild 域指示其前驱；

若结点有右子树，则其 rchild 域指示其右孩子，否则令 rchild 域指示其后继。

为了避免混淆，尚需改变结点结构，增加两个标志域，其结点形式如图1所示。

3、二叉树的二叉线索类型定义

//二叉树的二又线索存储表示
typedef struct BiThrNode{
    TElemType data;
    struct BiThrNode *lchild, *rchild;
    int LTag, RTag;
}BiThrNode, *BiThrTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。

加上线索的二叉树称之为线索二叉树(Threaded Binary Tree)。对二又树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

4、中序线索二叉树与对应的中序线索链表

实线：指针（指向左、右子树）

虚线：线索（指向前驱和后继）

为方便，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其 lchild 域的指针指向二又树的根结点，其 rchild 域的指针指向中序遍历时访问的最后一个结点；同时，令二叉树中序序列中第一个结点的 lchild 域指针和最后一个结点 rchild 域的指针均指向头结点。

这好比为二又树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。

二、构造线索二叉树

由于线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程，可用递归算法。

对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树，包括先序线索二叉树、中序线索二叉树和后序线索二叉树。

下面重点介绍中序线索化的算法。

为了记下遍历过程中访问结点的先后关系，附设一个指针 pre 始终指向刚刚访问过的结点，而指针
p 指向当前访问的结点，由此记录下遍历过程中访问结点的先后关系。

1、算法1：以结点 p 为根的子树中序线索化的过程

（1）算法步骤

① 如果 p 非空，左子树递归线索化。
② 如果 p 的左孩子为空，则给 p 加上左线索，将其 LTag 置为1，让 p 的左孩子指针指向前驱；否则将 p 的 LTag 置为0。
③ 如果 pre 的右孩子为空，则给 pre 加上右线索，将其 RTag 置为1，让 pre 的右孩子指针为 p (后继)；否则将 pre 的 RTag 置为 0。
④ 将 pre 指向刚访问过的结点 p，即 pre = p。
⑤ 右子树递归线索化。

（2）算法描述

// pre 是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
vold InThreading(BiThrTree p){
    if(p){
        InThreading(p->lchild);       //左子树递归线索化

        if(!p-> lchild){   // p 的左孩子为空
            p->LTag = l;    //给p加上左线索
            P->lchild = pre;     //p的左孩子指针指向 pre (前驱)
        }
        else{
            p->LTag = 0;
        }

        if(pre->rchild){     //pre 的右孩子为空
            pre->RTag = l；    //给 pre 加上右线索
            pre->rchild = p;    //pre的右孩子指针指向p (后继)
        }
        else{
            p->RTag = 0;
        }

        pre = p;     //保持 pre 指向 p 的前驱
        InThreading(p->rchlld);    //右子树递归线索化
    }
}

2、算法2：带头结点的二叉树中序线索化

通过调用算法1来完成整个二叉树的中序线索化。算法描述如下：

//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
void InorderThreading(BiThrTree &Thrt, BiThrTree T){
    Thrt-new BiThrNode;      //建头结点

    Thrt->LTag = 0;         //头结点有左孩子，若树非空，则其左孩子为树根
    Thrt->RTag = l;          //头结点的右孩子指针为右线索
    Thrt->rchild = Thrt;         //初始化时右指针指向自己

    if(!T){
        Thrt->lchild = Thrt;        //若树为空，则左指针也指向自己
    }
    else{
        Thrt->lchild = T; 
        pre = Thrt;        //头结点的左孩子指向根，pre初值指向头结点

        InThreading(T);      //调用算法1，对以T为根的二又树进行中序线索化
        pre->rchild = Thrt;        //算法1结束后，pre为最右结点，pre的右线索指向头结点
        pre->RTag = l; 
        Thrt->rchild = pre;    //头结点的右线过指向 pre
    }
}

三、遍历中序线索二叉树

① 查找 p 指针所指结点的前驱：
● 若 p->LTag 为1，则 p 的左链指示其前驱;
● 若 p->LTag 为0，则说明 p 有左子树，结点的前驱是遍历左子树时最后访问的一个结点 ( 左子树中最右下的结点 ) 。

② 查找 p 指针所指结点的后继：
● 若 p->RTag 为1，则 p 的右链指示其后继，以图 2 所示的中序线索树为例来看，结点 b 的后继为结点*;
● 若 p->RTag 为 0，则说明 p 有右子树。根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。例如，在找结点 * 的后继时，首先沿右指针找到其右子树的根结点-，然后顺其左指针往下直至其左标志为 1 的结点，即为结点 * 的后继，在图中是结点 c 。

1、算法步骤

① 指针 p 指向根结点。
② p 为非空树或遍历未结束时，循环执行以下操作：
        ● 沿左孩子向下，到达最左下结点 *p，它是中序的第一个结点；
        ● 访问 *p；
        ● 沿右线索反复查找当前结点 *p 的后继结点并访问它，直至右线索为 0 或者遍历结束；
        ● 转向 p 的右子树。

2、算法描述

// T 指向头结点，头结点的左链 lchild 指向根结点，可参见线索化算法2。
// 中序遍历二又线索树 T 的非递归算法，对每个数据元素直接输出
void InOrderTraverse Thr (BiThrTree T)
{
    p = T->lchild;    //p指向根结点
    while(p != T){    //空树或遍历结束时，p--T
        while(p->LTag == 0) {
            p = p->lchild;     //沿左孩子向下
        }
        cout << p->data;     //访向其左子树为空的结点

        while (p->RTag == 1 && p->rchild != T){   //沿右线索访问后继结点
            p = p->rchild;
            cout << p->data;
        }
        p = p->rchild;       //转向 p 的右子树
    }
}