二叉树以及堆的实现

树

树的定义及概念

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

  • 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。
  • 除根结点外，其余结点被分成M(M>0) 个互不相交的集合T1、T2、……、Tm ，其中每⼀个集合Ti(1 <= i <= m) 又是⼀棵结构与树类似的⼦树。每棵子树的根结有且只有⼀个前驱，可以有0个或多个后继。因此，树是递归定义的。

在这里插入图片描述
树的性质：

  • 子树不相交
  • 除了根结点外，每个结点有且仅有一个父结点
  • 一棵N个结点的树有N-1条边

树的相关术语

  • 父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图中G为J和k的父结点
  • 子结点/孩子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图中B是A的孩子结点
  • 结点的度：一个结点有几个孩子结点，他的度就是多少；⽐如A的度为3，F的度为0，G的度为2
  • 树的度：⼀棵树中，最大的结点的度称为树的度；如上图树的度为3
  • 叶子结点/终端结点：度为0的结点称为叶结点；如上图中的E和F结点都为叶子结点
  • 分支结点/非终端结点：度不为0的结点；如上图中的B和G结点都为分支结点
  • 兄弟结点：具有相同父结点的结点互称为兄弟结点(亲兄弟)；如上图中的B和C结点为兄弟结点
  • 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
  • 树的高度或深度：树中结点的最大层次；如上图树的高度或深度为4
  • 结点的祖先：从根到该结点所经分支上的所有结点；如上图中A是所有结点的祖先
  • 路径：⼀条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；如上图中A到K的路径为A-C-G-K
  • 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图中所有结点都是A的子孙
  • 森林：由m（m>0） 棵互不相交的树的集合称为森林；

树的表示

孩子兄弟表示法：
树结构相对线性表就比较复杂了，要存储表示起来就比较⿇烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这⾥就简单的了解其中最常用的孩⼦兄弟表示法。

 struct TreeNode 
{ struct Node* child;//左边开始的第⼀个孩⼦结点struct Node* brother;//指向其右边的下⼀个兄弟结点int data;             
};

在这里插入图片描述
在这里插入图片描述

树形结构实际运用场景

文件系统是计算机存储和管理文件的⼀种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。
在这里插入图片描述

二叉树

概念与结构

在树形结构中，我们最常用的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左子树和右子树的⼆叉树组成或者为空。
在这里插入图片描述

二叉树的性质
  • 二叉树不存在度大于2的结点
  • 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

特殊的二叉树

满二叉树

⼀个⼆叉树，如果每一个层的结点数都达到最大值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀
个二叉树的层数为K，且结点总数是2^k-1，则它就是满⼆叉树。
在这里插入图片描述

完全二叉树

完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树而引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当其每一个结点都与深度为K的满⼆叉树中编号从1⾄n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
在这里插入图片描述
性质：

  • 若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有2^(i-1)个结点
  • 若规定根结点的层数为1，则深度为h的⼆叉树的最大结点数是h^2 −1
  • 若规定根结点的层数为1，具有n个结点的满二叉树的深度( h = log2(n+1) log以2为底，n+1 为对数)

二叉树的存储

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

顺序结构

顺序结构存储就是使用数组来存储，⼀般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全⼆叉树更适合使用顺序结构存储。
在这里插入图片描述

链式结构

⼆叉树的链式存储结构是指，用链表来表示⼀棵⼆叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构⼜分为二叉链和三叉链。

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

实现顺序结构二叉树

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

堆的概念与结构

如果有⼀个关键码的集合K = {k0,k1 ,k2 ,…，kn } ，把它的所有元素按完全⼆叉树的顺序存储方式存储，在⼀个⼀维数组中，并满⾜：Ki<= K2∗i+1（K>=i K2∗i+1 且K <=i K2∗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.h、heap.c、test.c

heap.h

