【数据结构】二叉树概念 | 满二叉树 | 完全二叉树
二叉树的概念
二叉树在实践中用的很多。
一棵二叉树是结点的一个有限集合,该集合:
- 或者为空;
- 由一个根结点加上两棵别称为左子树和右子树的二叉树组成。
- 二叉树最多两个孩子。

这里注意:二叉树并不是度为2的树。
二叉树的度最大值是2,并不是说它的度一定为2。所以一下这四种情况也均是二叉树:
- 空树
- 只有根节点
- 只有左子树
- 只有右子树
- 左右子树均存在
二叉树不存在度大于2的节点;
二叉树的子树有左右之分,次序是不能颠倒的,因此二叉树是有序树。

二叉树通俗也可以理解为对树进行了“计划生育”。 “计划生育”也就是生两个小孩,但是是每一家来说都是生两个吗?
那么度为2的一定是二叉树吗?
- 度为2一定是二叉树。度为2的话,那么所有节点的最大的度就是2,而二叉树的概念是不存在度大于2的节点。
- 二叉树是一个特殊的树,它的度最大为2,但是并没有说一定为2。
特殊的二叉树
满二叉树
一个二叉树,如果每一个层的结点数都达到最大值,那么这个二叉树就是满二叉树。也就是说,如果一个二叉树的成熟为K,那么结点总数就是,那么它就是满二叉树。

