二叉树与堆的实现

一 . 概念与结构

在树的概念与结构中树的概念与结构-CSDN博客， 我们发现子结点可以为 0 或者是更多 ， 结构较为复杂 ， 然后把树的结点个数 加个限制条件 --> 不能超过 2 --> 我们引出了二叉树，在实际运用广 且高效 ；

在树形结构中 ， 我们最常用的就是二叉树 ， 一棵二叉树是结点的一个有限集合 ， 该结点由一个根结点加上两棵   称 为左子树  和  右子树的二叉树 或者为空 ；

二叉树的特点 ：

1 . 不存在大于 2 的结点

2 . 二叉树的子树有左右之分 ， 次序不能颠倒 ， 因此二叉树是有序树 ； 

注意 ： 对于任意的二叉树都是由以下几种情况复合而成的 ! ! !

二 . 特殊的二叉树

 2.1 满二叉树

一个二叉树 ， 如果每一层的结点数都达到最大值 ， 则这个二叉树就是满二叉树 。 

也就是说 ， 如果一个二叉树的层数为K，且结点的总数是    _2{k}-1  ,  则它就是满二叉树。

 2.2 完全二叉树

完全二叉树是效率很高的数据结构 ， 完全二叉树是由满二叉树而引出来的 。 对于深度为 K 的 ， 有 n 个结点的二叉树 ， 当且仅当其每个结点都与深度为 K 的满二叉树从 1 到 n 的结点一 一对应时称之为完全二叉树 ；

注意 : 满二叉树是一种特殊的完全二叉树  。 

通俗点说 ： 最后一层结点的个数不一定达到最大 ， 但是最后一层的结点必须从左往右依次排列 。

满二叉树是特殊的完全二叉树 ！！！ 

 二叉树的特质 :

  1.  若规定根结点的层数为 1 ，则一棵非空二叉树的第 i 层最多有 2^{i-1} 个结点
  2. 若规定根结点的层数为 1  ， 则深度为 h 的二叉树的最大结点树是 2^{h} - 1
  3. 若规定根结点的层数为 1  ，具有 n 个结点的满二叉树的深度 h =  \log_{2}(n+1)

 三 . 二叉树存储结构

二叉树一般可以使用两种结构存储 ， 一种顺序结构 ， 一种链式结构 。

3.1 顺序存储结构

顺序结构存储就是使用数组来存储 ， 一般使用数组只适合表示完全二叉树 ， 因为不是完全二叉树会有空间的浪费 ， 完全二叉树更适合使用顺序结构存储 。

 现实生活中 ， 我们通常把堆 （一种二叉树 ）使用顺序结构的数组来存储 ， 需要注意的是这里的堆和   操作系统虚拟进程地址空间中的堆  是两回事 ， 一个是数据结构 ， 一个是操作系统中管理内存的一块区域分段 。

 3.2 链式结构

二叉树的链式存储结构是指 ， 用链表来表示一棵二叉树 ，即用链来指示元素的逻辑关系 。 通常的方法是链表中每个结点由三个域组成 ， 数据域 和左右指针域 ， 左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。 链式结构又分为二叉链 和 三叉链 ，接下来介绍的是二叉链 ， 在后续更新的数据结构 --> 如红黑树 ， 会使用到三叉链 。

四 . 实现顺序结构二叉树

一般堆使用   顺序结构的数组  来存储数据 ， 堆是一种特殊的二叉树 ， 具有二叉树的特性的同时 ， 还具备其他的特性 。

4.1 树的概念与结构

如果由一个关键码的集合 K =  {  k_{0},k_{1},k_{2},...,k_{n+1}   } , 它把所有元素按完全二叉树的顺序存储方式存储 ， 一个一维数组中 ， 并满足 ：K_{i} <= K_{2*i +1}  ( K_{i} >= K_{2*i +1} 且 K_{i} <= K_{2*i +1} ） ， i = 0,1,2...) , 称为小堆(或大堆) 。将根结点最大的堆叫做最大堆或大根堆 ， 根结点最小的堆叫最小堆或小根堆 。

 堆具有以下性质 ： 

