数据结构:线索二叉树(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 条评论
登录 后参与评论

相关文章

来自专栏一英里广度一英寸深度的学习

三路快排算法-求中位数问题(4)

step1排列数组的时间复杂度是O(N),空间复杂度是O(1) step2 递归调用的复杂度O(logN)

772
来自专栏静默虚空的博客

排序一 冒泡排序

要点 冒泡排序是一种交换排序。 什么是交换排序呢? 交换排序:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。 算法思想 它...

2005
来自专栏前端架构

排序算法图文讲解(php,javascript,java)

大湿们常说,程序=算法+数据结构!砖家门的资料也介绍的非常详细,但是,比如小白我来讲,看的还是昏昏欲睡的感觉。尼玛!就不能简单些吗?我想,各位攻城师和程序猿们也...

832
来自专栏F_Alex

数据结构与算法(七)-树

前言:回顾一下前面学习的内容,大概说了下数据结构中的线性结构,从物理存储方面来说又分为顺序存储和链式存储结构,各自有自己的优缺点,顺序存储结构读快写慢,链式存储...

703
来自专栏racaljk

[数据结构]C语言二叉树的实现

树和图是数据结构中比较麻烦的东西,里面涉及的概念比较多,也最有用, 就比如一般树广泛应用于人工智能的博弈上,而基于图的广度优先和深度优先搜索也广泛应用于人工智能...

802
来自专栏机器之心

资源 | 从算法到数据结构,百道面试问题实现答案集合

选自GitHub 作者:Sherali Obidov 机器之心编译 参与:李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合,里面的 rep...

2486
来自专栏java学习

面试题65(树,图)

面试例题1:前序遍历二叉树值为abcdefg,下面哪个不可能是中序遍历?A.abcdefg B.gfedcba C.bcdefga D.bceadfg 正确解析...

2704
来自专栏熊二哥

深入入门系列--Data Structure--04树

终于有机会重新回头学习一下一直困扰自身多年的数据结构了,赶脚棒棒哒。一直以来,对数据结构的掌握基本局限于线性表,稍微对树有一丢丢了解,而对于图那基本上就是不懂(...

1729
来自专栏算法修养

HDU 5701 中位数计数 百度之星初赛

中位数计数 Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (J...

2476
来自专栏老九学堂

干货| 期末临近快捷C语言复习

? 盼望着盼望着,寒假近了 当然期末考试也就近了 C 语言,晦涩难懂 对于很多同学来说又是初次接触… 期末考试怎么办 不要担心!老九又出新篇章啦 总结了排序...

3607

扫码关注云+社区