数据结构---二叉树(顺序结构),堆(上)

 树

树的概念与结构

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

PS

  • 有⼀个特殊的结点,称为根结点,根结点没有前驱结点。
  • 除根结点外,其余结点被分成 M(M>0) 个互不相交的集合 T1T2……Tm ,其中每⼀个集合Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱,可以0 个或多个后继。因此,树是递归定义的。
注意:
  • ⼦树是不相交的
  • 除了根结点外,每个结点有且仅有⼀个⽗结点
  • ⼀棵N个结点的树有N-1条边
  • 树形结构中,⼦树之间不能有交集,否则就不是树形结构(如下图)

树的相关术语

  • ⽗结点/双亲结点:若⼀个结点含有⼦结点,则这个结点称为其⼦结点的⽗结点; 如上图:A是B的⽗结点
  • ⼦结点/孩⼦结点:⼀个结点含有的⼦树的根结点称为该结点的⼦结点; 如上图:B是A的孩⼦结点
  • 结点的度:⼀个结点有⼏个孩⼦,他的度就是多少;⽐如A的度为6,F的度为2,K的度为0
  • 树的度:⼀棵树中,最⼤的结点的度称为树的度; 如上图:树的度为 6
  • 叶⼦结点/终端结点:度为 0 的结点称为叶结点; 如上图: B、C、H、I... 等结点为叶结点
  • 分⽀结点/⾮终端结点:度不为 0 的结点; 如上图: D、E、F、G... 等结点为分⽀结点
  • 兄弟结点:具有相同⽗结点的结点互称为兄弟结点(亲兄弟); 如上图: B、C 是兄弟结点
  • 结点的层次:从根开始定义起,根为第 1 层,根的⼦结点为第 2 层,以此类推;
  • 树的⾼度或深度:树中结点的最⼤层次; 如上图:树的⾼度为 4
  • 结点的祖先:从根到该结点所经分⽀上的所有结点;如上图: A 是所有结点的祖先
  • 路径:⼀条从树中任意节点出发,沿⽗节点-⼦节点连接,达到任意节点的序列;⽐如A到Q的路径为: A-E-J-Q;H到Q的路径H-D-A-E-J-Q
  • ⼦孙:以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙:如上图:所有结点都是A的⼦孙
  • 森林:由 m(m>0) 棵互不相交的树的集合称为森林;

树的表示

孩子兄弟表示法:
树结构相对线性表就⽐较复杂了,要存储表⽰起来就⽐较⿇烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表⽰⽅式如:双亲表⽰法,孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表示法。
struct TreeNode
{
        struct TreeNode* child; // 左边开始的第⼀个孩⼦结点
        struct TreeNode* brother; // 指向其右边的下⼀个兄弟结点
        int data; // 结点中的数据域
};
假设我们有下图这样的二叉树,A是根节点,指向它左边的第一个孩子节点B,B在指向它右边的兄弟节点。这一层结束后,开始第三层,B再指向它的孩子节点D,D再指向它的兄弟节点E,F,E再指向它的左孩子H,H在指向它的兄弟节点I,C没有左孩子所以直接指向右孩子。

树形结构实际运⽤场景

⽂件系统是计算机存储和管理⽂件的⼀种⽅式,它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中,树结构被⼴泛应⽤,它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。

二叉树

概念与结构

在树形结构中,我们最常⽤的就是⼆叉树,⼀棵⼆叉树是结点的⼀个有限集合,该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。
从上图可以看出⼆叉树具备以下特点:
  • ⼆叉树不存在度⼤于 2 的结点
  • ⼆叉树的⼦树有左右之分,次序不能颠倒,因此⼆叉树是有序树
注意:对于任意的⼆叉树都是由以下⼏种情况复合⽽成的

特殊的⼆叉树

满⼆叉树

⼀个⼆叉树,如果每⼀个层的结点数都达到最⼤值,则这个⼆叉树就是满⼆叉树。也就是说,如果⼀个⼆叉树的层数为 K ,且结点总数是 2 k − 1 ,则它就是满⼆叉树。

完全⼆叉树

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

二叉树的性质

