二叉树(上)
“路虽远,行则将至”
❤️主页:小赛毛
目录
1.树概念及结构
1.1树的概念
1.2 树的相关概念
1.3 树的表示(树的存储)
2.二叉树概念及结构
2.1概念
2.2现实中的二叉树
2.3 特殊的二叉树:
2.4 二叉树的性质
3.二叉树的顺序结构及实现
3.1 二叉树的顺序结构
3.2 堆的概念及结构
3.3 堆的实现
3.2.1 堆向下调整算法
3.2.2堆的创建
前言:
在进入今天的正题之前,我们先来回顾一下我们已经学过的知识:
顺序的本质是什么呢?数组
但是呢,顺序表在这里是有一些缺陷的:
1.中间或者头部插入删除数据要挪动数据,效率低
2.空间不够,只能扩容。扩容有消耗
3.倍数扩容,用不完,存在空间浪费
当然,有利有弊,优点:
1.下标随机访问。排序 二分查找适合
2.CPU高速缓存命中率比较高
在我们学完顺序表之后呢,我们当时顺序就学了链表:
在这里呢,我们要请出链表的典型代表——带头结点的双向循环链表 同志来参加。
优点:
1.任意位置插入删除效率高
2.按需申请释放,不存在扩容
缺点:
1.不能下标随机访问
2.CPU高速缓存命中率低
1.树概念及结构
1.1树的概念
- 有一个特殊的结点,称为根结点,根节点没有前驱结点
- 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
- 因此,树是递归定义的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
1.2 树的相关概念
- 节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的为6
- 叶节点或终端节点:度为0的节点称为叶节点;如上图:B、C、H、I...等节点为叶节点
- 非终端节点或分支节点:度不为0的节点;如上图:D、E、F、G...等节点为分支节点
- 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;如上图:A是B的父节点
- 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;如上图:B是A的孩子节点
- 兄弟节点:具有相同父节点的节点互称为兄弟节点;如上图:B、C是兄弟节点
- 树的度:一棵树中,最大的节点的度称为树的度;如上图:树的度为6
- 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
- 树的高度或深度:树中节点的最大层次;如上图:树的高度为4
- 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点
- 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
- 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
- 森林:由m(m>0)棵互不相交的树的集合称为森林;(并查集里面就是多棵树)
1.3 树的表示(树的存储)
struct TreeNode
{int val;struct TreeNode* firstchild;//第一个孩子节点struct TreeNode* nextbroyher;//指向其下一个兄弟节点
}
双亲表示法(只存储父亲的下标或指针):
在很多地方,双亲表示法一般就是用数组的方式直接玩
这个地方就可以很容易判断出来有几棵树,有几个兄弟。
于是否,两个节点在不在同一棵树,如何判断?
找根,根相同就在同一棵树
其实呢,在实际生活中,我们用的最多的实际上是二叉树
2.二叉树概念及结构
2.1概念

2.2现实中的二叉树
2.3 特殊的二叉树:

2.4 二叉树的性质
3.二叉树的顺序结构及实现
3.1 二叉树的顺序结构
parent = (child-1) / 2
任意位置通过下标可以找父亲或者孩子
那如果不是满二叉树或者完全二叉树的话,还适合这个规律吗?显然不可以
那我们这里可以进行总结:
满二叉树 或者 完全二叉树适合用数组存储
3.2 堆的概念及结构


3.3 堆的实现
3.2.1 堆向下调整算法
我们在这里先来说明一下:
栈:线性表,后进先出
堆:非线性表,完全二叉树
小堆:树中任意一个父亲都 ≤ 孩子
大堆:树中任意一个父亲都 ≥ 孩子
intarray[] = {27,15,19,18,28,34,65,49,25,37};
底层:
- 物理结构:数组
- 逻辑结构:完全二叉树
小堆,底层数组是否升序呢?不一定
小堆的根是整棵树的最小值
3.2.2堆的创建
inta[] = {1,5,3,8,7,6};
相关文章:

二叉树(上)
“路虽远,行则将至” ❤️主页:小赛毛 目录 1.树概念及结构 1.1树的概念 1.2 树的相关概念 1.3 树的表示(树的存储) 2.二叉树概念及结构 2.1概念 2.2现实中的二叉树 2.3 特殊的二叉树: 2.4 二叉树的性质 3.二叉树的顺…...

Excel怎么批量生成文件夹
Excel怎么批量生成文件夹的链接: https://jingyan.baidu.com/article/ea24bc398d9dcb9b63b3312f.html...

c++ 学习之 静态成员变量和静态成员函数
文章目录 前言正文静态成员变量初始化操作如何理解共享一份数据访问权限 静态成员函数访问方式静态成员函数只能访问静态成员变量访问权限 前言 静态成员分为 1)静态成员变量 所有对象共享一份数据在编译阶段分配空间类内声明,类外初始化 2)…...
C程序需要按下回车键才能读取字符
当编写涉及从终端输入字符的C程序时,有时会遇到需要按下回车键才能读取字符的问题。这是因为默认情况下,终端通常处于行缓冲模式,需要等待用户按下回车键才会将输入的字符发送给正在运行的程序。这可能会导致一些不便,尤其是当程序…...

