前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【数据结构】树与二叉树(四):满二叉树、完全二叉树及其性质

【数据结构】树与二叉树(四):满二叉树、完全二叉树及其性质

作者头像
Qomolangma
发布于 2024-07-30 02:01:14
发布于 2024-07-30 02:01:14
58301
代码可运行
举报
文章被收录于专栏:深度学习深度学习
运行总次数:1
代码可运行

5.1 树的基本概念

5.1.1 树的定义

  • 一棵树是结点的有限集合T:
    • 若T非空,则:
      • 有一个特别标出的结点,称作该树的,记为root(T);
      • 其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m>0),其中T1, T2, …, Tm又都是树,称作root(T)的子树
    • T 空时为空树,记作root(T)=NULL。

5.1.2 森林的定义

  一个森林是0棵或多棵不相交(非空)树的集合,通常是一个有序的集合。换句话说,森林由多个树组成,这些树之间没有交集,且可以按照一定的次序排列。在森林中,每棵树都是独立的,具有根节点和子树,树与树之间没有直接的连接关系。   森林是树的扩展概念,它是由多个树组成的集合。在计算机科学中,森林也被广泛应用于数据结构和算法设计中,特别是在图论和网络分析等领域。

5.1.3 树的术语

  • 父亲(parent)、儿子(child)、兄弟(sibling)、后裔(descendant)、祖先(ancestor)
  • 度(degree)、叶子节点(leaf node)、分支节点(internal node)
  • 结点的层数
  • 路径、路径长度、结点的深度、树的深度

参照前文:【数据结构】树与二叉树(一):树(森林)的基本概念:父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度

5.1.4 树的表示

5.2 二叉树

5.2.1 二叉树

1. 定义

  二叉树是一种常见的树状数据结构,它由结点的有限集合组成。一个二叉树要么是空集,被称为空二叉树,要么由一个根结点和两棵不相交的子树组成,分别称为左子树右子树。每个结点最多有两个子结点,分别称为左子结点和右子结点。

2. 特点

  二叉树的特点是每个结点最多有两个子结点,并且子结点的位置是有序的,即左子结点在前,右子结点在后。这种有序性使得二叉树在搜索、排序等算法中有广泛的应用。

  • 在二叉树中,根结点是整个树的起始点,通过根结点可以访问到整个树的其他结点。每个结点都可以看作是一个独立的二叉树,它的左子树和右子树也是二叉树。
  • 二叉树可以是空树,也可以是只有根结点的树,或者是由多个结点组成的树。每个结点可以包含一个数据元素,以及指向左子结点和右子结点的指针。
  • 二叉树的形状可以各不相同,它可以是平衡的或者不平衡的,具体取决于结点的分布情况。在二叉树中,每个结点的左子树和右子树都是二叉树,因此可以通过递归的方式来处理二叉树的操作。
3. 性质
引理5.1:二叉树中层数为i的结点至多有
2i

个,其中

i0

引理5.2:高度为k的二叉树中至多有
2k+11

个结点,其中

k0

引理5.3:设T是由n个结点构成的二叉树,其中叶结点个数为
n0

,度数为2的结点个数为

n2

,则有

n0=n2+1

详细证明过程见前文:【数据结构】树与二叉树(三):二叉树的定义、特点、性质及相关证明

4. 满二叉树
定义

  定义5.3:一棵非空高度为

k(k0)

满二叉树(perfect binary tree),是有

2k+11

个结点的二叉树。

特点

  满二叉树是一种特殊类型的二叉树,具有以下特点:

  1. 叶结点都在第
k

层上:满二叉树的高度为

k

,即最深层的层数为

k

。所有的叶结点都位于最深层,也就是第

k

层。

  1. 每个分支结点都有两个子结点:满二叉树中的每个非叶结点都有两个子结点。也就是说,每个结点要么是叶结点,要么有两个子结点。
  2. 叶结点的个数等于非叶结点个数加1:满二叉树中的叶结点个数(记为
n0

)与非叶结点个数(记为

n1

)之间满足关系

n0=n1+1

