数据结构——二叉树——堆（1）

今天，我们来写一篇关于数据结构的二叉树的知识。

在学习真正的二叉树之前，我们必不可少的先了解一下二叉树的相关概念。

一：树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的
 

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

除了根结点外，每个结点有且仅有一个父结点

一颗N节点的树又N-1条边
 

下面我们来具体给出树的相关名词：

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：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.二叉树不存在度大于2的结点
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

3. 存在情况：

接下来，我们认识

特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

 证明：满二叉树中高度为h的有多少个结点？

完全二叉树：前h-1都是满的
最后一层要求从左到右是连续的

高度为h的完全二叉数，节点数量的范围是[2^(h-1),2^h-1]

由上面知道满二叉树为2^h-1.

根据完全二叉树的定义

2^(h-1)-1----不算最后一层的。然后再算最后一层：2^(h-1)-1+1==2^(h-1)

所以，它的范围：[2^(h-1),2^h-1]。

此外，对任何一颗二叉树，如果度为0的叶结点个数为n0，度为2的分支节点为2 ，则由n0=n2+1.

结论：度为0的永远比度为2的多1。

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，

我们知道：顺序表是都一样的，实际上就是数组嘛
而链表不一样，我们通常用箭头那些是想象出来的，实际上并没有箭头的。

同样，二叉树也是：

逻辑结构  想象出来的

物理结构  实实在在内存中是如何存储的

反向过来，你把这棵树的一层一层的值依次往数组里面存储

如下图：

逻辑结构：（想象成这样）

物理结构：（实际就是数组） 

  

另外，我们平时画图的时候，很麻烦画出第一张图那么标准，其实，我们也是可以画出这样子

简便：

 通过观察上面得出的规律：

表示二叉树的值在数组位置中的父子下标关系

parent=（child-1）/2

leftchlid=parent*2+1
rightchlid=parent*2+2

注意，这里必须是从0开始，不然就乱了

有人会问了，能不能在完全二叉树那里使用呢？


这里用数组存储完全二叉数，有局限不适合。

因为浪费很多空间，数组存储表示二叉树只适合完全二叉树。

好了，有了上面的铺垫后，现在让我们来实现一下堆。

堆

概念：

什么是堆呢？

我们将堆分为大堆和小堆

小堆

大堆：

 

在写堆时，底层代码实际就是数组
注意：堆不是排序，堆只规定父亲的大小，并没有规定它的左右孩子的大小

插入时，可能会影响部分祖先。
实际控制的是数组，写的时候把它想象成树

一：定义结构体

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

1.需要一个数组

2.要算出数组的大小

3.最大容量

二：初始化部分

void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}

这里初始化跟之前的都差不多。

1.创建数组，用malloc

2.初始化size为0；

3.因为上面创建了数组：4个位置，所以初始化时的最大容量为4。

三：销毁部分

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

1.置空，置零就可以了。

四：Push部分

首先，我们得思考一下，堆咋push的。

由于本质上是数组，所以我们push在数组的最后那里插。

假如在下面数组push一个数字60.

因此我们会写成这样一个代码：

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity*2);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;调整部分下面有讲AdjustUp(php->a, php->size - 1);
}

但是呢，如果是像上面一样push了一个数字的话，堆就乱了：

变成了

 面对这种问题，我们又该怎么办呢？

这里我们使用一种叫向上调整法解决这种问题：

我们以大堆来举例子：

我们发现上面是不是将30和60的位置交换了，就可以重新变成大堆了？

那么，我们又是怎么变成这一步的呢？

不能发现，你看

1.将分为左孩子和右孩子和根三部分。

2.比较左孩子和右孩子，拿出大的孩子，再跟根比较。

3.如果大的孩子的数字大于根，就交换。反之不换。

对上述做法叫做向上调整法。

对此我们写一个函数：

向上调整部分

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while(child > 0){if (a[child] > a[parent]){交换Swap(&a[child], &a[parent]);更新child = parent;parent = (child - 1) / 2;}else{break;}}
}

 解读：

除了child这个位置，前面数据构成堆

1.我们是不是得找到父亲结点。上面我们已经给出了父亲与孩子之间的公式变换了

2.由于交换这个代码内容在后面也是常用到的，所以我们单独封装一个函数

交换部分

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}

3.这样容易忽略的问题是：

while的条件：弄成   while(child > 0)   而不要弄成while (parent >= 0)

这里看似都没有问题运行时，但是会不好。

parent >= 0，意味着parent<0才会中止，但是，parent会小于0吗？不会，因为这里最差的情况就是孩子等于0.

