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

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

前言

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

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

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

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

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

目录

前言

一、基本概念

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

2、线索二叉树的规定

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

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

二、构造线索二叉树

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

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

三、遍历中序线索二叉树

1、算法步骤

2、算法描述

3、算法分析

四、习题

---

一、基本概念

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 的右子树
    }
}

3、算法分析

遍历线索二又树的时间复杂度为O(n)，空间复杂度为O(1)，这是因为线索二叉树的遍历不需要使用栈来实现递归操作。
 

四、习题

1、在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序（     B     ）

A. 都不相同                                                                 B. 完全相同               

C. 前序和中序相同，而与后序不同                             D. 后序和中序相同，而与前序不同   

解：在三种遍历方式中，访问左右子树的先后顺序是不变的，只是访问根结点的顺序不同，因此叶子结点的先后顺序完全相同。

2、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（     B     ）

A. 空或只有一个结点                                             B. 高度等于其结点数    

C. 任一结点无左孩子                                             D. 任一结点无右孩子   

解：非空的二叉树的先序序列和后序序列相反，即 “根左右” 与 “左右根” 顺序相反，因此树只有根结点，或根结点只有左子树或右子数，以此类推，其子树具有同样的性质，任意结点只有一个孩子，才能满足题目条件，树形应为一个长链。

3、线索二叉树是一种_____物理______结构。

解：二叉树是一种逻辑结构，但线索二叉树是加上线索后的链表结构，即它是二叉树在计算机内部的一种存储结构，即是一种物理结构。

4、n 个结点的线索二叉树上含有的线索数为_____n + 1______。

解：n 个结点共有链域指针 2n 个，其中，除根结点外，每个结点都被一个指针指向。剩余的链域建立线索，共 2n - (n - 1) = n + 1个线索。

5、一棵左子树为空的二叉树进行先序线索化，其中空的链域个数是_____2______。

 解：对左子树为空的二叉树进行先序线索化，根结点的左子树为空，并且也没有前驱结点（先遍历根结点），先序遍历的最后一个元素为叶结点，左、右子树均为空且有前驱无后继结点，所以线索化后，树中空链域有 2 个。

6、【2010统考真题】下列线索二又树中(用虚线表示线索)符合后序线索树定义的是（  D  ）

解：题中所给二叉树的后序序列为 dbca， 结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b 无左子树，左链域指向其前驱结点 d；结点 c 无左子树，左链域指向其前驱结点 b，无右子树，右链域指向其后继结点 a。正确选项为D。
 

7、二叉树在线索化后，仍不能有效求解的问题是（    D   ）。
A. 先序线索二叉树中求先序后继              B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱              D. 后序线索二叉树中求后序后继

解： 后序线索二叉树不能有效解决求后序后继的问题。如下图所示，结点 E 的右指针指向右孩子，而在后序序列中E的后继结点为 B，在查找 E 的后继时后序线索不能起到任何作用，只能按常规方法来。

8、若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 X 的前驱为(    C    )。
A. X 的双亲                                             B. X 的右子树中最左的结点
C. X 的左子树中最右结点                       D. X 的左子树中最右叶结点

 解：在二叉中序线索树中，某结点若有左孩子，则按照中序 “左根右” 的顺序，该结点的前驱结点为左子树中最右的一个结点(注意，并不一定是最右叶子结点)。

9、（  C  ）的遍历仍需要栈的支持。
A. 前序线索树             B. 中序线索树               C. 后序线索树               D. 所有线索树

解：后序线索树遍历时，最后访问根结点，若从右孩子 x 返回访问父结点，则由于结点 x 的右孩子不一定为空 (右指针无法指向其后继)，因此通过指针可能无法遍历整棵树。

如下图所示，结点中的数字表示遍历的顺序，图(c) 中结点 6 的右指针指向其右孩子 5，而不指向其后序后继结点 7，因此后序遍历还需要栈的支持，而图 (a) 和图 (b) 均可遍历。