。也就是说,叶结点的个数比非叶结点的个数多1。

  根据定义5.3,一棵非空高度为

k

的满二叉树具有

2k+11

个结点。这个结论可以通过归纳法证明。当

k=0

时,满二叉树只有一个结点,符合条件。假设对于某个正整数

k

,高度为

k

的满二叉树有

2k1

个结点。那么对于高度为

k+1

的满二叉树,根结点有两个子结点,每个子结点都是高度为

k

的满二叉树。根据归纳假设,每个子树都有

2k1

个结点,所以总共有

2(2k1)+1=2k+11

个结点。因此,高度为

k+1

的满二叉树有

2k+11

个结点。(引理5.2)   可按层次顺序(即按从第0层到第k层,每层由左向右的次序)将一棵满二叉树的所有结点用自然数从1开始编号。例如:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
        1
       / \
      2   3
     / \ / \
    4  5 6  7
   /\ /\ /\ /\
  8 9 A B C D E

  根据上述满二叉树的编号规律,节点的编号如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
0层:11层:2, 32层:4, 5, 6, 73层:8, 9, A, B, C, D, E

  这里使用了十六进制数字A到E来表示编号大于9的节点。这样,高度为3的满二叉树的所有节点共有

241=15

个节点,按照层次顺序从1到15进行编号。

5. 完全二叉树
定义

  定义5.4:一棵包含

n

个节点、高度为

k

的二叉树

T

,当按层次顺序编号

T

的所有节点,对应于一棵高度为

k

的满二叉树中编号由1至

n

的那些节点时,

T

被称为完全二叉树(complete binary tree)

  换句话说,完全二叉树是按照层次顺序从左到右依次填满节点的二叉树,除了最后一层可能不满外,其他层都必须是满的。在完全二叉树中,节点编号与高度为

k

的满二叉树中的节点编号一一对应。

下面是一个例子来说明完全二叉树的概念:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
        1
       / \
      2   3
     / \  /
    4  5 6

  在上面的例子中,这棵二叉树有6个节点,高度为2。按照层次顺序编号,节点的编号与高度为2的满二叉树中的节点编号一一对应。完全二叉树在树的存储和遍历等操作中具有一些特殊的性质,因此在算法和数据结构中经常被使用。

特点
  • 树中只有最下面两层节点的度可以小于2
    • 这意味着在完全二叉树中,除了最后一层和倒数第二层的节点可以是度小于2的节点(即叶节点或只有一个子节点),其他层的节点都必须是度为2的节点(具有两个子节点)。
  • 树中最下面一层的节点都集中在该层最左边的若干位置上(满二叉树意义上)
    • 在完全二叉树中,最后一层的节点从左到右依次排列,不会有空缺。
  • 树中叶节点只能在层数最大的两层上出现,即存在一个非负整数
k

使得树中每个叶节点或在第

k

层或第

k+1

层上

  • 这意味着在完全二叉树中,叶节点只能出现在最底层和倒数第二层上。其他层不会有叶节点。

  • 对树中所有节点,按层次顺序,用自然数从1开始编号,仅编号最大的非叶节点可以没有右儿子,其余非叶节点都有两个儿子节点
    • 在完全二叉树中,除了编号最大的非叶节点可能只有一个子节点(左子节点),其他非叶节点都必须有两个子节点(左子节点和右子节点)。
  • 树中所有节点对应于高度为
k

的满二叉树中编号由1至

n

的那些节点:

  • 这是完全二叉树的定义,完全二叉树的节点编号与高度为
k

的满二叉树中的节点编号一一对应。

  这些特点描述了完全二叉树的一些重要性质和规律。完全二叉树在算法和数据结构中经常被使用,因为它的结构相对简单,可以方便地进行存储和遍历等操作。

引理5.4

  将一棵有

n

个节点的完全二叉树按层次顺序用自然数从1开始编号时,节点编号

i

的结点满足的性质:

① 若

i1

,则编号为

i

的结点的父节点的编号为

i/2

。即除了根节点(编号为1)之外,其他节点的父节点的编号可以通过将节点编号除以2并向下取整得到。

② 若

2in

