数据结构:线索二叉树(Threaded Binary Tree)

我们知道满二叉树只是一种特殊的二叉树,大部分二叉树的结点都是不完全存在左右孩子的,即很多指针域没有被充分地利用。另一方面我们在对一棵二叉树做某种次序遍历的时候,得到一串字符序列,遍历过后,我们可以知道结点之间的前驱后继关系,也就是说,我们可以很清楚地知道任意一个结点,它的前驱和后继是哪一个。可是这是建立在已经遍历过的基础之上的。在二叉链表上,我们只能知道每个结点指向其左右孩子结点的地址,而不知道某个结点的前驱是谁,后继是谁。要想知道,必须遍历一次。以后每次需要知道时,都必须遍历一次。为什么不考虑在创建时就记住这些前驱和后继呢?那将是多大的时间上的节省。

综合刚才两个角度的分析后,我们可以考虑利用那些空地址,存放指向结点在某次遍历次序下的前驱和后继结点的地址。我们把这种指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树(Threaded Binary Tree)。

如图6-10-2,我们把这棵二叉树进行中序遍历后,将所有的空指针域中的rchild,改为指向它的后继结点。

如图6-10-3,我们把这棵二叉树进行中序遍历后,将所有的空指针域中的lchild,改为指向它的前驱结点。

通过图6-10-4(空心箭头实线为前驱,虚线黑箭头为后继),更容易看出,其实线索二叉树,等于是把一棵二叉树转变成了一个双向链表,这样对我们的插入删除结点,查找某个结点都带来了方便。所以我们把对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

为了区分指针域是指向左右孩子还是前驱后继,需要再增加两个标志位ltag和rtag,ltag为0时表示指向左孩子,为1时表示指向前驱,rtag为0时表示指向右孩子,为1时表示指向后继。和双向链表结构一样,可以在二叉树线索链表上添加一个头结点,如图6-10-6所示,这样做的好处是我们既可以从第一个结点H开始顺后继进行遍历(利用1,4两根线),也可以从最后一个结点G开始顺前驱进行遍历(利用2,3两根线),将头结点作为遍历结束的判据。

示例程序如下:(改编自《大话数据结构》)

#include<iostream>
using namespace std;

#define MAXSIZE 50

typedef char ElemType;
typedef enum { Link, Thread } PointerTag;
typedef char String[MAXSIZE + 1]; //以'\0’结尾
String str; /* 用于构造二叉树*/

/* 结点结构 */
typedef struct BThrNode
{
    ElemType data;/* 结点数据 */
    struct BThrNode *LChild;/* 左右孩子指针 */
    struct BThrNode *RChild;
    PointerTag LTag;
    PointerTag RTag;

} BThrNode, *BThrNodePtr;

/* 构造一个字符串 */
bool StrAssign(String Dest, char *ptr)
{
    cout << "Assign Str ..." << endl;
    int i;
    for (i = 0; ptr[i] != '\0' && i < MAXSIZE; i++)
        Dest[i] = ptr[i];
    Dest[i] = '\0';
    return true;
}

bool  CreateBThrTree(BThrNodePtr *Tpp)
{
    ElemType ch;
    static int i = 0;
    if (str[i] != '\0')
        ch = str[i++];
    if (ch == '#')
        *Tpp = NULL;
    else
    {
        *Tpp = (BThrNodePtr)malloc(sizeof(BThrNode));
        if (!*Tpp)
            exit(1);
        (*Tpp)->data = ch;/* 生成根结点 */
        CreateBThrTree(&(*Tpp)->LChild);/* 构造左子树 */
        if ((*Tpp)->LChild)
            (*Tpp)->LTag = Link;
        CreateBThrTree(&(*Tpp)->RChild);/* 构造右子树 */
        if ((*Tpp)->RChild)
            (*Tpp)->RTag = Link;

    }
    return true;

}