我们需要借助数组来实现堆，因此在结构体的定义时，我们选择了动态数组

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int HPDataType;typedef struct Heap
{HPDataType* arr;int size;int capacity;
}HP;//初始化
void HPInit(HP* php);//销毁
void HPDestory(HP* php);//入堆
void HPPush(HP* php, HPDataType x);//出堆
void HPPop(HP* php);//判空
bool HPEmpty(HP* php);//堆头元素
HPDataType HPtop(HP* php);

heap.c

初始化（同顺序表）

#include"heap.h"//初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}

销毁（同顺序表）

void HPDestory(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

入堆

思路：

  1. 判断数组空间是否满了，满了则需要进行扩容
  2. 将数据插入，需要判断该数据是否满足小根堆的特点
  3. 若不满足，则需要将父结点与该结点进行交互，并继续进行判断，从而实现数据向上调整，从而满足小跟读的特点
  4. 将size++

在这里插入图片描述

例如需要在该小根堆中插入数据5，插入完成后跟父结点进行对比，即将5与56进行对比，因为56>5，因此将56与5进行交换
在这里插入图片描述
接着判断插入的5与他的父结点10，接着再进行交换
在这里插入图片描述
发现该结点已经变成根节点，已满足小根堆结点

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 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!");exit(1);}php->capacity = newcapacity;php->arr = tmp;}php->arr[php->size] = x;AdjustUp(php->arr, php->size);php->size++;
}

出堆

思路：

  1. 将根结点与最后的结点进行交换
  2. 将size–
  3. 向下调整，使堆满足小根堆的条件

在这里插入图片描述
例如要对该堆进行出堆操作，则需将56与5进行交换，由于size–，因此5不进入向下调整
在这里插入图片描述
取根节点的子节点，将它的左右孩子结点进行对比，将小的孩子结点与根节点进行交换
在这里插入图片描述
发现满足小根堆的条件，调整结束

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[parent] > arr[child]){swap(&arr[parent], &arr[child]);parent = child;child= parent * 2 + 1;}else{break;}}
}//出堆
void HPPop(HP* php)
{assert(php && php->size);swap(&php->arr[0],&php->arr[php->size-1]);php->size--;AdjustDown(php->arr, 0, php->size);
}

判空

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

寻找堆头元素

HPDataType HPtop(HP* php)
{assert(php && php->size);return php->arr[0];
}

test.c

#include"heap.h"void Test()
{HP hp;HPInit(&hp);int arr[] = { 17,20,10,13,19,15 };for (int i = 0; i < 6; i++){HPPush(&hp, arr[i]);}while (!HPEmpty(&hp)){printf("%d ", HPtop(&hp));HPPop(&hp);}HPDestory(&hp);
}int main()
{Test();return 0;
}

请添加图片描述
入堆操作成功
请添加图片描述
出堆成功

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

不支持jdk8的jenkins部署jdk8项目

不支持jdk8的jenkins部署jdk8项目

1、背景 目前最新的jenkins必须基于jdk8以上&#xff0c;才能安装。jenkins最新的插件部分也不支持jdk8了。 2、全局工具配置 配置一个jdk8 配置一个jdk8以上的版本&#xff0c;如jdk17 3、部署maven项目 jdk17项目 可以直接使用maven插件&#xff0c;部署。 jdk8项目 由…
阅读更多...
01-调试开发k8s

01-调试开发k8s

使用 Docker 构建 Kubernete 官方 release 是使用 Docker 容器构建的。要使用 Docker 构建 Kubernetes&#xff0c;请遵循以下说明: Requirements docker Key scripts 以下脚本位于 build/ 目录中。请注意&#xff0c;所有脚本都必须从 Kubernetes 根目录运行 build/run.…
阅读更多...
MySQL环境的配置文件json

MySQL环境的配置文件json

突然了解到&#xff0c;使用json文件去进行环境的配置&#xff0c;这样修改参数的时候就只需要去改json文件中的内容&#xff0c;不需要去修改代码中的内容&#xff0c;其他人的MySQL和我的MySQL也不同&#xff0c;这时其他人只需要修改json文件中的内容&#xff0c;清晰明了&a…
阅读更多...
代码随想录||day25 非递减子序列，全排列问题