1 ） 堆中某个结点的值总是  不大于 或者 不小于 其父结点的值 ；

2 ） 堆总是一棵完全二叉树 ；

 二叉树的性质 ：

对于具有  n 个节点的完全二叉树 ， 如果按照   从上到下 ， 从左到右 的数组顺序对所有结点 从 0 开始编号 ， 则对于序号为 i 的结点有 : 

1 ） 若 i > 0 ,i 位置 结点的双亲序号 : （ i - 2 ) / 2 ;  

       i  = 0 , i 为根结点编号 ， 无双亲结点 

2 ）若 2 i + 1< n ，左孩子序号 : 2i + 1 ， 2i+1>= n 否则无左孩子

3 )  若 2 i + 2 < n ， 右孩子序号 : 2i + 2 ， 2i+2>= n 否则无右孩子

4.2 堆的常见接口/函数的实现

堆 一般使用顺序结构的数组来存储数据 ： 

初始化

堆 的底层结构是数组 。

typedef int HPDataType;
//定义堆的结构
typedef struct Heap
{HPDataType* arr;int size; // 有效数据int capacity; //空间容量
}HP;//堆的初始化
void HPInit(HP* php);
//堆的初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
销毁

当数组不为空的时候 ， 进行空间释放

//堆的销毁
void HPDeatory(HP* php)
{if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}
向上调整

主要运用于  堆的插入后进行数据顺序的调整 :

将新数据插入到数组的尾上，即最后一个孩子之后 ， 插入之后如果堆的性质遭到破坏 ， 将新插入的结点顺着其双亲往上调整到合适的位置即可 -----> 向上调整算法 ， 直到满足堆( 大堆 / 小堆） ！

1 ） 先找插入数据的父结点 ( child - 1 ) / 2

2 )   然后子结点与父结点进行判断大小，是否需要交换

3 ） 交换后，仍需继续比较，直到满足了堆的需求

//向上调整
void AdjustUP(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){// > : 大堆// < : 小堆if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

 

插入数据

1 ） 判断空间是否足够 ， 不足够时进行增容 ( realloc)

2 )   插入数据 ， 让后让有效数据size往后走 (size++）

3 ） 进行向上调整！

//插入数据
void HPPush(HP* php, HPDataType x)
{assert(php);//空间不足时 -- 申请空间 -- reallocif (php->size == php->capacity){int newCapacity = php->capacity == 0 ? sizeof(HPDataType) : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//空间足够 - 插入数据php->arr[php->size] = x;php->size++;AdjustUP(php->arr, php->size - 1);
}

判断是否为空

如果有效数据为 0 ，即为空

//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

 

求有效数字Size

直接返回size

//判断size
int HPSize(HP* php)
{assert(php);return php->size;
}

 

向下调整

一般用于堆的删除后 ， 进行顺序的调整 ；

注意 : 删除堆是删除堆顶的数据 ！

前提 : 左右子树必须是一个堆才能调整 ！

1 ）先让堆顶的数据与 最后一个有效数据交换

2  ) 然后删除最后一个数据

3  )  让交换完之后的堆顶数据与 子结点 进行对比 ， 直到满足需求！

 然后一直往下调整

 

//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){//先找最小孩子if (child+1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}
删除数据 

1 ） 删除数据之前需要判断堆是否为空！

2 ） 将堆顶的数据与最后一个有效数据进行交换

3 ） size--;

4 )   从堆顶开始向下调整

