数据结构之线索二叉树详细解释

这篇具有很好参考价值的文章主要介绍了数据结构之线索二叉树详细解释。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.1 线索二叉树的原理

我们现在倡导节约型社会,一切都应该以节约为本。但当我们创建二叉树时我们会发现其中一共有两个指针域,有的指针域指向的结构为空,这也就浪费了很多空间。所以为了不去浪费这些空间我们采取了一个措施。就是利用那些空地址,存放指向结点在某种遍历次序之下 的前驱和后继结点的地址。就好像GPS导航仪一样,它可以告诉我们下一站是哪里,我们是从那里来的。我们把这种指向前驱和后继的指针成为线索,加上线索的二叉链表称为线索链表,相应的二叉树就成为线索二叉树。

我们将对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化 。

下图是线索化结束的图:

数据结构之线索二叉树详细解释

这里存在一个问题,我们怎么 知道某一个结点的lchild是指向它的左孩子还是它的前驱呢?rchild是指向其右孩子还是指向后继结点呢?可以在结构体中多两个变量用来去判断是指向前驱后继还是左孩子右孩子。

1.2 线索二叉树结构的实现

二叉树结构体线索存储结构如下:

struct Tree
{
    char name[28];        //需要存储的数据 
    int num;
    int L;        //左右的标志
    int R;
    struct Tree *lchild,*rchild;    //左右孩子的指针
};

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树的时候才能得到,所以线索化的过程就是在遍历的过程中修改空指针的过程。

中序遍历线索化的递归函数如下:

struct Tree *pre = NULL;    //全局变量 

void Inthreading(struct  Tree  *p)
{
    Inthreading(p->lchild);    //递归左子树线索化

    if(!p->lchild)            //没有左孩子
    {
        p->L = 1;
        p->lchild = pre;    //本来指向左孩子的指针指向前驱结点 
    }

    if(!pre->rchild)        //没有右孩子
    {
        pre->R = 1;
        pre->rchild = p;    //本来指向右孩子的指针指向后继结点 
    }

    pre = p;    //保持pre指向p的前驱

    Inthreading(p->rchild);    //递归右子树线索化
}

你会发现,代码中除了if语句以外,和二叉树中序遍历的递归代码几乎一模一样。只不过是将打印的代码改为了线索化功能的代码。

if(!p->lchild)表示如果某结点的左指针域为空,因为其前驱结点刚刚访问过(如果是第一个元素则前驱指向NULL),赋值给了 pre,所以可以将pre赋值给p->lchild,并修改p->L为1,以完成前驱结点的线索化。

后继结点的线索化就会麻烦一点。因为此时p结点的后继结点还没有被访问到,因此只能对它的前驱结点pre的右指针rchild做判断,if(!pre->rchild)表示如果为空,则p就为pre的后继结点,于是就让pre->rchild = p,并设置pre->R为1,以完成后继结点的线索化。

结果如下图所示:

数据结构之线索二叉树详细解释

结构体中有一个标志(L和R)该指针域是否指向其左孩子还是右孩子的结点,若指向左孩子或右孩子则该值为0,若指向前驱或后继时则该值为1。 

遍历的代码如下:

void print(struct Tree *T)
{
    struct Tree *p;
    p = T->lchid;    //p指向根结点

    while(p!=T)    //当p是空树,或等于T时结束循环
    {
        while(p->L == 0)
            p = p->lchild;
           cout << name <<" " << num << endl;
        while(p->R == 1 && p->rchild != T)
        {
            p = p->rchild;    //访问后续结点
            cout << name <<" " << num << endl;
        }
        p = p->rchild;
    }
}

大致运行的过程如下:

 数据结构之线索二叉树详细解释

从此段代码也可以看出,它等于是一个链表的扫描,所以时间复杂度是O(n)。

由于它充分利用了空指针域的空间(这等于节省了空间),又保证了创建时的一次遍历就可以 终生享用前驱后继的信息(这意味着节省了时间)。所以在实际问题中,如果所用的二叉树经常要遍历或查找结点时需要某种遍历序列中的前驱后继,那么采用线索二叉链表的存储结构就是非常不错的选择。 

1.3 树、森林与二叉树的转换

首先在介绍树、森林与二叉树转换之前我们先了解一下什么是树和森林吧。