,则编号为

i

的结点的左子节点的编号为

2i

。这意味着如果节点编号的两倍小于等于总节点数

n

,则该节点有左子节点,且左子节点的编号为节点编号的两倍。

③ 若

2i+1n

,则编号为

i

的结点的右子节点的编号为

2i+1

。这意味着如果节点编号的两倍加一小于等于总节点数

n

,则该节点有右子节点,且右子节点的编号为节点编号的两倍加一。

  这些性质描述了完全二叉树中节点编号与父节点、左子节点和右子节点编号之间的关系。通过这些性质,可以方便地在完全二叉树中定位和访问特定节点的父节点、左子节点和右子节点。

  证明完全二叉树性质②的正确性可以通过归纳法进行:

  • 首先,当
i=1

时,如果

n2

,则左儿子的编号显然为2。这是基本情况。

  • 假设对于所有
1ji

,且

2in

,节点

j

的左儿子的编号为

2j

。现在要证明节点

j=i+1

的左儿子的编号为

2(i+1)

  • 根据完全二叉树的性质,如果
2(i+1)n

,则节点

i+1

有左儿子。根据层次顺序的编号规则,节点

i+1

的左儿子之前的两个节点就是节点

i

的左儿子和右儿子。根据归纳假设,节点

i

的左儿子编号为

2i

,因此节点

i

的右儿子编号为

2i+1

。因此,节点

i+1

的左儿子的编号为

2i+2=2(i+1)

  • 通过归纳法,我们证明了对于所有
1in

,若

2in

,则节点

i

的左儿子的编号为

2i

  由于性质②可以直接推导出性质③,而性质②和③又可以得到性质①,所以这个证明也同时证明了性质③和①。

引理5.5 具有n个结点的完全二叉树的高度是⌊𝑙𝑜𝑔2𝑛⌋ .

证明:   设完全二叉树的高度为

k

。根据定义5.4,完全二叉树的结点个数介于高度为

k

k1

的满二叉树的结点数之间,即有

2k1<n2k+11

从而,我们可以得到

2kn2k+11

,即

klog2n<k+1

由于高度

k

为整数,所以我们可以得到

k=log2n

因此,具有

n

个结点的完全二叉树的高度是

log2n

思考:完全二叉树和满二叉树是什么关系?
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-11-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
数据结构二叉树知识点总结
术语  1. 节点的度:一个节点含有的子树的个数称为该节点的度; 2. 叶节点或终端节点:度为零的节点;  3. 非终端节点或分支节点:度不为零的节点;  4. 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;  5. 兄弟节点:具有相同父节点的节点互称为兄弟节点;  6. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;  7. 树的高度或深度:树中节点的最大层次;  8. 堂兄弟节点:父节点在同一层的节点互为堂兄弟;  9. 节点的祖先:从根到该节点所经分支
10JQKA
2018/05/09
1.5K0
【数据结构】树与二叉树(六):二叉树的链式存储(创建、释放)
参照前文:【数据结构】树与二叉树(一):树(森林)的基本概念:父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度
Qomolangma
2024/07/30
1700
【数据结构】树与二叉树(六):二叉树的链式存储(创建、释放)
二叉树简介
二叉树是由n(n>=0)个节点组成的数据集合。当 n=0 时,二叉树中没有节点,称为空二叉树。当 n=1 时,二叉树只有根节点一个节点。当 n>1 时,二叉树的每个节点都最多只能有两个子树,递归地构建成一棵完整的二叉树。
Python碎片公众号
2021/02/26
4630
二叉树简介
二叉树数据结构:深入了解二叉树的概念、特性与结构
我们转向了更为复杂而有趣的数据结构——二叉树。本文将引领我们进入二叉树的世界,从最基本的概念和结构开始,逐步深入了解二叉树的顺序结构和链式结构
是Nero哦
2024/01/18
6600
二叉树数据结构:深入了解二叉树的概念、特性与结构
我的软考之路(四)——数据结构与算法(2)之树与二叉树
上篇博文主要介绍的是数据结构的线性结构,我们这篇博文介绍非线性结构—树与二叉树,我先介绍树的一些基本概念,树的遍历,再介绍二叉树相关概念和特性,以及二叉树的遍历,最后再树与二叉树的对比,总结。
程序猿小亮
2021/01/29
4310
【数据结构与算法】详解二叉树 上:理论篇——二叉树的基本概念与性质
二叉树的顺序存储结构,又称为数组表示法,是用一组地址连续的存储单元依次存储二叉树中的节点元素。在顺序存储结构中,通常按照二叉树节点自上向下、自左向右的顺序存储。以下是关于二叉树顺序存储结构的详细解释:
倔强的石头
2024/12/06
3190
【数据结构与算法】详解二叉树 上:理论篇——二叉树的基本概念与性质
二叉树:数据结构的分形之美
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把他叫做树是因为它看起来像一棵倒挂的树,也就说它的根朝上,而叶朝下的。它具有以下的特点:
用户11070251
2024/05/04
1500
二叉树:数据结构的分形之美
数据结构——二叉树
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
Eternity._
2024/06/14
1060
数据结构——二叉树
【数据结构】树与二叉树(五):二叉树的顺序存储(初始化,插入结点,获取父节点、左右子节点等)
  一个森林是0棵或多棵不相交(非空)树的集合,通常是一个有序的集合。换句话说,森林由多个树组成,这些树之间没有交集,且可以按照一定的次序排列。在森林中,每棵树都是独立的,具有根节点和子树,树与树之间没有直接的连接关系。   森林是树的扩展概念,它是由多个树组成的集合。在计算机科学中,森林也被广泛应用于数据结构和算法设计中,特别是在图论和网络分析等领域。