x86体系结构(WinDbg学习笔记)
寄存器 eaxAccumulator累加器ebxBase register基寄存器ecxCounter register计数器寄存器edxData register - can be used for I/O port access and arithmetic functions数据寄存器-可用于I/O端口访问和算术函数esiSource index register源索引寄存器ediDestination index reg…...

Hadoop的第二个核心组件:MapReduce框架第四节
Hadoop的第二个核心组件:MapReduce框架 十、MapReduce的特殊应用场景1、使用MapReduce进行join操作2、使用MapReduce的计数器3、MapReduce做数据清洗 十一、MapReduce的工作流程:详细的工作流程第一步:提交MR作业资源第二步:运行M…...
算法通关村第十九关——最少硬币数
LeetCode322.给你一个整数数组 coins,表示不同面额的硬币,以及一个整数 amount,表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回-1。你可以认为每种硬币的数量是无限的。 示例1&…...

Linux ifconfig只显示 lo 网卡,没有ens网卡解决方案
项目场景: 虚拟机中linux无网络问题 问题描述 之前在调试linux的时候,由于一些不太清楚的误操作,导致ubuntu linux出现无网络问题,现象如下 ifconfig 只显示了 lo 网卡 lo 网卡:它是本地环回接口。 这意味着您的虚…...
Java复习-26-枚举
枚举(替换多例设计) 目的(使用场景) 不用也没啥 定义一个描述性别的类,那么该对象只有两个:男、 女。或者描述颜色基色的类,可以使用: 红色、绿色、蓝色。 功能 用于定义有限个数对象的一种结构&#x…...

NLP(六十八)使用Optimum进行模型量化
本文将会介绍如何使用HuggingFace的Optimum,来对微调后的BERT模型进行量化(Quantization)。 在文章NLP(六十七)BERT模型训练后动态量化(PTDQ)中,我们使用PyTorch自带的PTDQ&…...

Tomcat多实例和负载均衡动静分离
目录 一、Tomcat多实例部署 二、负载均衡动静分离 2.1.动静分离 2.11 nginx负载均衡 192.168.30.203 2.22 Tomcat服务器:192.168.30.200:80 2.23 Tomcat服务器:192.168.30.100:80 2.24 配置nginx 192.168.30.203静态页面 2…...

企业ERP和泛微OA集成场景分析
轻易云数据集成平台(qeasy.cloud)为企业ERP和泛微OA系统提供了强大的互通解决方案,特别在销售、采购和库存领域的单据审批场景中表现出色。这些场景涉及到多个业务单据的创建和审批,以下是一些具体的应用场景描述: 采购…...

31 WEB漏洞-文件操作之文件包含漏洞全解
目录 文件包含漏洞原理检测类型利用修复 本地包含-无限制,有限制远程包含-无限制,有限制各种协议流玩法文章介绍读取文件源码用法执行php代码用法写入一句话木马用法每个脚本支持的协议玩法 演示案例某CMS程序文件包含利用-黑盒CTF-南邮大,i春…...
qmake.exe xxx.pro -spec win32-g++ 作用
作用 qmake.exe xxx.pro -spec win32-g的作用是使用win32-g构建系统规范来生成针对xxx.pro项目的构建脚本。 具体来说,这个命令的含义如下: qmake.exe:使用qmake命令行工具。xxx.pro:指定了要构建的项目文件,.pro文…...

SpringMVC实现增删改查
文章目录 一、配置文件1.1 导入相关pom依赖1.2 jdbc.properties:配置文件1.3 generatorConfig.xml:代码生成器1.4 spring-mybatis.xml :spring与mybatis整合的配置文件1.5 spring-context.xml :上下文配置文件1.6 spring-mvc-xml:…...
React 配置别名 @ ( js/ts 项目中通过 webpack.config.js 配置)
一、简介 在 Vue 项目当中,可以使用 来表示 src/,但在 React 项目中,默认却没有该功能,因此需要进行手动的配置来实现该功能。 别名主要解决的问题:每个页面都使用路径的方式进行引入,这样很麻烦ÿ…...

Android 在TextView前面添加多个任意View且不影响换行
实现效果如下: 如上,将头像后面的东西看作一个整体,因为不能影响后面内容的换行,且前面控件的长度是可变的,所以采用自定义View的方法来实现: /*** CSDN深海呐 https://blog.csdn.net/qq_40945489/articl…...
字符串相加
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。 示例 1: 输入ÿ…...
uni-app直播从0到1实战
1.安装开发工具 2.创建项目 参考:uniapp从零到一的学习商城实战_云澜哥哥的博客-CSDN博客...

Python UI自动化 —— pytest常用运行参数解析、pytest执行顺序解析
pytest常用Console参数: -v 用于显示每个测试函数的执行结果-q 只显示整体测试结果-s 用于显示测试函数中print()函数输出-x 在第一个错误或失败的测试中立即退出-m 只运行带有装饰器配置的测试用例-k 通过表达式运行指定的测试用例-h 帮助 首先来看什么参数都没加…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
Qt学习及使用_第1部分_认识Qt---Qt开发基本流程
前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...