二叉树(补充)
二叉树
- 1.二叉树的基本特性
- 2.堆
- 2.1.堆的基本概念
- 2.2.堆的实现
- 2.2.1.基本结构
- 2.2.2.堆的初始化
- 2.2.3.堆的销毁
- 2.2.4.堆的插入
- 2.2.5.取出堆顶的数据
- 2.2.6.堆的删除
- 2.2.7.堆的判空
- 2.2.8.堆的数据个数
- 2.2.9.交换
- 2.2.10.打印堆数据
- 2.2.11.堆的创建
- 2.2.12.堆排序
1.二叉树的基本特性
上图展示的就是二叉树,我将它的规律也写在上面了
一般我们把二叉树的高度设置从1开始,从0开始的话,空树就是-1,就不太合适了
一棵N个结点的树有N-1条边
假设二叉树的第k层是满的,它的结点数为2^(k-1)个
我们的二叉树还分为满二叉树
和完全二叉树
,下图展示了二者的对比图
满二叉树:一个二叉树,如果每一层的结点都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为k,且结点总数是2^k-1,则就是满二叉树。
完全二叉树:前N-1层是满的,最后一层可以不满,但是必须从左往右是连续的,满二叉树是一种特殊的完全二叉树。
我们先来分析一下满二叉树的特性:
假设满二叉树有k层,则它的最后一层的结点有2^(k-1)个
假设满二叉树有k层,一棵满二叉树一共有2^k-1个结点
,计算方法如下:
其实还有一个小技巧:我们的二进制的每一位的值和二叉树的每一层的结点数相等的,假设我们的二进制为11111111,它是一个unsigned char类型的最大值,此时我们计算它的十进制就通过它的再高一位的值-1计算得出,即2^8-1=255。类比到二叉树,即下一层的结点数-1,设最后一层的结点个数为2 ^3,第4层,计算整棵二叉树的结点数为2 ^4-1。
设满二叉树的总结点数为N个,
树的高度为log₂(N+1)
,通过2^k-1=N计算可得
完全二叉树的特性:
设完全二叉树有k层,完全二叉树总共结点最少就是最后一层只有一个,即2^(k-1)个
;最多也就是满二叉树,即2 ^k-1个结点
最多不用讲怎么计算了,最少可以用之前讲的错位相减法来计算,也可以二叉树的规律来算:假设完全二叉树一共k层;那么根据前面讲的,除去最后一层一个结点,它就是一棵满二叉树,共k-1层,根据满二叉树的总共结点公式,总结点数为2^ (k-1)-1个;那么再加上去掉的一个结点,完全二叉树的总结点数即为2^(k-1)个,如下图
对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n2=n0+1
2.堆
2.1.堆的基本概念
接下来讲的堆是二叉树的一种存储方式,从逻辑结构(想象的结构)上看我们的堆是一棵
完全二叉树
,从存储结构上看堆是数组
我们的堆还分为大根堆(大堆)和小根堆(小堆)
大堆:父结点大于等于孩子结点,并且子树也同样的,大堆的根结点在整个堆中是最大的元素
大堆:父结点小于等于孩子结点,并且子树也同样的,小堆的根结点在整个堆中是最小的元素
之所以我们我们的数组只能表示完全二叉树,是因为不是完全二叉树会有空间浪费,如下图
并且我们的堆是数组存储还有一个特性:
对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子
2.2.堆的实现
2.2.1.基本结构
//Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
typedef int T;//堆数据类型typedef struct Heap
{T* arr;//堆的存储位置int size;//堆的数据个数int capacity;//堆的容量
}Heap;void HeapInit(Heap* heap);//堆的初始化
void HeapCreate1(Heap* heap, T* a, int n);//创建堆方法1
void HeapCreate2(Heap* heap, T* a, int n);//创建堆方法2
void HeapDestory(Heap* heap);//将堆销毁
void HeapPush(Heap* heap,T x);//堆的构建
void HeapPrint(Heap* heap);//将堆数据打印出来
T HeapTop(Heap* heap);//取出堆顶数据
void HeapPop(Heap* heap);//删除堆顶数据
int HeapSize(Heap* heap);//堆的数据个数
bool HeapEmpty(Heap* heap);//堆是否为空void swap(T* x, T* y);//交换
void AdjustUp(T* arr, int child);//向上调整
上述代码已经将存储堆的结构体已经写好,同时把我们的堆的各种函数调用已经声明好了
2.2.2.堆的初始化
void HeapInit(Heap* heap)//堆的初始化
{assert(heap);heap->arr = NULL;heap->capacity = heap->size = 0;
}
我们这边的写法是一开始不给数组任何的空间,后期直接使用realloc开辟
2.2.3.堆的销毁
void HeapDestory(Heap* heap)//将堆销毁
{assert(heap);free(heap->arr);//释放空间heap->size = heap->capacity = 0;
}
不要忘记释放开辟的空间!!!
2.2.4.堆的插入
由于我们数组的特性,头插需要移动元素什么的,效率极低,但是可以尾插,所以说堆一般性就都是在尾部插入
//我们默认建立大堆哈
void AdjustUp(T* arr,int child)//向上调整
{int parent = (child - 1) / 2;//找父结点//使用parent>=0有点不合理,倒数第二次运行循环时child已经是0了,应该结束//但是(child-1)/2导致parent依旧为0,再次进入循环,然后通过else中的breakwhile (child>0){//孩子结点大于父结点if (arr[child] > arr[parent]){//交换swap(&arr[child], &arr[parent]);//继续向上调整child = parent;parent = (child - 1) / 2;}else{//如果孩子结点小于父结点,就不用向上调整了break;}}
}void HeapPush(Heap* heap, T x)//堆的插入
{assert(heap);//空间不足开辟内存if (heap->size == heap->capacity){int newcapacity = heap->capacity == 0 ? 4 : heap->capacity * 2;//realloc的第一个元素是NULL的话,功能和malloc一样T* newarr = (T*)realloc(heap->arr, newcapacity*sizeof(T));if (newarr == NULL){perror("realloc fail");exit(-1);}//修改已经开辟好空间后的信息heap->arr = newarr;//realloc可能不在原位扩容,所以说这一步是必要的heap->capacity = newcapacity;}//正式插入heap->arr[heap->size] = x;heap->size++;//数据个数+1//向上调整,保证是一个堆AdjustUp(heap->arr, heap->size - 1);
}
我们默认建立的是大堆哈,如果想要建立小堆,只需要将向上调整中的比较孩子结点和父结点的>变成<即可
代码和图片也展示在了上面,可以通过图片来理解一下,之所以这样写是因为我们在没有进行插入前,我们的结构肯定是堆的,但是插入后,我们需要进行调整才能保证堆的结构,我们写的是大堆,
因此需要和父结点进行比较,如果比父结点大,那么继续交换。但是由于交换后,可能还是比祖父结点大,也就还需要不停地调整。向上调整是对插入结点的祖先进行调整
2.2.5.取出堆顶的数据
T HeapTop(Heap* heap)//取出堆顶数据
{ assert(heap);assert(heap->size > 0);return heap->arr[0];
}
我们的可以用于Top-k问题,举个例子,我们在10000个人里面,选出最有钱的人,我们的堆就发挥了大用处,因为它的堆顶的数据,即数组第一个元素是最大(最小)的,我们只需要取出后,再删除就可以选出第二大的…第n大的,因此我们还需要来实现一下删除才能彻底理解
2.2.6.堆的删除
void AdjustDown(T* arr, int size,int parent)
{//选出左孩子和右孩子中较大的那个//假设较大的是左孩子int child = parent * 2 + 1;//孩子结点存在才向下调整while (child<size){if (child + 1 < size && arr[child + 1] > arr[child]){//进行判断,如果右孩子大于左孩子,就+1,因为左孩子和右孩子之间就相差1child++;}//孩子结点大于父节点,就需要交换,保证大堆的特性if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else{//如果孩子结点小于父结点,说明不需要调整了,跳出循环break;}}}void HeapPop(Heap* heap)//删除堆顶数据
{assert(heap);assert(heap->size>0);//先将堆顶的元素和最后一个元素进行交换swap(&heap->arr[0], &heap->arr[heap->size - 1]);//堆数据个数-1heap->size--;//向下调整AdjustDown(heap->arr,heap->size,0);
}
上面已经给出了代码和交换的图片,我们首先来讲一下为什么需要通过交换才能删除这个最大(最小)元素,究其原因还是它在根节点的原因,没有办法对它进行一个直接删除,一旦直接删除,就会导致整体的一个堆结构就乱掉了。我们根结点的左子树和右子树是堆,不能破坏它,那么最好的方法就是和尾元素进行交换,然后进行向下调整,这样不但保证了结构的完整性,效率还高。
向下调整如下图:
2.2.7.堆的判空
bool HeapEmpty(Heap* heap)//堆是否为空
{assert(heap);return heap->size == 0;
}
2.2.8.堆的数据个数
int HeapSize(Heap* heap)//堆的数据个数
{assert(heap);return heap->size;
}
2.2.9.交换
void swap(T* x, T* y)//交换
{T tmp = *x;*x = *y;*y = tmp;
}
2.2.10.打印堆数据
void HeapPrint(Heap* heap)//将堆数据打印出来
{for (int i = 0; i < heap->size; ++i){printf("%d ", heap->arr[i]);}printf("\n");
}
2.2.11.堆的创建
//简单粗暴的一种方法
void HeapCreate1(Heap* heap, T* a, int n)//创建堆1
{assert(heap);HeapInit(heap);for (int i = 0; i < n; i++){HeapPush(heap, a[i]);}
}void AdjustDown(T* arr, int size, int parent);//定义在下面,这边要使用,声明一下void HeapCreate2(Heap* heap, T* a, int n)//创建堆2
{assert(heap);HeapInit(heap);//开辟空间heap->arr = (T*)malloc(sizeof(T) * n);if (heap->arr == NULL){perror("malloc fail");exit(-1);}//拷贝数据memcpy(heap->arr, a, n*sizeof(T));heap->size = heap->capacity = n;//从下至上进行向下调整for (int end = (n - 1 - 1) / 2; end >= 0; end--){AdjustDown(heap->arr, n, end);}
}
上面展示了代码和图片,堆的创建我们用了两种方法,第一种就比较直接,循环push即可,但它的效率不是很高,于是我们有了第二种方法,想要保证一组毫无序列的元素变成堆,就需要保证每一个子树的父节点都大于(小于)孩子节点,因此我们只能从最后一棵子树开始向下调整(叶子结点不需要调整了),这样当调整到上一层时,下层都已经是堆了,只需要对当前节点也是向下调整即可。一直到根节点完成最后一次向下调整就可以完成堆的构建。
在代码中end两次-1,第一次-1是为了找到最后一个元素在数组中的位置,第二次-1是为了找到父结点。
2.2.12.堆排序
在我们讲述堆排序前,我们先来讨论一下,当我们对于一个随机的数组,将它变成一个堆,是使用向上调整好还是向下调整好呢?我们接下来分析一下
可以看到,向下调整和向上调整都能建堆,如果简单来看的话会认为向上调整的时间复杂度是都是O(N*logN),而向下调整就有点难以看出来了,我们来计算一下
相关文章:

二叉树(补充)
二叉树 1.二叉树的基本特性2.堆2.1.堆的基本概念2.2.堆的实现2.2.1.基本结构2.2.2.堆的初始化 2.2.3.堆的销毁2.2.4.堆的插入2.2.5.取出堆顶的数据2.2.6.堆的删除2.2.7.堆的判空2.2.8.堆的数据个数2.2.9.交换2.2.10.打印堆数据2.2.11.堆的创建2.2.12.堆排序 1.二叉树的基本特性…...
(DM)达梦数据库基本操作(持续更新)
1、连接达梦数据库 ./disql 用户明/"密码"IP端口或者域名 2、进入某个模式(数据库,因达梦数据库没有库的概念,只有模式,可以将模式等同于库) set schema 库名; 3、查表结构; SELECT COLUMN_NAM…...
CRM 微服务
文章目录 项目地址一、项目地址 教程作者:教程地址:代码仓库地址:所用到的框架和插件:dbt airflow一、 用户与认证服务 主要功能: 用户注册、登录、注销。 认证(OAuth、JWT 等)。 权限和角色管理(RBAC/ABAC)。 单点登录(SSO)。 技术亮点: 集成第三方身份认证(如 …...

AI软件外包需要注意什么 外包开发AI软件的关键因素是什么 如何选择AI外包开发语言
1. 定义目标与需求 首先,要明确你希望AI智能体做什么。是自动化任务、数据分析、自然语言处理,还是其他功能?明确目标可以帮助你选择合适的技术和方法。 2. 选择开发平台与工具 开发AI智能体的软件时,你需要选择适合的编程语言、…...

DBSyncer开源数据同步中间件
一、简介 DBSyncer(英[dbsɪŋkɜː(r)],美[dbsɪŋkɜː(r) 简称dbs)是一款开源的数据同步中间件,提供MySQL、Oracle、SqlServer、PostgreSQL、Elasticsearch(ES)、Kafka、File、SQL等同步场景。支持上传插件自定义同步转换业务,提供监控全量…...

< OS 有关 > 阿里云 几个小时前 使用密钥替换 SSH 密码认证后, 发现主机正在被“攻击” 分析与应对
信息来源: 文件:/var/log/auth.log 因为在 sshd_config 配置文件中,已经定义 LogLevel INFO 部分内容: 2025-01-27T18:18:55.68272708:00 jpn sshd[15891]: Received disconnect from 45.194.37.171 port 58954:11: Bye Bye […...

react-bn-面试
1.主要内容 工作台待办 实现思路: 1,待办list由后端返回,固定需要的字段有id(查详细)、type(本条待办的类型),还可能需要时间,状态等 2,一个集中处理待办中转路由页,所有待办都跳转到这个页面…...

1. Java-MarkDown文件创建-工具类
Java-MarkDown文件创建-工具类 1. 思路 根据markdown语法,拼装markdown文本内容 2. 工具类 import java.util.Arrays; import java.util.List;/*** Markdown生成工具类* Author: 20004855* Date: 2021/1/15 16:00*/ public class MarkdownGenerator {private Str…...

全连接神经网络(前馈神经网络)
一、全连接神经网络介绍 在多层神经网络中, 第 N 层的每个神经元都分别与第 N-1 层的神经元相互连接。 1、神经元 这个神经元接收的输入信号为向量 , 向量为输入向量的组合权重, 为偏置项, 是一个标量。 神经元的作用是对输入向…...
【llm对话系统】什么是 LLM?大语言模型新手入门指南
什么是 LLM?大语言模型新手入门指南 大家好!欢迎来到 LLM 的奇妙世界!如果你对人工智能 (AI) 的最新进展,特别是那些能像人类一样阅读、写作甚至进行对话的 AI 感兴趣,那么你来对地方了。这篇文章将带你认识 LLM 的基…...

【Linux】互斥锁、基于阻塞队列、环形队列的生产消费模型、单例线程池
⭐️个人主页:小羊 ⭐️所属专栏:Linux 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 1、互斥锁2、生产消费模型2.1 阻塞队列2.2 环形队列 3、单例线程池4、线程安全和重入问题 1、互斥锁 临界资源:多线程…...

【学术会议征稿】第五届能源、电力与先进热力系统学术会议(EPATS 2025)
能源、电力与先进热力系统设计是指结合物理理论、工程技术和计算机模拟,对能源转换、利用和传输过程进行设计的学科领域。它涵盖了从能源的生产到最终的利用整个流程,旨在提高能源利用效率,减少能源消耗和环境污染。 重要信息 官网…...
ES6 类语法:JavaScript 的现代化面向对象编程
Hi,我是布兰妮甜 !ECMAScript 2015,通常被称为 ES6 或 ES2015,是 JavaScript 语言的一次重大更新。它引入了许多新特性,其中最引人注目的就是类(class)语法。尽管 JavaScript 一直以来都支持基于…...

Sprintboot原理
配置优先级 Springboot中支持的三种配置文件: application.propertiesapplication.ymlapplication.yaml java系统属性:-Dxxxxxx 命令行参数:-xxxxxx 优先级:命令行参数>java系统属性>application.properties>applicat…...
OpenHarmony 5.0.2 Release来了!
版本概述 OpenHarmony 5.0.2 Release版本对标准系统的能力进行持续完善,以快速迭代的方式推出API 14,相比5.0.1 Release版本,重点做出了如下特性新增或增强: 进一步增强ArkUI、图形图像的能力,提供更多组件的高级属性…...

Qt 控件与布局管理
1. Qt 控件的父子继承关系 在 Qt 中,继承自 QWidget 的类,通常会在构造函数中接收一个 parent 参数。 这个参数用于指定当前空间的父控件,从而建立控件间的父子关系。 当一个控件被设置为另一控件的子控件时,它会自动成为该父控…...
使用小尺寸的图像进行逐像素语义分割训练,出现样本不均衡训练效果问题
在使用小尺寸图像进行逐像素语义分割训练时,确实可能出现样本不均衡问题,且这种问题可能比大尺寸图像更显著。 1. 小尺寸图像如何加剧样本不均衡? (1) 局部裁剪导致类别分布偏差 问题:遥感图像中某些类别(如道路、建…...
0.91英寸OLED显示屏一种具有小尺寸、高分辨率、低功耗特性的显示器件
0.91英寸OLED显示屏是一种具有小尺寸、高分辨率、低功耗特性的显示器件。以下是对0.91英寸OLED显示屏的详细介绍: 一、基本参数 尺寸:0.91英寸分辨率:通常为128x32像素,意味着显示屏上有128列和32行的像素点,总共409…...

读书笔记--分布式服务架构对比及优势
本篇是在上一篇的基础上,主要对共享服务平台建设所依赖的分布式服务架构进行学习,主要记录和思考如下,供大家学习参考。随着企业各业务数字化转型工作的推进,之前在传统的单一系统(或单体应用)模式中&#…...

HTML5 新的 Input 类型详解
HTML5 引入了许多新的输入类型,极大地增强了表单的功能和用户体验。这些新的输入类型不仅提供了更好的输入控制,还支持内置的验证功能,减少了开发者手动编写验证逻辑的工作量。本文将全面介绍 HTML5 中新增的输入类型,并结合代码示…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...

实战设计模式之模板方法模式
概述 模板方法模式定义了一个操作中的算法骨架,并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下,重新定义算法中的某些步骤。简单来说,就是在一个方法中定义了要执行的步骤顺序或算法框架,但允许子类…...