根据上图:
- 假设高度为h,那么就会有
的节点;
- 那么假设树有N个节点的话,那就是
;那么 高度就为
。
完全二叉树
完全二叉树,前h-1层都是满的,最后一层不一定满,但是从左到右必须连续。
完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深入为K的,有n个节点的二叉树,当且仅当其每一个节点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
这里注意二叉树顺序是固定的,必须是连续的。
假设完全二叉树的高度为h,那么它的结点数量是多少呢?
完全二叉树的最后一层的范围:
思路:
- 这里我们想在满二叉树中,结点数为
;
- 那么满二叉树中的上一层就是有
;
- 因为完全二叉树就是满二叉树的基础上,最后一层不满,也就是最后一层的结点数最多有
,最少有1个;
- 所以根据等比公式可以求得出完全二叉树最后一层的范围为:
。
相关文章:
【数据结构】二叉树概念 | 满二叉树 | 完全二叉树
二叉树的概念 二叉树在实践中用的很多。 一棵二叉树是结点的一个有限集合,该集合: 或者为空;由一个根结点加上两棵别称为左子树和右子树的二叉树组成。二叉树最多两个孩子。 这里注意:二叉树并不是度为2的树。 二叉树的度最大值是…...
第 373 场 LeetCode 周赛题解
A 循环移位后的矩阵相似检查 模拟 class Solution { public:bool areSimilar(vector<vector<int>> &mat, int k) {int m mat.size(), n mat[0].size();k % n;auto g mat;for (int i 0; i < m; i)if (i & 1)rotate(mat[i].begin(), mat[i].begin() …...
C#,《小白学程序》第二十五课:大数乘法(BigInteger Multiply)的Karatsuba算法及源代码
1 文本格式 /// <summary> /// 《小白学程序》第二十五课:大数(BigInteger)的Karatsuba乘法 /// Multiplies two bit strings X and Y and returns result as long integer /// </summary> /// <param name"a">&…...
Redis的五大数据类型详细用法
我们说 Redis 相对于 Memcache 等其他的缓存产品,有一个比较明显的优势就是 Redis 不仅仅支持简单的key-value类型的数据,同时还提供list,set,zset,hash等数据结构的存储。本篇博客我们就将介绍这些数据类型的详细使用…...
C++类与对象(6)—初始化列表、explicit关键字、static成员
目录 一、初始化列表 1、定义 2、注意事项 3、尽量使用初始化列表初始化 4、初始化顺序 二、 explicit关键字 1、定义 2、特点 三、static成员 1、定义 2、特性 3、例题 一、初始化列表 下面这段代码可以正常编译: class A { private:int _a1;//成员…...
vue3+tsx的使用
<template><div><xiaoman on-click"getItem" name"似懂非懂"></xiaoman></div> </template><script setup langts>import xiaoman from "./App"const getItem(item:any)>{console.log(item,it…...
JMeter 设置请求头信息的详细步骤
在使用 JMeter 的过程中,我们会遇到需要设置请求头信息的场景。比如: POST 传过去的 Body 数据是 json 格式的。需要填添加头信息:Content-Type:application/json。 在 header 中用 token 来传用户的认证信息。 下面,…...
从零构建属于自己的GPT系列1:预处理模块
1 训练数据 在本任务的训练数据中,我选择了金庸的15本小说,全部都是txt文件 数据打开后的样子 2 数据预处理 数据预处理需要做的事情就是使用huggingface的transformers包的tokenizer模块,将文本转化为token 最后生成的文件就是train_n…...
002、ArkTS
之——开发语言 目录 之——开发语言 杂谈 正文 1.TypeScript基础 1.1 基础类型 1.2 条件语句 1.3 函数 1.4 类 1.5 模块 1.6 迭代器 2.ArkTS 2.1 JAVA SCRIPT 2.2 TS 2.3 ArkTS 编辑 3.示例 3.1 概述性示例 3.2 自定义组件 3.3 渲染控制语法 3.4 状态管…...
如何通过nginx进行服务的负载均衡
简单介绍 随着互联网的发展,业务流量越来越大并且业务逻辑也越来越复杂,单台服务器的性能及单点故障问题就凸显出来了,因此需要多台服务器组成应用集群,进行性能的水平扩展以及避免单点故障的出现。应用集群是将同一应用部署到多台…...
FPGA程序前仿真和后仿真问题处理
参考链接:FPGA程序前仿真和后仿真问题处理 - 知乎...
C语言WFC绘制矩形
代码实现: void CCGDrawingView::Rectangle(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, COLORREF color,CDC* pDC) {CPen redPen(PS_SOLID, 1, color);CBrush redBursh(color);CPen* pOldPen pDC->SelectObject(&redPen);CBrush* p…...
SpringCloud Alibaba集成 Gateway(自定义负载均衡器)、Nacos(配置中心、注册中心)、loadbalancer
文章目录 POM依赖环境准备配置配置文件配置类 案例展示 POM依赖 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.7.10</version><relativePath/></p…...
HarmonyOS应用开发者基础认证【题库答案】
HarmonyOS应用开发者高级认证【题库答案】 一、判断 首选项preferences是以Key-Value形式存储数据,其中Key是可以重复。(错)使用http模块发起网络请求时,必须要使用on(‘headersReceive’)订阅请求头,请…...
[pyqt5]pyqt5设置窗口背景图片后上面所有图片都会变成和背景图片一样
pyqt5的控件所有都是集成widget,窗体设置背景图片后控件背景也会跟着改变,此时有2个办法。第一个办法显然我们可以换成其他方式设置窗口背景图片,而不是使用styleSheet样式表,网上有很多其他方法。还有个办法就是仍然用styleSheet…...
【Docker】从零开始:7.Docker命令:容器命令及参数详解
【Docker】从零开始:7.帮助启动类命令 一、帮助启动类命令启动Docker停止Docker重启Docker查看Docker状态开机启动查看docker概要信息查看docker总体帮助文档查看docker命令帮助文档 二、镜像命令列出本地主机上的镜像运行示例返回说明操作参数 搜索仓库里的某个镜像…...
Mysql 锁机制分析
整体业务代码精简逻辑如下: Transaction public void service(Integer id) {delete(id);insert(id); }数据库实例监控: 当时通过分析上游问题流量限流解决后,后续找时间又重新分析了下问题发生的根本原因,现将其总结如下…...
跟着chatgpt学习|1.spark入门
首先先让chatgpt帮我规划学习路径,使用Markdown格式返回,并转成思维导图的形式 目录 目录 1. 了解spark 1.1 Spark的概念 1.2 Spark的架构 1.3 Spark的基本功能 2.spark中的数据抽象和操作方式 2.1.RDD(弹性分布式数据集) 2…...
使用conan包 - 安装依赖项
使用conan包 - 安装依赖项 主目录 conan Using packages1 Requires2 Optional user/channel3 Overriding requirements4 Generators5 Options 本文是基于对conan官方文档Installing dependencies的翻译而来, 更详细的信息可以去查阅conan官方文档。 This section s…...
【数据库设计和SQL基础语法】--数据库设计基础--数据规范化和反规范化
一、 数据规范化 1.1 数据规范化的概念 定义 数据规范化是数据库设计中的一种方法,通过组织表结构,减少数据冗余,提高数据一致性和降低更新异常的过程。这一过程确保数据库中的数据结构遵循一定的标准和规范,使得数据存储更加高…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
