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

相关文章

来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

1131
来自专栏null的专栏

数据结构和算法——二叉树

二叉树是使用较多的一种树形结构,如比较经典的二叉排序树,Huffman编码等,都使用到了二叉树的结构,同时,在机器学习算法中,基于树的学习算法中也大量使用到二叉...

2865
来自专栏琯琯博客

PHP二叉树(三):红黑树

2644
来自专栏来自地球男人的部落格

[LeetCode] 113. Path Sum II

【原题】 Given a binary tree and a sum, find all root-to-leaf paths where each pa...

2077
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

2765
来自专栏kevindroid

leetcode257 Binary Tree Paths

1435
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列04:重建二叉树 原

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

662
来自专栏向治洪

数据结构之二叉树

二叉树的定义: 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及...

2035
来自专栏用户画像

4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

762
来自专栏深度学习思考者

二叉树的遍历、查找、插入以及删除

二叉树的主要存储方式是链接存储,标准存储结构也称为二叉链表。 二叉链表结点类的定义 struct Node{ Node *left, *right;...

30110

扫码关注云+社区