树(tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:(1)有且仅有一个特定的称为根(boot)的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2.....,其中每一个集合本身又是一颗树,并且称为根的树,如下图所示:

数据结构之线索二叉树详细解释

 森林就是树和二叉树的一个集合,下图就是一个森林:

数据结构之线索二叉树详细解释

1.3.1 树转换为二叉树

 树如下图所示:

数据结构之线索二叉树详细解释

将树转换为二叉树的步骤如下。

(1)加线。在所有兄弟节点之间加一条线,如下图所示:(树的话b的结点可以是三个,考虑画图过程本人没画很多 )

数据结构之线索二叉树详细解释

 (2)去线。对树的每个结点,只保留它与第一个孩子结点的连线(即左孩子),删除它与其他孩子结点的连线。如下图所示:(树的话b的结点可以是三个,考虑画图过程本人没画很多 )

数据结构之线索二叉树详细解释

(3)层次调整。以树的根结点为轴心,将整棵树旋转一定的角度,使其结构层次分明。注意第一个孩子是二叉树的左孩子,兄弟转过来的孩子是结点的右孩子,如图所示:

数据结构之线索二叉树详细解释

1.3.2 森林转换为二叉树

森林是由若干颗树组成的,所以完全可以理解为,森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作。如下图:

数据结构之线索二叉树详细解释

 转换步骤如下:

(1) 把每个树转换为二叉树,将根结点的右孩子断开作为下个结点的右孩子。如图所示:

数据结构之线索二叉树详细解释

(2)第一颗二叉树不动,从第二颗二叉树开始,一次把后一颗二叉树的根结点作为前一颗二叉树的根结点的右孩子,用连线连接起来。当所有的二叉树连接起来之后就得到了由森林转换过来的二叉树了。如下图所示:

数据结构之线索二叉树详细解释

 1.3.3  二叉树转换为树

二叉树转换为树就是树转换为二叉树的逆过程,也就是反过来做而已。比如下图的二叉树转换为树 :

数据结构之线索二叉树详细解释

步骤如下:

(1)加线。如果结点的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点....与根部的结点相连接起来。如下图所示:(根据下图将右孩子都与根结点连接起来)

数据结构之线索二叉树详细解释

(2)去线。删除原二叉树中所有的结点与其右孩子结点的连线,如下图所示:

数据结构之线索二叉树详细解释

(3)层次调整。使其结构层次分明即可,如下图所示:

数据结构之线索二叉树详细解释

1.3.4  二叉树转换为森林

判断一颗二叉树能够转换成一颗树还是森林,标准很简单,就是只要看这颗二叉树的根结点有没有右孩子,有右孩子就是森林,没有就是一颗树。

如下图:

 数据结构之线索二叉树详细解释

步骤如下:

(1)从根结点开始,若右孩子存在,则把与右孩子所有的连线删除,如下图所示: 

数据结构之线索二叉树详细解释

(2)再查看分离后的二叉树,若存在右孩子则连线继续删除,删除到没有右孩子的存在,得到分离的二叉树。如下图所示:

数据结构之线索二叉树详细解释

(3)再将每颗分离后的二叉树转换为树即可。如下图所示:

数据结构之线索二叉树详细解释

1.4 树与森林的遍历

树的遍历分为两种方式。

(1)先根遍历树。即先访问树的根结点,然后依次先根遍历根的每颗子树。

(2)后根遍历树。即先依次后根遍历每颗子树,然后再访问根结点。

如下图:

数据结构之线索二叉树详细解释

先根遍历结果是:ABEFCGDHI

后根遍历结果是:EFBGCHIDA

森林的遍历也分为两种方式:

(1)前序遍历:先访问森林中的第一课树的根结点,然后再依次先根遍历根的每颗子树,在依次利用相同的方式遍历除去第一颗树的剩余树构成的森林。

(2)后序遍历:先访问森林中的第一颗树,后根遍历的方式遍历每一颗树,然后在访问根结点即可。

数据结构之线索二叉树详细解释

前序遍历结果是:ABCDEFGHI

后续遍历结果是:BCDAFEHIG

本篇博客的知识点就到这里结束了 ,后面博客再详细写一些程序作为应用介绍,因为放假回家没拿电脑,所以代码就没办法给大家实现了,先看看知识点进行复习吧!!文章来源地址https://www.toymoban.com/news/detail-419072.html

到了这里,关于数据结构之线索二叉树详细解释的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——二叉树线索化遍历(前中后序遍历)

    为什么要转换为线索化         二叉树线索化是一种将普通二叉树转换为具有特殊线索(指向前驱和后继节点)的二叉树的过程。这种线索化的目的是为了提高对二叉树的遍历效率,特别是在不使用递归或栈的情况下进行遍历。         将二叉树线索化的主要目的是为了

    2024年02月09日
    浏览(39)
  • 【数据结构】线索二叉树(适用场景+图文推导过程+C语言代码实现)

    普通二叉树(如下图): 空间浪费 :存在大量“∧”,该空间未利用。 时间效率 :查找一次结点的前驱、后继就需要遍历一次,时间效率低。         在实际问题中,如果所用的 二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表

    2024年02月04日
    浏览(37)
  • 数据结构三叉链表与线索二叉树的思路与实现详解

    ❤️作者主页:微凉秋意 ✅作者简介:后端领域优质创作者🏆,CSDN内容合伙人🏆,阿里云专家博主🏆 我们知道最常见的链式存储二叉树的结构体中有数据域、左孩子指针以及右孩子指针,通过递归来创建二叉树。显而易见的是,想找到二叉树中任意一个结点的 前驱 或 后

    2024年02月02日
    浏览(61)
  • 探索树形数据结构,通识树、森林与二叉树的基础知识(专有名词),进一步利用顺序表和链表表示、遍历和线索树形结构

      结点之间有分支,具有层次关系 树的定义 : 树 (tree)是n(n≥0)个有限集。 若n = 0,则称为空树; 若n 0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树,并称为根的

    2024年02月01日
    浏览(53)
  • 【数据结构】二叉树(详细)

    学习二叉树,首先得了解树,从树的基本概念出发。 树是n个节点的的有限集合,是一种非线性结构。当n=0时称为空树,对于非空树T:(1)只有一个根结点(root);(2)除根节点外的其余结点可分为m个互不相交的有限集T1,T2,……,Tm,其中每个集合本身又是一棵树,称为

    2024年03月10日
    浏览(36)
  • 数据结构详细笔记——二叉树

    二叉树的基本概念 二叉树是n(n=0)个结点的有限集合 ①或者为空的二叉树,即n=0 ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成,左子树和右子树又分别是一颗二叉树 特点: 1、每一个结点至多只有两棵子树 2、左右子树不能颠倒(二叉树是有序树)

    2024年02月06日
    浏览(37)
  • 数据结构之二叉树(详细版)

            二叉树作为数据结构的一种,尤为重要,下面是对二叉树的详细讲解。想要了解二叉树,首先要了解 二叉树的基本概念,以及创建二叉树的结构,再深层点,遍历二叉树的前序中序和后续,其次是层序,后面将会讲解如何计算二叉树的高和叶结点 等等。        

    2024年02月03日
    浏览(46)
  • 数据结构--二叉树遍历(详细过程)

    目录 一、什么是二叉树? 二、二叉树的遍历 1. 先序遍历 2. 中序遍历  3.后序遍历 4. 遍历的推导 三、重要的事情 1. 二叉树:一种树形结构,特点是每个 结点至多只有两颗子树 ,并且子树有左右之分,次序不能颠倒。 特殊形态的二叉树:满二叉树和完全二叉树; 2. 满二叉树

    2024年04月17日
    浏览(38)
  • 二叉树【数据结构】【超详细,一学就会】

    目录 📖1.什么是二叉树? 🌴2.满二叉树和完全二叉树  ⛳2.二叉树的性质 🔥3.二叉树的创建与遍历 3.1 创建二叉树 3.2 前中后序遍历——递归和非递归 🏹4.二叉树的实现 1️⃣获取树中节点的个数 2️⃣获取叶子节点的个数 3️⃣获取第K层节点的个数 4️⃣获取二叉树的高度

    2024年02月05日
    浏览(43)
  • 【数据结构】—搜索二叉树(C++实现,超详细!)

                                                           🎬 慕斯主页 : 修仙—别有洞天                                                        ♈️ 今日夜电波 :消えてしまいそうです—真夜中                                              

    2024年02月05日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包