Qomolangma
2024/07/30
3240
【数据结构】树与二叉树(五):二叉树的顺序存储(初始化,插入结点,获取父节点、左右子节点等)
【数据结构】树与二叉树
https://cloud.tencent.com/developer/article/2466159?shareByChannel=link
池央
2024/11/28
1080
【数据结构】树与二叉树
二叉树的性质
节点的度:一个节点含有的子树的个数称为该节点的度 树的度:一棵树中,最大的节点的度称为树的度 叶子节点或终端节点:度为0的节点称为叶节点 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点 根结点:一棵树中,没有双亲结点的结点 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推 树的高度或深度:树中节点的最大层次
VIBE
2022/12/02
4730
[数据结构]二叉树概念
树是一种非线性的数据结构,它是由n(n>=0)个有限节点组成一个具有有限关系的集合。把它叫做树,是因为它看起来像一颗倒挂的树,也就是它是根朝上,而叶朝下的。
IT编程爱好者
2023/04/12
2870
[数据结构]二叉树概念
数据结构之树
树(Tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的圣诞树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
我是攻城师
2018/11/08
8580
【数据结构】初识二叉树
我们在数前面已经学了许多数据结构,顺序表,链表,栈,队列。但是他们都有一个特点那就是,他们通常存储具有线性关系的数据,而在实际应用中许多逻辑结构并不是简单线性结构,常常存在着一对多,甚至多对多的情况。如:企业里的职级关系。族谱……
薄荷冰
2024/01/22
1190
【数据结构】初识二叉树
【愚公系列】软考中级-软件设计师 017-数据结构(树和二叉树概念)
数据结构中的树是一种非线性的数据结构,它由一组节点和连接这些节点的边组成。树的节点之间的关系是一种层次关系,其中一个节点称为根节点,其他节点可以是它的子节点或后代节点。树的结构使得在树中进行快速的搜索、插入、删除操作成为可能。
愚公搬代码
2024/01/29
3150
【数据结构】二叉树
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
xxxflower
2023/04/16
2690
【数据结构】二叉树
二叉树的一些性质图解
把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点: (01) 每个节点有零个或多个子节点; (02) 没有父节点的节点称为根节点; (03) 每一个非根节点有且只有一个父节点; (04) 除了根节点外,每个子节点可以分为多个不相交的子树。
全栈程序员站长
2022/08/31
9240
期末复习之数据结构 第6章 树和二叉树
答:最快方法:用叶子数=[n/2]=350 5. 设一棵完全二叉树具有1000个结点,则此完全二叉树有 500 个叶子结点,有 499 个度为2的结点,有 1 个结点只有非空左子树,有 0 个结点只有非空右子树。 答:最快方法:用叶子数=[n/2]=500 ,n2=n0-1=499。 另外,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0. 6. 一棵含有n个结点的k叉树,可能达到的最大深度为 n ,最小深度为 2 。 答:当k=1(单叉树)时应该最深,深度=n(层);当k=n-1(n-1叉树)时应该最浅,深度=2(层),但不包括n=0或1时的特例情况。教材答案是“完全k叉树”,未定量。) 7. 二叉树的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按N L R次序),后序法(即按 L R N 次序)和中序法(也称对称序法,即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是 F E G H D C B 。 8.中序遍历的递归算法平均空间复杂度为 O(n) 。 答:即递归最大嵌套层数,即栈的占用单元数。精确值应为树的深度k+1,包括叶子的空域也递归了一次。 9. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是 33 。 三、单项选择题 ( C )1. 不含任何结点的空树 。 (A)是一棵树; (B)是一棵二叉树; (C)是一棵树也是一棵二叉树; (D)既不是树也不是二叉树 答:以前的标答是B,因为那时树的定义是n≥1 ( C )2.二叉树是非线性数据结构,所以 。 (A)它不能用顺序存储结构存储; (B)它不能用链式存储结构存储; (C)顺序存储结构和链式存储结构都能存储; (D)顺序存储结构和链式存储结构都不能使用 ( C )3. 〖01年计算机研题〗 具有n(n>0)个结点的完全二叉树的深度为 。 (A) élog2(n)ù (B) ë log2(n)û (C) ë log2(n) û+1 (D) élog2(n)+1ù 注1:éx ù表示不小于x的最小整数;ë xû表示不大于x的最大整数,它们与[ ]含义不同! 注2:选(A)是错误的。例如当n为2的整数幂时就会少算一层。似乎ë log2(n) +1û是对的? ( A )4.把一棵树转换为二叉树后,这棵二叉树的形态是 。 (A)唯一的 (B)有多种 (C)有多种,但根结点都没有左孩子 (D)有多种,但根结点都没有右孩子 5. 从供选择的答案中,选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏内。 树是结点的有限集合,它A 根结点,记为T。其余的结点分成为m(m≥0)个 B 的集合T1,T2,…,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。一个结点的子结点个数为该结点的 C 。 供选择的答案 A: ①有0个或1个 ②有0个或多个 ③有且只有1个 ④有1个或1个以上 B: ①互不相交 ② 允许相交 ③ 允许叶结点相交 ④ 允许树枝结点相交 C: ①权 ② 维数 ③ 次数(或度) ④ 序 答案:ABC=1,1,3 6. 从供选择的答案中,选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏内。 二叉树 A 。在完全的二叉树中,若一个结点没有 B ,则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里,一个结点N的左子女是N在原树里对应结点的 C ,而N的右子女是它在原树里对应结点的 D 。 供选择的答案 A: ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点的树形结构 B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟 C~D: ①最左子结点 ② 最右子结点 ③ 最邻近的右兄弟 ④ 最邻近的左兄弟 ⑤ 最左的兄弟 ⑥ 最右的兄弟 答案:A= B= C= D= 答案:ABCDE=2,1,1,3 四
henu_Newxc03
2021/12/28
6790
期末复习之数据结构 第6章 树和二叉树
【数据结构】树和二叉树详解
在前面我们一起了解的数据结构有顺序表、链表、栈和队列,这次要介绍的是树 与它们相同的是,树也是常见的数据结构。而与它们又不同的是,树是非线性结构。之前我们了解的都是线性的。 这次一起来看一个非线性的结构–树。
zxctscl
2024/01/23
1710
【数据结构】树和二叉树详解
数据结构——lesson6二叉树基础
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
大耳朵土土垚
2024/03/13
980
数据结构——lesson6二叉树基础
推荐阅读
相关推荐
数据结构二叉树知识点总结
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档