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

相关文章

来自专栏深度学习思考者

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

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

38310
来自专栏撸码那些事

【图解数据结构】二叉查找树

1222
来自专栏LinkedBear的个人空间

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

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

862
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

2128
来自专栏WindCoder

DateUtil-常用关于date的工具类备份

1261
来自专栏kevindroid

leetcode257 Binary Tree Paths

1535
来自专栏琯琯博客

PHP二叉树(三):红黑树

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

判断二叉树是否为平衡二叉树

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

772
来自专栏编程坑太多

HashMap 源码解析

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

[LeetCode] 113. Path Sum II

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

2217

扫码关注云+社区

领取腾讯云代金券