【数据结构与算法篇】 二叉树的性质(补充)

简介: 【数据结构与算法篇】 二叉树的性质(补充)

👻内容专栏:《数据结构与算法篇

🐨本文概括: 继上一篇深入浅出_二叉树之后遗漏掉了,再次写一篇二叉树的性质博文,对二叉树进行补充总结。

🐼本文作者:花 碟

🐸发布时间:2023.6.8

二叉树的性质

对于二叉树,有以下几条性质:

  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有 2^(i - 1) 个结点
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是 2^h - 1
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n₀ , 度为2的分支结点个数为 n₂ ,则有 n₀=n₂ +1
  4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log₂(n + 1) . (ps:log₂(n + 1) 是log以2为底,n+1为对数)

🏃‍♂️🏃‍♂️牛刀小试:

  1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
    A. 不存在这样的二叉树
    B. 200
    C. 198
    D. 199
    解释:我们直接套用上面的第3条性质,度为2的分支结点个数为199, 那么度为0的分支结点个数比度为2的分支节点个数多一个,199 + 1 = 200
  2. 下列数据结构中,不适合采用顺序存储结构的是( )
    A. 非完全二叉树
    B. 堆
    C. 队列
    D. 栈
    解释:堆一般为二叉树的顺序存储结构,所以适合,栈遵循后进先出的原则,也适合,对于队列和非完全二叉树来说,队列相对来说,更易于用顺序存储,比如说循环队列,但是非完全二叉树就不适合了,因为可能存在很多空树的情况,导致空间出现大量的浪费,所以不适合。
  3. 在具有 2n 个节点的完全二叉树中,叶子节点个数为( )
    A. n
    B. n+1
    C. n-1
    D. n/2
    解释:对于一个完全二叉树节点个数为2n,设叶子节点的个数为n₀,度为1的节点个数为n₁,度为2的节点个数为n₂,则必有n₀+ n₁ + n₂ = 2n,而完全二叉树度为1的节点只有0个或者1个,这取决于完全二叉树最底层的节点的个数是奇数还是偶数,是奇数,n₁ 就为1;是偶数,n₁就为0。最后根据第3条的性质,代入进去,2n₀ - 1 + n₁ = 2n ,所以这里的n₁ 只能为1个,得到选项的结果,叶子节点个数就是n
  4. 一棵完全二叉树的节点数位为531个,那么这棵树的高度为( )
    A 11
    B 10
    C 8
    D 12
    解释:2¹⁰是1024,2⁹是512, 高度为h的完全二叉树的最大节点数为2h - 1 + 1,高度为9的完全二叉树的最大节点数为 2⁹ - 1 + 1 = 512,高度为10的完全二叉树的最大节点数为 2¹⁰ - 1 + 1 = 1024,题目说是节点数为531个,小于高度为10的最大节点数。符合。
  5. 一个具有767个节点的完全二叉树,其叶子节点个数为()
    A. 383
    B. 384
    C. 385
    D. 386
    解释:这题与第三题类似,对于一个完全二叉树节点个数为767,设叶子节点的个数为n₀,度为1的节点个数为n₁,度为2的节点个数为n₂,则必有n₀+ n₁ + n₂ = 767,最后根据第3条的性质,代入进去,2n₀ - 1 + n₁ = 767,根据选项的结果,n₁为0,即完全二叉树最底层的节点个数为偶数,算得叶子节点个数为384

根据两种遍历方式确定一颗二叉树

  1. 某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为( )
    A. ABDHECFG
    B. ABCDEFGH
    C. HDBEAFCG
    D. HDEBFGCA
    解释:
    我们直接根据层序遍历的序列,把二叉树画出来,前序序列就很直观的写出来了。
  2. 二叉树的先序遍历和中序遍历如下:前序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为()
    A. E
    B. F
    C. G
    D. H
    解释:前序遍历的第一个节点即为根节点。
  3. 设一课二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树前序遍历序列为____。
    A. adbce
    B. decab
    C. debac
    D. abcde
    解释:见下图
    法一:前(or 后)序遍历 确定根,中序遍历确定左右子树的区间。

    法二:第二种是投机取巧的方法,仅限于解题。将后序(or 前序)遍历的序列 放置纵轴,且需要保证根的方向,按根的方向排列。然后将中序遍历的序列放置于横轴,确立两个相同的点的坐标,然后连线。
    ⚠ 注意连线的规则:①左子树的所有节点在父节点的左侧,右子树的所有节点在父节点的右侧。
    ②如果需要代码实现,还是第一种方法的思想适合写递归操作。
  4. 某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出(同一层从左到右)的序列

    A. FEDCBA
    B. CBAFED
    C. DEFCBA
    D. ABCDEF
    解释:如下图
  5. 已知某二叉树的中序遍历序列为JGDHKBAELIMCF,后序遍历序列为JGKHDBLMIEFCA,则其前序遍历序列为( )
    A.ABDGHJKCEFILM
    B.ABDGJHKCEILMF
    C.ABDHKGJCEILMF
    D.ABDGJHKCEIMLF
    解释:
    法一:

    法二:
  6. 已知某二叉树的前序遍历序列为5 7 4 9 6 2 1,中序遍历序列为4 7 5 6 9 1 2,则其后序遍历序列为( )
    A.4 2 5 7 6 9 1
    B.4 2 7 5 6 9 1
    C.4 7 6 1 2 9 5
    D.4 7 2 9 5 6 1
    解释:
    通过前序遍历找到子树的根,在中序遍历中找到根的位置,然后确定根左右子树的区间,即根的左侧为左子树中所有节点,根的右侧为右子树中所有节点。
    故:根为: 5
    5的左子树:4 7 5的右子树: 6 9 1 2
    5的左子树的根为: 7 5的右子树的根为:9
    7的左子树: 4 7的右:空 9的左子树:6 9的右子树:2
    确定树的结构为:

🥰🥰本章节完,后续会补充二叉树进阶内容知识,小伙伴们可以持续关注,若本篇文章对你有帮助的话,可以三连支持博主哦~,另外本篇内容有编写有误的话,可以私聊博主进行纠正!

目录
相关文章
|
1月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
82 4
|
1月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
1月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
58 5
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
132 8
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
45 0
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
32 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
37 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
31 1
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
29 1
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学