根据满⼆叉树的特点可知:
  • 若规定根结点的层数为 1 ,则⼀棵⾮空⼆叉树的第i层上最多有 2 i−1 个结点
  • 若规定根结点的层数为 1 ,则深度为 h 的⼆叉树的最⼤结点数是 2 h − 1
  • 若规定根结点的层数为 1 ,具有 n 个结点的满⼆叉树的深度 h = log2 (n + 1) ( log 以2为底, n+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 +2 ),i = 0、 1 2... ,则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆,根结点最⼩的堆叫做最⼩堆或⼩根堆。
堆具有以下性质
  • 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值;
  • 堆总是⼀棵完全⼆叉树。

⼆叉树性质

对于具有 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 否则⽆右孩⼦

堆的实现

和往常一样,我们先创建Heap项目,在其中创建三个文件分别是头文件 Heap.h, 源文件Heap.c, test.c

堆的结构

这里我们实现的是二叉树的顺序结构,所以定义一个数组。这个数组的空间大小一直在变化所以我么定义一个capacity记录数组的容量大小。数组中并不一定所有数据都是有效的,所以我们再定义一个size用来记录数组中有效数据的个数。
代码:
//堆的结构
typedef int HPDataType;
typedef struct Heap {HPDataType* arr;int size;int capacity;
}HP;

堆的初始化

把上述的三个元素,初始化为空。

代码:

//初始化
void HPInit(HP* php) {assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
堆的销毁
销毁的是数组里面动态申请的空间,free完成后,不要忘记把arr置为空!size和capacity也要置为0。
代码:
//销毁堆
void HPDesTroy(HP* php) {if (php->arr) {free(php->arr);}php->arr = NULL;php->size = php->capacity = 0;
}

插入数据

想要插入数据需要先判断空间大小是否足够如果有效的数据个数和空间大小刚好一样说明没有位置了,想要继续插入数据就需要增容。在默认的时候开capacity是零,如果capacity等于零,那我就直接给他四,如果不等于零,我就让他二倍增容。
假设我想要建立一个小堆,我往数组中插入2 和 1,那么此时他就不是小堆。
那么这个时候我要怎么办呢?
我们就要调整堆,使其变成一个小堆。把 1 向上调整,让其与 2 交换位置。那么这种调整的方法我们称为 向上调整算法
向上调整算法

假设现在我们要把10插入到数组中。直接插入数组中,他在最末尾的位置。那么此时我们应该怎么调整呢?

我们把10(孩子)直接和它的父节点比较,谁小谁往上放,10 就和 28 交换位置。再继续和它的父节点比较10 < 18,继续向上调整,直到找到比10小的父亲节点或孩子节点遍历到下表为 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);if (php->size == php->capacity) {int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType)*newCapacity);if (tmp == NULL) {perror("realloc fail\n");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size] = x;//向上调整ADjustUP(php->arr, php->size);++php->size;
}

删除堆顶数据

假设我们有一个上图的一个小堆,我想删除堆顶数据10,如果我直接删除 10 ,那么这个堆就会变成下图
这个堆中的所有父子关系都会发生改变。那我们应该怎么办呢?
我们可以将堆顶和最后一个数据交换,让10 与 70 交换,然后把最后一个数据(10)删除,再让 70 回到它原有的位置。这样就不会破坏堆的结构。 
删除堆顶后,该堆是下图的状态。当前堆不在是小堆,那我们再把它变成小堆不就行了。
我们让 70 (父节点)与它左右孩子中小的那一个交换,如此循环,直到该节点没有下一个节点或它比他的孩子小,循环停止。那么这种方法我们称为 向下调整算法
向下调整算法有⼀个前提:左右⼦树必须是⼀个堆,才能调整。
向下调整算法步骤
  • 将堆顶元素与堆中最后⼀个元素进⾏交换
  • 删除堆中最后⼀个元素
  • 将堆顶元素向下调整到满⾜堆特性为⽌
向下调整算法代码:
//向下调整
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);
}

获取堆顶数据 

首先需要判断堆为不为空,堆不为空才能取到堆顶数据。堆顶的下标不就是0吗,所以我们直接return数组下标为0的位置就可以了

代码:

//获取堆顶数据
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