//删除堆顶数据
void HPPop(HP* php)
{//堆不为空 -- 才可以进行数据的删除assert(!HPEmpty(php));// 从堆顶开始比较Swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;//向下调整AdjustDown(php->arr, 0 ,php->size);}
总代码

test.c

#include "Heap.h"void test()
{HP hp;HPInit(&hp);HPPush(&hp, 1);HPPush(&hp, 2);HPPush(&hp, 3);HPPush(&hp, 4);HPPop(&hp);HPPop(&hp);HPPop(&hp);HPPop(&hp);HPDeatory(&hp);
}
int main()
{test();return 0;
}

Heap.c

#include "Heap.h"//堆的初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//向上调整
void AdjustUP(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){// > : 大堆// < : 小堆if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//插入数据
void HPPush(HP* php, HPDataType x)
{assert(php);//空间不足时 -- 申请空间 -- reallocif (php->size == php->capacity){int newCapacity = php->capacity == 0 ? sizeof(HPDataType) : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//空间足够 - 插入数据php->arr[php->size] = x;php->size++;AdjustUP(php->arr, php->size - 1);
}//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}//判断size
int HPSize(HP* php)
{assert(php);return php->size;
}//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){//先找最小孩子if (child+1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}//删除堆顶数据
void HPPop(HP* php)
{//堆不为空 -- 才可以进行数据的删除assert(!HPEmpty(php));// 从堆顶开始比较Swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;//向下调整AdjustDown(php->arr, 0 ,php->size);}//堆的销毁
void HPDeatory(HP* php)
{if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int HPDataType;
//定义堆的结构
typedef struct Heap
{HPDataType* arr;int size; // 有效数据int capacity; //空间容量
}HP;//堆的初始化
void HPInit(HP* php);//向上调整
void AdjustUP(HPDataType* arr, int child);//插入数据
void HPPush(HP* php , HPDataType x);//判断堆是否为空
bool HPEmpty(HP* php);//判断size
int HPSize(HP* php);//向下调整
void AdjustDown(HPDataType* arr,int parent, int n);//删除堆顶数据
void HPPop(HP* php);//堆的销毁
void HPDeatory(HP* php);

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/458149.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

springboot-springboot官方文档架构

springboot-springboot官方文档架构

spring官网 >project&#xff1a;spring项目列表&#xff0c;包含了spring一系列框架的List >springboot(也可以换成其他框架)&#xff1a;springboot框架 >learn:显示这个框架的各个版本的reference doc和api doc >某版本的reference doc © 著作权归作者所有…
阅读更多...
提示工程（Prompt Engineering）指南（进阶篇）

提示工程（Prompt Engineering）指南（进阶篇）

在 Prompt Engineering 的进阶阶段&#xff0c;我们着重关注提示的结构化、复杂任务的分解、反馈循环以及模型的高级特性利用。随着生成式 AI 技术的快速发展&#xff0c;Prompt Engineering 已经从基础的单一指令优化转向了更具系统性的设计思维&#xff0c;并应用于多轮对话、…
阅读更多...
【gRPC】什么是RPC——介绍一下RPC

【gRPC】什么是RPC——介绍一下RPC

说起RPC&#xff0c;博主使用CPP手搓了一个RPC项目&#xff0c;RPC简单来说&#xff0c;就是远程过程调用&#xff1a;我们一般在本地传入数据进行执行函数&#xff0c;然后返回一个结果&#xff1b;当我们使用RPC之后&#xff0c;我们可以将函数的执行过程放到另外一个服务器上…
阅读更多...
基于python的马尔可夫模型初识

基于python的马尔可夫模型初识

基于python的马尔可夫模型初识 **1.什么是随机过程&#xff1f;****1.1模拟赌徒的毁灭Gamblers Ruin** **2.马尔可夫链(Markov Chains)****2.1马尔可夫链模拟****2.2马尔可夫转移概率图****2.3无记忆性&#xff1a;给定现在&#xff0c;未来独立于过去****2.4 n n n 步转移矩阵…
阅读更多...
Python金色流星雨

Python金色流星雨

系列目录 序号直达链接爱心系列1Python制作一个无法拒绝的表白界面2Python满屏飘字表白代码3Python无限弹窗满屏表白代码4Python李峋同款可写字版跳动的爱心5Python流星雨代码6Python漂浮爱心代码7Python爱心光波代码8Python普通的玫瑰花代码9Python炫酷的玫瑰花代码10Python多…
阅读更多...
Python图像处理——基于ResNet152的人脸识别签到系统（Pytorch框架）

Python图像处理——基于ResNet152的人脸识别签到系统（Pytorch框架）

&#xff08;1&#xff09;数据集制作 本次使用明星做为数据集&#xff0c;首先编写爬虫函数&#xff0c;根据关键字爬取对应的明星&#xff0c;爬取结果保存至data文件夹&#xff0c;并以标签名作为文件名。具体爬取的明星如下&#xff1a; 注&#xff1a;实际应用中&#xf…
阅读更多...
linux下gpio模拟spi三线时序

linux下gpio模拟spi三线时序

目录 前言一、配置内容二、驱动代码实现三、总结 前言 本笔记总结linux下使用gpio模拟spi时序的方法&#xff0c;基于arm64架构的一个SOC&#xff0c;linux内核版本为linux5.10.xxx&#xff0c;以驱动三线spi(时钟线sclk&#xff0c;片选cs&#xff0c;sdata数据读和写使用同一…
阅读更多...
华为鸿蒙HarmonyOS应用开发者高级认证视频及题库答案

华为鸿蒙HarmonyOS应用开发者高级认证视频及题库答案

华为鸿蒙开发者高级认证的学习资料 1、课程内容涵盖HarmonyOS系统介绍、DevEco Studio工具使用、UI设计与开发、Ability设计与开发、分布式特性、原子化服务卡片以及应用发布等。每个实验都与课程相匹配&#xff0c;帮助加深理解并掌握技能 2、学习视频资料 华为HarmonyOS开发…
阅读更多...
Minio文件服务器：SpringBoot实现文件上传

Minio文件服务器：SpringBoot实现文件上传

在Minio文件服务器部署成功后(参考上篇文章Minio文件服务器&#xff1a;安装)接下来我们通过SpringBoot框架写一个接口&#xff0c;来实现文件的上传功能&#xff1a;文件通过SpringBoot接口&#xff0c;上传到Minio文件服务器。并且&#xff0c;如果上传的文件是图片类型&…
阅读更多...
2025考研各省市网上确认时间汇总！

2025考研各省市网上确认时间汇总！

2025考研各省市网上确认时间汇总&#xff01; 安徽&#xff1a;11月1日至5日 福建&#xff1a;11月1日-11月5日 山东&#xff1a;10月31日9:00至11月5日12:00 新疆&#xff1a;10月31日至11月4日17:00 湖南&#xff1a;11月1日9:00-4日12:00 广东&#xff1a;10月下旬至1…
阅读更多...
【mysql进阶】4-3. 页结构

【mysql进阶】4-3. 页结构

页面结构 ⻚在MySQL运⾏的过程中起到了⾮常重要的作⽤&#xff0c;为了能发挥更好的性能&#xff0c;可以结合⾃⼰系统的业务场景和数据⼤⼩&#xff0c;对⻚相关的系统变量进⾏调整&#xff0c;⻚的⼤⼩就是⼀个⾮常重要的调整项。同时关于⻚的结构也要有所了解&#xff0c;以…
阅读更多...
Word中Normal.dotm样式模板文件

Word中Normal.dotm样式模板文件

Normal.dotm文档 首先将自己电脑中C:\Users\自己电脑用户名\AppData\Roaming\Microsoft\Templates路径下的Normal.dotm文件做备份&#xff0c;在下载本文中的Normal.dotm文件&#xff0c;进行替换&#xff0c;重新打开word即可使用。 字体样式如下&#xff08;可自行修改&#…
阅读更多...
Tongweb7049m4+THS6010-6012版本 传真实ip到后端（by yjm+lwq）

Tongweb7049m4+THS6010-6012版本 传真实ip到后端（by yjm+lwq）

遇到客户需要通过ths传真实ip到后端也就是部署到tongweb的需求&#xff0c;在ths的httpserver.conf里的location块配置了以下内容&#xff1a; proxy_set_header Host $host; proxy_set_header X-Real-IP $remote_addr; proxy_set_header X-Forwarded-For $proxy_add_x_forwar…
阅读更多...
leetcode hot100（1）

leetcode hot100（1）

1.160.相交链表 &#xff08;1&#xff09;暴力解法 循环遍历listA的所有节点&#xff0c;循环内遍历B所有节点&#xff0c;检查当前遍历到的的A、B中的节点是否一致。 如果一致&#xff0c;标记&#xff0c;跳出循环。 最后根据标记为返回结果。 时间复杂度O(len(A)*len(…
阅读更多...
解决torch识别不到cuda的问题——AssertionError: Torch not compiled with CUDA enabled

解决torch识别不到cuda的问题——AssertionError: Torch not compiled with CUDA enabled

问题表现 测试torch-gpu是否可用 运行如下代码&#xff1a; import torch print(f"Current device: {device}") print(torch.__version__) # 查看pytorch安装的版本号 print(torch.cuda.is_available()) # 查看cuda是否可用。True为可用&am…
阅读更多...
Java学习Day53：铲除紫云山金丹原料厂厂长(手机快速登录、权限控制)

Java学习Day53：铲除紫云山金丹原料厂厂长(手机快速登录、权限控制)

1.手机快速登录 手机快速登录功能&#xff0c;就是通过短信验证码的方式进行登录。这种方式相对于用户名密码登录方式&#xff0c;用户不需要记忆自己的密码&#xff0c;只需要通过输入手机号并获取验证码就可以完成登录&#xff0c;是目前比较流行的登录方式。 前端页面&…
阅读更多...
Halcon 多相机统一坐标系（标定）

Halcon 多相机统一坐标系（标定）

多相机统一坐标系是指将多个不同位置的相机的图像采集到同一个坐标系下进行处理和分析的方法。 在计算机视觉和机器视觉领域中&#xff0c;多相机统一坐标系被广泛应用于三维重建、立体视觉、目标跟踪等任务中。 以gen_binocular_rectification_map&#xff08;生成描述图像映…
阅读更多...
Python条形图 | 指标（特征）重要性图的绘制

Python条形图 | 指标（特征）重要性图的绘制

在数据科学和机器学习的工作流程中&#xff0c;特征选择是一个关键步骤。通过评估每个特征对模型预测能力的影响&#xff0c;我们可以选择最有意义的特征&#xff08;指标&#xff09;&#xff0c;从而提高模型的性能并减少过拟合。本文将介绍如何使用 Python 的 Seaborn 和 Ma…
阅读更多...
Vue.js 组件开发教程：从基础到进阶

Vue.js 组件开发教程：从基础到进阶

Vue.js 组件开发教程：从基础到进阶 引言 在现代前端开发中，Vue.js 作为一款流行的 JavaScript 框架，以其简单易用和灵活性赢得了开发者的青睐。Vue 组件是 Vue.js 的核心概念之一，理解组件的开发和使用对构建复杂的用户界面至关重要。本篇文章将详细介绍 Vue.js 组件的开…
阅读更多...
spygalss cdc 检测的bug（二）

spygalss cdc 检测的bug（二）

当allow_qualifier_merge设置为strict的时候&#xff0c;sg是要检查门的极性的。 如果qualifier和src经过与门汇聚&#xff0c;在同另一个src1信号或门汇聚&#xff0c;sg是报unsync的。 假设当qualifier为0时&#xff0c;0&&src||src1src1&#xff0c;src1无法被gat…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023