二叉树(补充)
二叉树
- 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 中新增的输入类型,并结合代码示…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...

LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...