parent = (child - 1) / 2;即就是-1/2，按理是0.5，但是这里是整形，所以还是0，还是会进入循环。

但是呢？这个程序不会死循环，parent=0时，进入循环，但是它不满足if (a[child] > a[parent])条件，所以还是会到达break。

所以能正常跑，但是不好，最好用child>0.

删除部分

void HeapPop(HP* php)
{assert(php);后面讲到assert(!HeapEmpty(php));// 删除数据Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

堆的删除部分，有人可能会想直接这样删

但是，接下来的堆就会变成这样：

直接挪动删除 ：

1.效率低下。

2.父子兄弟关系全乱了。

 那么，我们想到用间接的方法来解决这种问题：

1.我们先把第一个和最后一个交换。

2.删除最后一个。

3.接着向下调整法。

1）什么是向下调整法，即从上面往下调

1.找到孩子中大的数字，与父亲比较，孩子大的就交换。反之不交换

向下调整部分

void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩子中大的那一个if (child + 1 < n && a[child+1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

 1.这里采用的是假设左孩子大，然后再循环里面再弄个if语句，如果右孩子大的话，就交换变成右孩子。（因为左右孩子再邻位，相差1）

2.接着再比较父亲结点，与大的孩子，大就交换，再更新父亲结点和孩子结点。反之就break，跳出循环。

返回顶位置

HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}

判断空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

返回大小

int HeapSize(HP* php)
{assert(php);return php->size;
}

好了，最后

附上总代码

Heap.h部分

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int HPTypeData;
typedef struct Heap
{HPTypeData* a;int size;int capacity;}Heap;void HPInit(Heap* php);
void HPDestory(Heap* php);
void HPPush(Heap* php, HPTypeData x);
void HPPop(Heap* php);
HPTypeData HPtop(Heap* php);
bool HPEmpty(Heap* php);
int HPSize(Heap* php);

Heap.c部分

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"void HPInit(Heap* php)
{assert(php);php->a =(HPTypeData*)malloc(sizeof(HPTypeData)*4);if (php->a == NULL){perror("malloc fail");return;}php->capacity = 4;php->size = 0;
}
void HPDestory(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}void Swap(HPTypeData* p1,HPTypeData* p2)
{HPTypeData temp = *p1;*p1 = *p2;*p2 = temp;
}
void Adjustup(HPTypeData* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent= (child - 1) / 2;}else{break;}}
}
void HPPush(Heap* php, HPTypeData x)
{assert(php);if (php->a == php->capacity){HPTypeData* temp = (HPTypeData*)realloc(php->a, sizeof(HPTypeData) * php->capacity * 2);if (temp == NULL){perror("realloc fail");return;}php->a = temp;php->capacity *= 2;}php->a[php->size] = x;php->size++;//Adjustup(php->a,php->a[php->size-1]);Adjustup(php->a,php->size-1);}Adjustdown(HPTypeData* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[parent],&a[child]);parent = child;child= parent * 2 + 1;}else{break;}}
}
void HPPop(Heap* php)
{assert(php);assert(!HPEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;Adjustdown(php->a, php->size, 0);
}
HPTypeData HPtop(Heap* php)
{assert(php);return php->a[0];
}
bool HPEmpty(Heap* php)
{assert(php);return php->size == 0;
}
int HPSize(Heap* php)
{assert(php);return php->size;
}

test.c部分

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"//int main()
//{
//	HP hp;
//	HeapInit(&hp);
//	HeapPush(&hp, 4);
//	HeapPush(&hp, 18);
//	HeapPush(&hp, 42);
//	HeapPush(&hp, 12);
//	HeapPush(&hp, 21);
//	HeapPush(&hp, 3);
//	HeapPush(&hp, 5);
//	HeapPush(&hp, 5);
//	HeapPush(&hp, 50);
//	HeapPush(&hp, 5);
//	HeapPush(&hp, 5);
//	HeapPush(&hp, 15);
//	HeapPush(&hp, 5);
//	HeapPush(&hp, 45);
//	HeapPush(&hp, 5);
//
//	int k = 0;
//	scanf("%d", &k);
//	while (!HeapEmpty(&hp) && k--)
//	{
//		printf("%d ", HeapTop(&hp));
//		HeapPop(&hp);
//	}
//	printf("\n");
//
//	return 0;
//}// 排升序 -- 建大堆
void HeapSort(int* a, int n)
{// 建堆 -- 向上调整建堆for (int i = 1; i < n; ++i){AdjustUp(a, i);}// 自己先实现}int main()
{int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3}; // 对数组排序HeapSort(a, 10);return 0;
}

最后，到了本次鸡汤部分：

小小的人，有大大的梦想！干！

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

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

相关文章

Vue入门(Vue基本语法、axios、组件、事件分发）

Vue入门(Vue基本语法、axios、组件、事件分发）

Vue入门 Vue概述 Vue (读音/vju/&#xff0c;类似于view)是一套用于构建用户界面的渐进式框架&#xff0c;发布于2014年2月。与其它大型框架不同的是&#xff0c;Vue被设计为可以自底向上逐层应用。Vue的核心库只关注视图层&#xff0c;不仅易于上手&#xff0c;还便于与第三…
阅读更多...
数据结构：二叉树—面试题（二）

数据结构：二叉树—面试题（二）

1、二叉树的最近公共祖先 习题链接https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 描述&#xff1a; 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点…
阅读更多...
使用python-docx包进行多文件word文字、字符批量替换

使用python-docx包进行多文件word文字、字符批量替换

1、首先下载pycharm。 2、改为中文。 3、安装python-docx包。 搜索包名字&#xff0c;安装。 4、新建py文件&#xff0c;写程序。 from docx import Documentdef replace1(array1):# 替换词典&#xff08;标签值按实际情况修改&#xff09;dic {替换词1: array1[0], 替换…
阅读更多...
[操作系统] 进程地址空间管理

[操作系统] 进程地址空间管理

虚拟地址空间的初始化 缺页中断 缺页中断的概念 缺页中断&#xff08;Page Fault Interrupt&#xff09; 是指当程序访问的虚拟地址在页表中不存在有效映射&#xff08;即该页未加载到内存中&#xff09;时&#xff0c;CPU 会发出一个中断信号&#xff0c;请求操作系统加载所…
阅读更多...
万字长文总结前端开发知识---JavaScriptVue3Axios

万字长文总结前端开发知识---JavaScriptVue3Axios

JavaScript学习目录 一、JavaScript1. 引入方式1.1 内部脚本 (Inline Script)1.2 外部脚本 (External Script) 2. 基础语法2.1 声明变量2.2 声明常量2.3 输出信息 3. 数据类型3.1 基本数据类型3.2 模板字符串 4. 函数4.1 具名函数 (Named Function)4.2 匿名函数 (Anonymous Fun…
阅读更多...
【Linux】21.基础IO（3）

【Linux】21.基础IO（3）

文章目录 3. 动态库和静态库3.1 静态库与动态库3.2 静态库的制作和使用原理3.3 动态库的制作和使用原理3.3.1 动态库是怎么被加载的 3.4 关于地址 3. 动态库和静态库 3.1 静态库与动态库 静态库&#xff08;.a&#xff09;&#xff1a;程序在编译链接的时候把库的代码链接到可…
阅读更多...
Linux系统之gzip命令的基本使用

Linux系统之gzip命令的基本使用

Linux系统之gzip命令的基本使用 一、gzip命令简介二、gzip命令使用帮助2.1 help帮助信息2.2 选项解释 三、gzip命令的基本使用3.1 压缩文件3.2 保留原始文件3.3 解压文件3.4 查看压缩信息3.5 标准输出/输入3.6 批量处理文件3.7 递归解压缩目录3.8测试压缩文件完整性 四、注意事…
阅读更多...
【Matlab高端绘图SCI绘图模板】第05期 绘制高阶折线图

【Matlab高端绘图SCI绘图模板】第05期 绘制高阶折线图

1.折线图简介 折线图是一个由点和线组成的统计图表&#xff0c;常用来表示数值随连续时间间隔或有序类别的变化。在折线图中&#xff0c;x 轴通常用作连续时间间隔或有序类别&#xff08;比如阶段1&#xff0c;阶段2&#xff0c;阶段3&#xff09;。y 轴用于量化的数据&#x…
阅读更多...
免费SSL证书申请，springboot 部署证书

免费SSL证书申请，springboot 部署证书

申请免费域名证书,SSL证书(一共有两个有用&#xff0c;一个是私钥private.key 另一个是certificate.crt) 1、打开网址 申请免费域名证书,SSL证书 2、选择生成CSR 3、生成以后点击下一步&#xff08;private key 有用 ) ​​​​​​​ 4、这里选择 Cname域名解析验证 5、…
阅读更多...
Java 大视界 -- Java 大数据中的隐私增强技术全景解析（64）

Java 大视界 -- Java 大数据中的隐私增强技术全景解析（64）

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…
阅读更多...
深度学习项目--基于LSTM的糖尿病预测探究(pytorch实现)

深度学习项目--基于LSTM的糖尿病预测探究(pytorch实现)

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 前言 LSTM模型一直是一个很经典的模型&#xff0c;一般用于序列数据预测&#xff0c;这个可以很好的挖掘数据上下文信息&#xff0c;本文将使用LSTM进行糖尿病…
阅读更多...
js/ts数值计算精度丢失问题及解决方案

js/ts数值计算精度丢失问题及解决方案

文章目录 概念及问题问题分析解决方案方案一方案二方案其它——用成熟的库 概念及问题 js中处理浮点数运算时会出现精度丢失。js中整数和浮点数都属于Number数据类型&#xff0c;所有的数字都是以64位浮点数形式存储&#xff0c;整数也是如此。所以打印x.00这样的浮点数的结果…
阅读更多...
vite环境变量处理

vite环境变量处理

环境变量: 会根据当前代码环境产生值的变化的变量就叫做环境变量 代码环境: 开发环境测试环境预发布环境灰度环境生产环境 举例: 百度地图 SDK,小程序的SDK APP_KEY: 测试环境和生产环境还有开发环境是不一样的key 开发环境: 110 生产环境:111 测试环境: 112 我们去请求第三…
阅读更多...
Android GLSurfaceView 覆盖其它控件问题 (RK平台)

Android GLSurfaceView 覆盖其它控件问题 (RK平台)

平台 涉及主控: RK3566 Android: 11/13 问题 在使用GLSurfaceView播放视频的过程中, 增加了一个播放控制面板, 覆盖在视频上方. 默认隐藏setVisibility(View.INVISIBLE);点击屏幕再显示出来. 然而, 在RK3566上这个简单的功能却无法正常工作. 通过缩小视频窗口可以看到, 实际…
阅读更多...
Linux 环境变量

Linux 环境变量

目录 一、环境变量的基本概念 1.常见环境变量 2.查看环境变量方法 ​3.几个环境变量 环境变量&#xff1a;PATH 环境变量&#xff1a;HOME 环境变量&#xff1a;SHELL 二、和环境变量相关的命令 三、库函数getenv&#xff0c;setenv 四、环境变量和本地变量 五、命令行…
阅读更多...
Redis实战（黑马点评）——涉及session、redis存储验证码，双拦截器处理请求

Redis实战（黑马点评）——涉及session、redis存储验证码，双拦截器处理请求

项目整体介绍 数据库表介绍 基于session的短信验证码登录与注册 controller层 // 获取验证码PostMapping("code")public Result sendCode(RequestParam("phone") String phone, HttpSession session) {return userService.sendCode(phone, session);}// 获…
阅读更多...
MYSQL数据库 - 启动与连接

MYSQL数据库 - 启动与连接

MYSQL数据库的启动&#xff1a; 一 在cmd控制界面以管理员身份运行 执行语句: net start mysql80 net stop mysql80 二 MYSQL数据库客户端建立连接&#xff1a; 1 该种方法是使用windows系统的cmd界面&#xff0c;需要配置相关路径path 2 使用MYSQL自带的
阅读更多...
【Salesforce】审批流程，代理登录 tips

【Salesforce】审批流程，代理登录 tips

审批流程权限 审批流程权限问题解决方案代理登录代理登录后Logout 审批流程权限 前几天&#xff0c;使用审批流程&#xff0c;但是是两个sandbox&#xff0c;同样的配置&#xff0c;我有管理员权限。但是profile不是管理员&#xff0c;只是通过具备管理员权限的permission set…
阅读更多...
RDMA 工作原理 | 支持 RDMA 的网络协议

RDMA 工作原理 | 支持 RDMA 的网络协议

注&#xff1a;本文为 “RDMA” 相关文章合辑。 英文引文机翻未校。 图片清晰度受引文所限。 Introduction to Remote Direct Memory Access (RDMA) Written by: Dotan Barak on March 31, 2014.on February 13, 2015. What is RDMA? 什么是 RDMA&#xff1f; Direct me…
阅读更多...
hexo + Butterfly搭建博客

hexo + Butterfly搭建博客

Hexo‌是一个基于Node.js的静态网站生成器&#xff0c;主要用于快速搭建博客和个人网站。它使用Markdown语法编写文章&#xff0c;能够迅速生成静态页面并部署到服务器上。 配置node 使用nvm安装node(v16.13.2)后配置镜像 安装并使用node&#xff1a; nvm install 16.13.2 n…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023