当前位置: 首页 > article >正文

二叉树的基本概念(下)

文章目录

  • 🍊自我介绍
  • 🍊二叉树的分类
    • 满二叉树
    • 完全二叉树
  • 🍊二叉树的存储
    • 顺序存储[完全二叉树]
    • 链式存储


你的点赞评论就是对博主最大的鼓励
当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~


🍊自我介绍

  Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入式方面的内容。


🍊二叉树的分类

满二叉树

在一颗二叉树中,除了最后一层之外,如果所有的分支节点都存在左子树和右子树,并且所有的叶子节点都在同一层上,这样的二叉树,我们称之为满二叉树。
在这里插入图片描述
满二叉树的特点:
1.叶子节点只会出现在最下面一层。
2.非叶子节点的节点,拥有子树的个数一定为2。
3.在同样深度的二叉树中,满二叉树的节点个数最多。

完全二叉树

对于一颗具有n个节点的二叉树按照层数进行编号,如果编号为i(1 <= i <= n)的结点与同样深度为满二叉树节点编号为i的结点在二叉树中的位置完全相同,则这棵树,我们称之为完全二叉树。

注意:结点编号规则从上到下,从左到右.
在这里插入图片描述
我们来分析一下完全二叉树的相关规律:

节点左孩子右孩子
123
245
367
489
510

根据表格的值我们思考一下,如果定义节点为i ,那么左孩子和右孩子存在的条件是什么?

重点:

对于完全二叉树,共有n个节点,编号为i(i >= 1)的节点的特点:
左孩子存在的条件:2 * i <= n, 编号为2 * i
右孩子存在的条件: 2 * i + 1 <= n,编号为2 * i + 1

🍊二叉树的存储

顺序存储[完全二叉树]

顺序存储的话,若不是完全二叉树存储就没有意义。
假设下面有一棵树,我们如何把它存到数组中的?
在这里插入图片描述
思路:先把它转换成完全二叉树,然后再编号
在这里插入图片描述

因此,<>我们顺序存储规定无论是何种树,我们都会转换成完全二叉树。然后一层一层的从左给我们的二叉树进行编号,然后存储在数组中。及如下图。
在这里插入图片描述
我们发现这样顺序存储树的方式非常的浪费空间,那么我们该如何解决这个问题呢?这个需要运用链式存储方式进行存储。

链式存储

链式存储:定义结点保存左孩子和右孩子的地址

在这里插入图片描述
链式存储定义代码:

typedef char data_t

typedef struct bnode
{
	data_t data;
	struct bnode *lchild;
	struct bnode *rchild;
}bitree_t;

http://www.kler.cn/a/319980.html

相关文章:

  • 复用类(4):final关键字、初始化与类的加载
  • 网络设备安全保证计划 (NESAS) - 供应商视角 笔记
  • leetcode 面试经典 150 题:汇总区间
  • 一文掌握Docker
  • MySQL-索引
  • Rust 强制类型转换和动态指针类型的转换
  • 技术成神之路:设计模式(十五)中介者模式
  • VulnHub-Bilu_b0x靶机笔记
  • 大数据新视界 --大数据大厂之HBase 在大数据存储中的应用与表结构设计
  • K8S精进之路-控制器StatefulSet有状态控制 -(2)
  • qmt量化交易策略小白学习笔记第67期【qmt编程之获取ETF申赎清单】
  • 封装一个vue3的文件上传组件(拖拽或点击选择文件)
  • C++ | Leetcode C++题解之第437题路径总和III
  • react + antDesign封装图片预览组件(支持多张图片)
  • 服务端的 Session 详解
  • 无人机避障——4D 毫米波雷达 SLAM篇(一)
  • 3D扫描建模能代替传统建模吗?
  • 大觅网之业务部署(Business deployment of Da Mi Network)
  • Python发送邮件教程:如何实现自动化发信?
  • (学习记录)使用HAL库 STM32CubeMX——spi(DMA)配置OLED
  • 抽象类、比较器和接口
  • 大象机器人资料整理
  • /etc/init.d/mysql
  • 将上一篇的feign接口抽取到公共api模块(包含feign接口示例)
  • 如何在 macOS 上恢复未保存的 Excel 文件 – 文件恢复的最佳方法
  • 运维工程师面试整理-安全常见安全漏洞及修复