BThrNodePtr prev;/* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BThrNodePtr Tp)
{
    if (Tp)
    {
        InThreading(Tp->LChild);/* 在第一次左递归过程中绑定了如图的线条3 */
        if (!Tp->LChild)/* 没有左孩子 */
        {
            Tp->LTag = Thread;/* 前驱线索 */
            Tp->LChild = prev;/* 左孩子指针指向前驱 */
        }
        if (!prev->RChild)/* 前驱没有右孩子 */
        {
            prev->RTag = Thread;/* 后继线索 */
            prev->RChild = Tp;/* 前驱右孩子指针指向后继(当前结点Tp) */
        }

        prev = Tp;
        InThreading(Tp->RChild);/* 递归右子树线索化 */
    }
}
/* 中序遍历二叉树,并将其中序线索化,*Hpp指向头结点 */
bool InOrderThreading(BThrNodePtr *Hpp, BThrNodePtr Tp)
{
    cout << "InOrderThreading ..." << endl;
    *Hpp = (BThrNodePtr)malloc(sizeof(BThrNode));
    if (!(*Hpp))
        exit(1);
    (*Hpp)->LTag = Link;/* 建头结点 */
    (*Hpp)->RTag = Thread;
    (*Hpp)->RChild = (*Hpp);/* 右指针回指 */
    if (!Tp)
        (*Hpp)->LChild = *Hpp;/* 若二叉树空,则左指针回指 */
    else
    {
        (*Hpp)->LChild = Tp; /* 绑定如图的线1 */
        prev = (*Hpp); /* 头结点是第一个走过的点*/
        InThreading(Tp); /* 中序遍历进行中序线索化 */
        prev->RChild = *Hpp; /* 最后一个结点的后继指向头结点,即如图的线4*/
        prev->RTag = Thread;
        (*Hpp)->RChild = prev; /* 头结点的后继指向最后一个结点,即如图的线2*/
    }
}
/* 中序遍历二叉线索树(头结点)的非递归算法 */
bool InOrderTraverse_Thr(BThrNodePtr Hp)
{
    cout << "InOrderTraverse ..." << endl;
    BThrNodePtr Bp;
    Bp = Hp->LChild;/* Bp指向根结点 */
    while (Bp != Hp)
    {
        /* 空树或遍历结束时,Bp== Hp */
        while (Bp->LTag == Link)
            Bp = Bp->LChild;
        /* 访问其左子树为空的结点 */
        cout << Bp->data << ' ';

        while (Bp->RTag == Thread && Bp->RChild != Hp)
        {
            Bp = Bp->RChild;
            cout << Bp->data << ' '; /* 访问后继结点 */
        }

        Bp = Bp->RChild;
    }

    return true;
}

int main(void)
{
    BThrNodePtr Hp, Tp;
    StrAssign(str, "ABDH##I##EJ###CF##G##");
    cout << "输入前序遍历序列 :" << endl;
    cout << str << endl;
    CreateBThrTree(&Tp);
    InOrderThreading(&Hp, Tp);
    InOrderTraverse_Thr(Hp);

    return 0;
}

输出为:

由于线索二叉树充分利用了空指针域的空间,又保证了创建时一次遍历就可以持续受用的前驱后继信息,所以如果所用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱后继,那么采用线索二叉链表的存储结构就是不错的选择。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Kirito的技术分享

Java随机数探秘

一提到 Java 中的随机数,很多人就会想到 Random,当出现生成随机数这样需求时,大多数人都会选择使用 Random 来生成随机数。Random 类是线程...

1395
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

842
来自专栏我是东东强

数据结构之栈与队列(优先队列/堆)

栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

962
来自专栏King_3的技术专栏

leetcode-55-跳跃游戏

1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

381
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(06-10打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

802
来自专栏C/C++基础

统计无符号整数二进制中1的个数(Hamming weight)

之所以来记录这个问题的解法,是因为在在线编程中经常遇到,比如编程之美和京东的校招笔试以及很多其他公司都累此不疲的出这个考题。看似简单的问题,背后却隐藏着很多精妙...

1052
来自专栏趣学算法

数据结构 第12讲 二叉树的层次遍历

二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示:

723
来自专栏牛客网

校招面试手撕算法汇总

所有题目都是从面经中提取而来,持续更新。 本人也是菜鸟一枚,帖子也会相应的发布自己对于题目的解法和看法,但是可能想得不够,也希望大家能够一起讨论,一起进步。 1...

35411
来自专栏程序员的SOD蜜

Why to do,What to do,Where to do 与 Lambda表达式!

最近我做一个“四象限”图表控件,其中有一个比较复杂的“坐标变换”问题,即是如何让一组数据放到有限的一个区间内,例如有一组数据 List[4,5,6,7,8],要...

2139
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

1202

扫码关注云+社区