树与二叉树(概念篇)
创始人
2024-06-01 11:42:33
0

树与二叉树

  • 1 树的概念
    • 1.1 树的简单概念
    • 1.2 树的概念名词
    • 1.3 树的相关表示
  • 2 二叉树的概念
    • 2.1 二叉树的简单概念
      • 2.1.1 特殊二叉树
    • 2.2 二叉树的性质
    • 2.3 二叉树的存储结构

1 树的概念

1.1 树的简单概念

树是一种非线性的数据结构,它是由n(n>=0)个有限节点组成的一个具有层次关系的集合。把它称作树是因为它看起来就像一棵倒挂的树,也就是说它的根在上,而叶在下。

  • 树有一个特殊的节点,称为根节点,根节点没有前驱节点
  • 除根节点外,其余节点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<=i<=m)又是一棵结构与树类似的子树。这样的每棵子树的根节点有且只有一个前驱,可以有0个或多个后继节点。
  • 由此可见,树是递归定义
    注意:树形结构中,子树之间不能有交集(不能成环),否则就不是树形结构
    在这里插入图片描述
    除了根节点外,每个节点有且只有一个父节点,所以可以得出:一棵N个节点的树有N-1条边

1.2 树的概念名词

在这里插入图片描述

节点的度:一个节点含有的子树的个数称为该节点的度。如图:A节点的度为3。
叶节点或终端节点:度为0的节点称为叶节点。如图:J、F、K、L、H、I都是叶节点。
非终端节点或分支节点:度不为0的节点。
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点。如图:A分别是B、C、D的父节点。
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点。如图:B、C、D都是A的子节点。
兄弟节点:具有相同父节点的节点互称为兄弟节点。
树的度:一棵树中,最大的节点的度称为树的度。
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,依此类推。
树的高度或深度:树中节点的最大层次。如图:树的高度为4。
堂兄弟节点:双亲在同一层的节点互为堂兄弟节点。
节点的祖先:从根到该节点所经分支上的所有节点。如图:A节点是所有节点的祖先。
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如图:所有节点都是A节点的子孙。
森林:由m(m>0)棵互不相交的树组成的集合称为森林。

1.3 树的相关表示

树形结构相对线性结构就比较复杂了,要存储表示起来也就比较麻烦了。既要保存值域,也要保存节点和节点之间的关系。实际中树有很多种表示方式,如:双亲表示法,孩子表示法,孩子双亲表示法以及孩子兄弟表示法等。但最常用的还是孩子兄弟表示法
可将上图中树的结构用孩子兄弟表示法转化,如下图所示:
在这里插入图片描述
孩子兄弟表示法是用于将任意一棵普通的树转化为二叉树的最有效方法,其节点的结构定义大致如下:

typedef int DataType;
struct Node
{struct Node* _pfirstChild; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};

2 二叉树的概念

2.1 二叉树的简单概念

一棵二叉树是节点的一个有限集合,该集合:

  1. 或者为空
  2. 或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成
    在这里插入图片描述
    从上图可以看出:
  1. 二叉树不存在度大于2的节点
    二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

所以可得出,对于任意的二叉树都是由以下几种情况组合构成的:
在这里插入图片描述

2.1.1 特殊二叉树

  1. 满二叉树:一个二叉树,如果每一层的节点数都达到最大值,则这个二叉树就叫做满二叉树。也就是说,如果一棵树的高度为h,且节点总数为2h−12^h-12h−1,则它就是满二叉树。
  2. 完全二叉树:完全二叉树是一种效率很高的数据结构。完全二叉树是由满二叉树引出来的。对于高度为h的,有n个节点的树,当且仅当其每一个节点都与高度为h的满二叉树中编号从1至n的节点都一一对应时,才被称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

在这里插入图片描述

2.2 二叉树的性质

  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2(i−1)2^{(i-1)}2(i−1)个节点
  2. 若规定根节点的层数为1,则高度为h的二叉树的最大节点数是2h−12^h-12h−1。
  3. 对于任意一棵二叉树,如果度为0的叶节点个数是n0n_0n0​,度为2的分支结点个数是n2n_2n2​,则有n0=n2+1n_0=n_2+1n0​=n2​+1。
  4. 若规定根节点的层数是1,则具有n个节点的满二叉树的高度:h=log2(n+1)h=log_2(n+1)h=log2​(n+1)。
  5. 对于具有n个节点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的节点有:

若i>0,i节点位置的双亲序号为:(i-1)/2;若i=0,i为根结点序号,无双亲节点。
若2*i+1=n时无左孩子)
若2*i+2=n时无右孩子)

2.3 二叉树的存储结构