测试结果

判空

堆中有效数据个数为0 的时候 数组就是空的。
代码:
// 判空
bool HPEmpty(HP* php) {assert(php);return php->size == 0;
}

求size

直接返回size就是堆中的有效数据个数
代码:
//求size
int HPSize(HP* php) {assert(php);return php->size;
}

全部代码:

Heap.h
#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 HPDesTroy(HP* php);//插入数据
void HPPush(HP* php, HPDataType x);
//删除堆顶数据
void HPPop(HP* php);// 判空
bool HPEmpty(HP* php);
//求size
int HPSize(HP* php);
Heap.c
#include"Heap.h"
//初始化
void HPInit(HP* php) {assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
//销毁堆
void HPDesTroy(HP* php) {if (php->arr) {free(php->arr);}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);if (php->size == php->capacity) {int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType)*newCapacity);if (tmp == NULL) {perror("realloc fail\n");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size] = x;//向上调整ADjustUP(php->arr, php->size);++php->size;
}// 判空
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);
}

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);HPDesTroy(&hp);
}
int main() {test();return 0;
}

祝大家生活愉快。

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

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

相关文章

blender导入的图片渲染看不见,图片预览正常,但渲染不出

在使用Blender时&#xff0c;我们经常会遇到导入图片后在预览渲染中显示&#xff0c;但在实际渲染时图片消失的问题。本文将提供详细的解决方法&#xff0c;帮助大家解决“Blender导入的图片渲染图像不显示”的问题。 问题原因 导入的图片在Blender中只是一张图&#xff0c;并…

【Spring】Spring Web MVC基础入门~(含大量例子)

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 一&#xff1a;什么是Spring Web MVC 1&#xff1a;Servlet 2&#xff1a;总结 二&#xff1a;MVC …

使用 Python 调用云 API 实现批量共享自定义镜像

本文介绍如何通过 Python SDK 调用 API 接口&#xff0c;通过子用户批量共享云服务器自定义镜像。若您具备类似需求&#xff0c;或想了解如何使用 SDK&#xff0c;可参考本文进行操作。 前提条件 已创建子用户&#xff0c;并已具备云服务器及云 API 所有权限。 创建子用户请…

element-plus按需引入报错AutoImport is not a function

官网文档&#xff1a;快速开始 | Element Plus webpack配置 // webpack.config.js const AutoImport require(unplugin-auto-import/webpack) const Components require(unplugin-vue-components/webpack) const { ElementPlusResolver } require(unplugin-vue-components…

在 Vue 中实现与优化轮询技术

轮询&#xff08;Polling&#xff09;是一种计算机程序反复检查某个条件或状态的技术&#xff0c;通常用于在一定的时间间隔内不断请求信息或更新数据状态。轮询被广泛应用于前端开发&#xff08;例如实现页面实时更新&#xff09;、后端服务监控、网络设备状态检查等场景。 1…

内核调度抢占模式——voluntary和full对比

一、背景 在之前的内核调度子系统专栏里&#xff0c;我们已经把调度有关的如CFS调度/RT调度&#xff0c;调度时间片&#xff0c;调度时延&#xff0c;cfs唤醒抢占特性&#xff0c;这些基本概念和细节都讲了一遍。其实这些细节更多的是帮助我们理解调度系统是如何运作的&#x…

【网络原理】关于HTTP状态码以及请求的构造的哪些事

前言 &#x1f31f;&#x1f31f;本期讲解关于HTTP协议的重要的机制~~~ &#x1f308;感兴趣的小伙伴看一看小编主页&#xff1a;GGBondlctrl-CSDN博客 &#x1f525; 你的点赞就是小编不断更新的最大动力 &#x1f386;那么废话不…

Day13杨辉三角

给定一个非负整数 numRows&#xff0c;生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中&#xff0c;每个数是它左上方和右上方的数的和。 class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> res new Arra…

Docker基本概念汇总(更全面了解Docker)

Docker是一种开源的平台&#xff0c;用于开发、部署和运行应用程序。它通过“容器”技术实现了轻量级虚拟化&#xff0c;使应用程序和其依赖项能够一起打包、部署并运行。以下是Docker基本概念的详细解释。 图片来源网络 1. Docker 容器&#xff08;Container&#xff09; 容…