代码随想录||day25 非递减子序列，全排列问题

491非递减子序列 力扣题目链接 题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素&#xff0c;如出现两个整数相等&#x…
阅读更多...
双盲插便携屏方案：LDR6020系列便携显示

双盲插便携屏方案：LDR6020系列便携显示

在当今这个追求高效与便携的时代&#xff0c;电子设备尤其是便携式显示器&#xff08;Portable Monitor&#xff09;的需求日益增长&#xff0c;成为商务人士、设计师、游戏玩家及移动办公族的理想伴侣。其中&#xff0c;6020系列便携屏以其卓越的显示效果、紧凑的机身设计赢得…
阅读更多...
基于YOLO系列便捷式代码创新

基于YOLO系列便捷式代码创新

目标检测 YOLOv5 与 YOLOv7 系列详细介绍 YOLOv5 详细介绍 版本与特点 网络结构 技术亮点 YOLOv7 详细介绍 主要贡献 网络结构 技术亮点 性能对比 基于YOLOv5和YOLOv7系列的多方面创新方法 融合BiFormer注意力机制 融合SImAM注意力机制 CBAM注意力机制 DBB多分枝模块 LSKA注意力…
阅读更多...
NumpyPandas：pandas库的安装，不同对象的建立，文件的导入和了解数据

NumpyPandas：pandas库的安装，不同对象的建立，文件的导入和了解数据

目录 前言 一、Pandas库的安装 二、不同对象的建立 1.Series对象的创建 1.用index方法指定索引 2.在创建的时候就指定索引 3.使用字典的方式创建 4.将一个常量与index一起传入创建 5.输出值和索引 2.DataFrame对象的创建 1.不指定列名则以键当列名 行索引为默认值 …
阅读更多...
Hadoop3.3.5的安装与单机/伪分布式配置

Hadoop3.3.5的安装与单机/伪分布式配置

文章目录 一、安装须知二、安装jdk三、安装shh四、安装配置hadoop五、运行hadoop 一、安装须知 本次安装的Hadoop版本为hadoop3.3.5。 在这之前完成了VMware虚拟软件的安装&#xff0c;并安装了Ubuntu22.04&#xff0c;在这基础上进行相关配置。 二、安装jdk 在Ubuntu中使用…
阅读更多...
MySQL查询执行（一）：count执行慢

MySQL查询执行（一）：count执行慢

查询处理器 MySQL查询处理器是MySQL数据库服务器的组件&#xff0c;它负责执行SQL查询。查询处理器的主要任务是解析查询&#xff08;把用户提交的SQL查询转换为可以被数据库引擎理解和执行的数据操作指令序列&#xff09;&#xff0c;生成查询计划&#xff0c;然后执行该计划。…
阅读更多...
C++程序的UI界面闪烁问题的解决办法总结

C++程序的UI界面闪烁问题的解决办法总结

Windows C++程序复杂的UI界面要使用多种绘图技术（使用GDI、GDI+、ddraw、D3D等绘图），并要贴图去美化，在窗口移动或者改变大小的时候可能会出现闪烁。下面罗列一下UI界面产生闪烁的几种可能的原因，并给出相应的解决办法。 1、原因一 如果熟悉显卡原理的话，调用GDI函数向屏…
阅读更多...
JVM系列(三) -类加载器及双亲委派模型介绍

JVM系列(三) -类加载器及双亲委派模型介绍

在之前的文章中&#xff0c;介绍了类的加载过程中&#xff0c;我们有提到在加载阶段&#xff0c;通过一个类的全限定名来获取此类的二进制字节流操作&#xff0c;其实类加载器就是用来实现这个操作的。 在虚拟机中&#xff0c;任何一个类&#xff0c;都需要由加载它的类加载器…
阅读更多...
《Milvus Cloud向量数据库指南》——Milvus Cloud不同场景下的部署形态选型