二叉树一般可以使用两种结构进行存储,一种是顺序结构,一种是链式结构。

  1. 顺序结构存储
    顺序结构存储就是使用数组来存储。但数组存储一般只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。实际使用中只有(属于完全二叉树)才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一棵二叉树。
  2. 链式结构存储
    二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示节点间的逻辑关系。通常的方法是链表中的每个节点由三个域组成:数据域和左右指针域。左右指针分别用来存放该节点左孩子和右孩子所在的链节点的地址。链式结构又分为二叉链和三叉链。简单的一般二叉链就够了,更复杂的数据结构如红黑树等会用到三叉链。

相关内容

热门资讯

恋夜视频安卓系统Uc,恋夜视频... 亲爱的读者,你是否曾在深夜时分,被手机屏幕上跳动的视频吸引?今天,就让我带你一探究竟,揭开恋夜视频安...
鸿蒙套娃安卓系统视频,融合与创... 你知道吗?最近科技圈可是炸开了锅,因为华为的新操作系统鸿蒙OS又有了新动作。这不,他们竟然把鸿蒙套娃...
xp系统连接安卓手机问题,实用... 你有没有遇到过这样的情况:你的电脑上还运行着那个经典的XP系统,而你的安卓手机却时不时地想要和你亲密...
压缩安卓系统储存空间,高效管理... 手机里的照片越来越多,游戏也越玩越上瘾,可这安卓系统的储存空间却越来越紧张,是不是感觉像是在挤牙膏?...
安卓手游转苹果系统教程,轻松实... 你是不是也和我一样,手头有一堆安卓手游,突然之间想换换口味,体验一下苹果系统的魅力呢?别急,今天就来...
安卓原生系统锁屏暗,安卓系统锁... 亲爱的手机控们,你是否曾为安卓手机锁屏时的暗模式而感到好奇?那种在夜晚或光线不足的环境中,屏幕自动调...
安卓系统表情包下载地址,安卓系... 你是不是也和我一样,对安卓系统的表情包爱不释手?那些搞笑的、可爱的、甚至是有点小调皮的表情,总能让我...
原生安卓系统声音bug,揭秘那... 你有没有遇到过这种情况?手机里突然传来一阵奇怪的声音,让你瞬间从美梦中惊醒,或者正在专心工作时被打扰...
水果收银机安卓系统,便捷高效的... 你有没有想过,在繁忙的超市里,那些摆满新鲜水果的摊位,背后竟然隐藏着一个小小的科技秘密?没错,就是那...
安卓系统变苹果界面了吗,苹果界... 最近手机界可是炸开了锅,不少安卓用户都在议论纷纷:“安卓系统变苹果界面了吗?”这事儿可真不简单,得好...
miui操作系统与安卓系统吗,... 亲爱的读者,你是否曾在手机上看到过MIUI操作系统和安卓系统这两个名字,好奇它们之间有什么区别?今天...
安卓系统怎么卡道具界面,探究原... 手机用久了,是不是感觉安卓系统越来越卡?尤其是那个道具界面,点开就慢吞吞的,真是让人头疼。别急,今天...
安卓系统红包加速器,畅享无阻新... 你有没有发现,现在用手机抢红包简直是一场速度与激情的较量?别急,别急,让我来给你揭秘一款神器——安卓...
安卓经典版系统更新时间,从首次... 你有没有发现,最近你的安卓手机又悄悄地变了个样?没错,就是那个陪伴我们多年的经典版系统,它又来更新啦...
安卓系统开发要多久,约需1-2... 你有没有想过,自己动手开发一个安卓应用,究竟需要多长时间呢?这可是个让人好奇的问题,毕竟安卓系统开发...
原生安卓系统手机壁纸图片,探索... 亲爱的手机控们,你是否曾为寻找一款独特的壁纸而烦恼?今天,就让我带你走进原生安卓系统手机壁纸的奇幻世...
bmw安卓互联系统,智能驾驶新... 你有没有发现,现在开车已经不仅仅是驾驶那么简单了?一辆好车,还得有个好“大脑”,这样才能让你的驾驶体...
安卓手机升级系统卡吗,安卓手机... 你有没有遇到过这种情况:安卓手机升级系统后,突然感觉手机像蜗牛一样慢吞吞的,心里那个急啊!今天,就让...
无线麦克风安卓系统,轻松实现无... 你有没有想过,在一场热闹的K歌派对或者重要的演讲场合,无线麦克风简直就是救星啊!想象你手握麦克风,自...
怎么重新定制安卓系统,打造专属... 你有没有想过,你的安卓手机其实可以变得独一无二,就像是你自己的小宇宙一样?没错,就是重新定制安卓系统...