OpenCV视觉分析之目标跟踪(8)目标跟踪函数CamShift()使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 找到物体的中心、大小和方向。 CamShift&#xff08;Continuously Adaptive Mean Shift&#xff09;是 OpenCV 中的一种目标跟踪算法&#xff0…

【每日刷题】Day151

【每日刷题】Day151 &#x1f955;个人主页&#xff1a; 开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 【模板】01背包_牛客题霸_牛客网 【模板】01背包_牛客题霸_牛客网 //思路&#xff1a;动态规划 #incl…

学习Vue之商城案例(代码+详解)

目前&#xff0c;我们学习Vue的一些基础的知识&#xff0c;那么就让我们做一个像下图这样简单的商城案例吧。 目录 通过脚手架创建项目 安装axios和bootstrap组件 安装axios和bootstrap 在保存的时候不进行格式化校验 初步定义App.vue文件 初步渲染组件页面 根据接口渲染…

【测试】【Debug】vscode中同一个测试用例出现重复

这种是正常的情况 当下面又出现一个 类似python_test->文件夹名->test_good ->test_pad 同一个测试用例出现两次&#xff0c;名称都相同&#xff0c;显然是重复了。那么如何解决&#xff1f; 这种情况是因为在终端利用“pip install pytest”安装 之后&#xff0c;又…

基于C++的决策树C4.5机器学习算法(不调包)

目前玩机器学习的小伙伴&#xff0c;上来就是使用现有的sklearn机器学习包&#xff0c;写两行代码&#xff0c;调调参数就能跑起来&#xff0c;看似方便&#xff0c;实则有时不利于个人能力发展&#xff0c;要知道现在公司需要的算法工程师&#xff0c;不仅仅只是会调参&#x…

Mac解决 zsh: command not found: ll

Mac解决 zsh: command not found: ll 文章目录 Mac解决 zsh: command not found: ll解决方法 解决方法 1.打开bash_profile 配置文件vim ~/.bash_profile2.在文件中添加配置&#xff1a;alias llls -alF键盘按下 I 键进入编辑模式3. alias llls -alF添加完配置后&#xff0c;按…

VBA10-处理Excel的动态数据区域

end获取数据边界 1、基本语法 1-1、示例&#xff1a; 2、配合row和column使用 2-1、示例1 2-2、示例2 此时&#xff0c;不管这个有数值的区域&#xff0c;怎么增加边界&#xff0c;对应的统计数据也会跟着变的&#xff01;

无人车之路径规划篇

无人车的路径规划是指在一定的环境模型基础上&#xff0c;给定无人车起始点和目标点后&#xff0c;按照性能指标规划出一条无碰撞、能安全到达目标点的有效路径。 一、路径规划的重要性 路径规划对于无人车的安全、高效运行至关重要。它不仅能够提高交通效率&#xff0c;减少交…

【前端基础】CSS基础

目标&#xff1a;掌握 CSS 属性基本写法&#xff0c;能够使用文字相关属性美化文章页。 01-CSS初体验 层叠样式表 (Cascading Style Sheets&#xff0c;缩写为 CSS&#xff09;&#xff0c;是一种 样式表 语言&#xff0c;用来描述 HTML 文档的呈现&#xff08;美化内容&#…

一种高度集成的数字化管理平台:城市管理综合执法系统(源码)

什么是城市管理综合执法系统&#xff1f; 城市管理综合执法系统是一种高度集成的数字化管理平台&#xff0c;它旨在通过整合信息技术资源&#xff0c;实现对城市环境、秩序、设施等多方面的综合管理和高效执法。 城市管理综合执法系统通常包含以下几个核心要素和功能&#xff…

【Python】强大的正则表达式工具:re模块详解与应用

强大的正则表达式工具&#xff1a;re模块详解与应用 在编程和数据处理中&#xff0c;字符串的处理是不可避免的一项任务。无论是从文本中提取信息、验证数据格式&#xff0c;还是进行复杂的替换操作&#xff0c;正则表达式&#xff08;Regular Expression&#xff0c;简称Rege…