《Milvus Cloud向量数据库指南》——Milvus Cloud不同场景下的部署形态选型

不同场景下的部署形态选型 一般说选型肯定离不开阶段。用到向量数据库的应用基本有这么几个阶段： AI 应用的快速原型构建。比如你在做一个 AI 个人助手、一个小的搜索引擎原型、一个端到端的 RAG 原型，这类项目的迭代速度是很关键的，而且原型构建期不需要关心性能或者稳定性…
阅读更多...
暑假第二周任务——3Gshare的仿写

暑假第二周任务——3Gshare的仿写

3GShare的仿写 登陆注册页面 这个界面的UI比较简单&#xff0c;比较困难的地方在于限制我们的输入长度以及我们输入的字符类型。 在这里我是通过在textField的代理中设计限定输入字符的内容&#xff0c;从而实现限制输入长度和限制输入字符的内容&#xff0c;下面给出相关的代…
阅读更多...
Day24｜二叉树 PART08

Day24｜二叉树 PART08

235. 二叉搜索树的最近公共祖先 与236类似但可以利用二叉搜索树的性质来做 二叉搜索树&#xff1a;左子 小于头 小于右子 &#xff08;怪怪的 感觉是不是先记住比较好&#xff09;&#xff08;而且也没太理解二叉搜索树的规律&#xff09; 大体思路&#xff1a;从上到下遍历&a…
阅读更多...
html 解决tooltip宽度显示和文本任意位置换行文本显示问题

html 解决tooltip宽度显示和文本任意位置换行文本显示问题

.el-tooltip__popper {max-width: 480px;white-space: break-spaces; /* 尝试不同的white-space属性值 */word-break:break-all; }
阅读更多...
干货：three.js中的六大光源的知识点。

干货：three.js中的六大光源的知识点。

我们在二维屏幕中感知三维场景的一个最重要的要素就是光&#xff0c;光和光源是three.js中一个非常重要的知识点。本文想借着这个话题&#xff0c;为老铁们分享以下六大光源知识点&#xff1a;环境光、点光源、聚光灯、方向光、半球光、平面光。 一、点光源 在 Three.js 中&a…
阅读更多...
模拟string(四)详解

模拟string(四)详解

目录 判断string大小关系bool operator(const string&s1,const string s2)代码 bool operator<(const string& s1, const string& s2)代码 bool operator<(const string& s1, const string& s2)代码 bool operator>(const string& s1, const …
阅读更多...
Stable Diffusion WebUI本地环境搭建

Stable Diffusion WebUI本地环境搭建

一、项目代码下载 git clone https://github.com/AUTOMATIC1111/stable-diffusion-webui 二、环境配置 conda create --n stafu python3.10.6 实际上跟自己创建的环境没有关系&#xff0c;项目启动会自动复制这个环境&#xff0c;之后项目根据这个基础环境构建 也可以在自己…
阅读更多...
机器学习——第一章 绪论

机器学习——第一章 绪论

目录 1. 1 引言 1. 2 基本术语 1.3 假设空间 1.4 归纳偏好 1. 1 引言 机器学习致力于研究如何通过计算的手段&#xff0c;利用经验来玫善系统自身的性能在计算机系统中&#xff0c;"经验"通常以"数据"形式存在&#xff0c;因此&#xff0c;机器学习所研…
阅读更多...
由字节对齐引发的一场“血案“

由字节对齐引发的一场“血案“

最近在搞个网络通信协议&#xff0c; 采用socket udp传输&#xff0c; 运行时&#xff0c;居然报段错误了&#xff0c; 经过debug&#xff0c;发现居然是因为字节对齐问题导致的。 这个问题在实现通信协议&#xff0c;是经常会遇到的问题&#xff0c; 为了方便读者理解&am…
阅读更多...
最新文章

Copyright @ 2022~2023