当前位置：首页 > news >正文

二叉树_堆

news 来源：原创 2025/5/25 14:46:22

一. 树(非线性结构）

1.1 树的概念与结构

1.2 树的表示

二. 二叉树

2.1 二叉树的概念与结构

2.2 特殊的二叉树

2.3 二叉树的存储结构

三. 实现顺序结构的二叉树

3.1 堆的概念与结构

一. 树(非线性结构）

1.1 树的概念与结构

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

• 有一个特殊的结点，称为根结点，根结点没有前驱结点。

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

上面那个就是一个树的结构，A就是那个特殊的结点，叫做根结点。而且每一个子树的根节点有且只有一个前驱，可以有0个或者多个后继。需要注意的是，树形结构中，子树之间不能有交集，否则就不是树形结构；子树是不相交的（如果存在相交就是图了，图以后得课程会有讲解）；除了根结点外，每个结点有且仅有一个父结点，一棵N个结点的树有N-1条边。

1.2 树的表示

树的相关术语：

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

树的表示：

树的基本形式我们已经知道了，相对于线性结构树的结构确实会复杂很多，我们要如何去表示树？要用什么方法去表示？对于树的表示方法我们其实有很多，比如双亲表示法、孩子表示法、孩子兄弟表示法等，但其实我们最常用的还是孩子兄弟表示法。

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

上面的是我们利用结构体写出的树的结构，利用了孩子兄弟表示法，具体是什么思路，下面我会给大家详细解释，如图：

上面通过图片的形式表示出来，大家可能会更清楚一点，首先树中的每一个结点都是一样的结构，有孩子和兄弟，就拿上图来说，首先A的孩子结点指向B，同时B的兄弟结点指向C，这样就可以满足B和C的父节点是A，与树的形状一致，同理B的孩子结点指向D，D的兄弟结点再指向E，E的兄弟结点再指向F，以此类推，我们就可以利用这个方法完成数的结构了。其实也是很好理解的。

数的实际应用场景：对于数的结构，虽然有些许复杂，但是在实际生活中还是有很多用处的，比如我们最常见的电脑磁盘，每一个文件下可能有多个文件，在这些子文件中可能还有很多文件，这样的结构其实就是和数的结构基本是一致的。

二. 二叉树

2.1 二叉树的概念与结构

数的结构是有些许复杂的，可能每一个结点可能会有不一样数量的孩子结点等，可能数量会非常多，所以我们来介绍一种比较常用的类型，叫做二叉树。

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

从上图可以看出二叉树具备以下特点：

1. 二叉树不存在度大于 2 的结点；

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

对于任何的二叉树都是由下面几种复合而成的：

2.2 特殊的二叉树

满二叉树：

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

完全二叉树：

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

💡 二叉树性质

根据满二叉树的特点可知：

1）若规定根结点的层数为 1 ，则一棵非空二叉树的第i层上最多有 2^( i−1 )^个结点；

2）若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数是 2^h − 1；

3）若规定根结点的层数为 1 ，具有 n 个结点的满二叉树的深度 h = log2 (n + 1) ( log

以2为底， n+1 为对数)；

2.3 二叉树的存储结构

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

顺序结构 ：顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。因为我们知道完全二叉树是一个有序的二叉树，所以我们能根据它的顺序用数组来表述出来，一般我们示从左向右表示。

链式结构 ：二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链表来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。后面会学到高阶数据结构，如红黑树等会用到三叉链。

三. 实现顺序结构的二叉树

3.1 堆的概念与结构

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

堆其实结构上与二叉树是相同的，但是堆有小堆和大堆之分，当孩子结点始终要大于或等于父结点的时候，我们称之为小堆；相反，当父结点始终大于或等于孩子结点的时候，我们称之为大堆；

堆具有以下性质

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

• 堆总是一棵完全二叉树；

💡 二叉树性质

• 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从

0 开始编号，则对于序号为 i 的结点有：

1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，无双亲结点；

2. 若 2i+1<n ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子；

3. 若 2i+2<n ，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子；

本篇主要详细的讲了关于数的概念和结构，只有我们清楚了数的结构，是通过什么方法来实现的，我们在后续的学习中才会更加得心应手，后面一篇我会给大家详细讲解堆的实现，以及堆的向上调整法和向下调整法。

二叉树_堆

目录一. 树(非线性结构） 1.1 树的概念与结构 1.2 树的表示二. 二叉树 2.1 二叉树的概念与结构 2.2 特殊的二叉树 2.3 二叉树的存储结构三. 实现顺序结构的二叉树 3.1 堆的概念与结构一. 树(非线性结构） 1.1 树的概念与结构概念&#xff…...

编程日记 2025/5/25 14:46:22

Java图片拼接

最近遇到一个挺离谱的功能，某个表单只让上传一张图，多图上传会使导出失败。跟开发沟通后表示，这个问题处理不了。我... 遂自己思考，能否以曲线救国的方式拯救一下，即不伤及代码之根本，又能解决燃眉之急。灵…...

编程日记 2025/5/25 0:20:45

使用qemu搭建armv7嵌入式开发环境

目录目录 1 概述 2 环境准备 2.1 vexpress系列开发板介绍 2.2 安装工具 2.2.1 安装交叉工具链 2.2.2 安装qemu 2.2.3 安装其他工具 3 启动uboot 3.1 uboot下载与编译 3.1.1 下载 3.1.2 编译 3.2 使用qemu启动uboot 4 启动kernel 4.1 下载和编译kernel 4.1.1 下…...

编程日记 2025/5/23 23:12:16

新版国标GB28181设备端Android版EasyGBD支持国标GB28181-2022，支持语音对讲，支持位置上报，开源在Github

经过近3个月的迭代开发，新版本的国标GB28181设备端EasyGBD安卓Android版终于在昨天发布到Github了，最新的EasyGBD支持了国标GB28181-2022版，还支持了语音对讲、位置上报、本地录像等功能，比原有GB28181-2016版的EasyGBD更加高效、…...

编程日记 2025/5/23 23:12:15

Hashtable 描述及源码解析

目录一、Hashtable的基本概念二、Hashtable的源码解析构造函数哈希算法函数处理哈希冲突类定义和成员变量构造方法插入元素查找元素删除元素扩容 Hashtable（哈希表）是一种非常重要的数据结构，它提供了快速的数据插入、删…...

编程日记 2025/5/22 3:08:37

clickhouse-数据库引擎

1、数据库引擎和表引擎数据库引擎默认是Ordinary，在这种数据库下面的表可以是任意类型引擎。生产环境中常用的表引擎是MergeTree系列，也是官方主推的引擎。 MergeTree是基础引擎，有主键索引、数据分区、数据副本、数据采样、删除和修改等功…...

编程日记 2025/5/23 23:12:12

深度学习之超分辨率算法——SRCNN

网络为基础卷积层 tensorflow 1.14 scipy 1.2.1 numpy 1.16 大概意思就是针对数据，我们先把图片按缩小因子照整数倍进行缩减为小图片，再针对小图片进行插值算法，获得还原后的低分辨率的图片作为标签。 main.py 配置文件 from model im…...

编程日记 2025/5/23 23:12:09

本机如何连接虚拟机MYSQL

要让本机（主机）连接到虚拟机上的 MySQL 数据库，你需要确保虚拟机和主机之间的网络连接正常，并且 MySQL 配置允许外部连接。以下是实现本机连接虚拟机 MySQL 的步骤： 步骤 1：确认虚拟机与本机的网络连接确…...

编程日记 2025/5/21 4:33:11

Download GraalVM 上面链接选择jdk的版本以及系统的环境下载graalvm的tar包解压tar包 tar -xzf graalvm-jdk-<version>_macos-<architecture>.tar.gz 移入java的文件夹目录 sudo mv graalvm-jdk-<version> /Library/Java/JavaVirtualMachines 设置环境变…...

编程日记 2025/5/24 18:23:25

大模型日报 2024-12-19

大模型日报 2024-12-19 大模型资讯标题：OpenAI发布季第十天：ChatGPT登陆电话、WhatsApp，你可以给ChatGPT真正打电话了摘要：OpenAI于2024年12月18日发布了ChatGPT的新功能，用户可以通过电话和WhatsApp与ChatGPT进行互…...

编程日记 2025/5/20 13:21:02

【数据结构练习题】链表与LinkedList

顺序表与链表LinkedList 选择题链表面试题1. 删除链表中等于给定值 val 的所有节点。2. 反转一个单链表。3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。4. 输入一个链表，输出该链…...

编程日记 2025/5/25 14:18:10

使用 acme.sh 申请域名 SSL/TLS 证书完整指南

使用 acme.sh 申请域名 SSL/TLS 证书完整指南简介为什么选择 acme.sh 和 ZeroSSL？前置要求安装过程步骤一：安装 acme.sh步骤二：配置 ZeroSSL 证书申请方法一：手动 DNS 验证（推荐新手使用）方法二&#xf…...

编程日记 2025/5/21 5:14:06

微信小程序开发入门

实现滚动需要设置高度和边框轮播图差值表达式（ {{表达式的值}} ）,info数据要写到js文件的data数据中小程序中常用的事件...

编程日记 2025/5/17 23:42:41

【LeetCode】9、回文数

【LeetCode】9、回文数文章目录一、数学: 除法和取模1.1 数学: 除法和取模二、多语言解法一、数学: 除法和取模 1.1 数学: 除法和取模例如 15251, offset 也是五位数的 10000 先判断首1和尾1, 再变为 525, offset 变为 100 再判断首5和尾5, 再变为 2, offset 变为 1 整个…...

编程日记 2025/5/20 8:15:15

面试题整理9----谈谈对k8s的理解2

面试题整理9----谈谈对k8s的理解2 1. Service 资源1.1 ServiceClusterIPNodePortLoadBalancerIngressExternalName 1.2 Endpoints1.3 Ingress1.4 EndpointSlice1.5 IngressClass 2. 配置和存储资源2.1 ConfigMap2.2 Secret2.3 PersistentVolume2.4 PersistentVolumeClaim2.5 St…...

编程日记 2025/5/25 14:19:34

fpga系列 HDL：Quartus II PLL (Phase-Locked Loop) IP核 (Quartus II 18.0)

在 Quartus II 中使用 PLL (Phase-Locked Loop) 模块来将输入时钟分频或倍频，并生成多个相位偏移或频率不同的时钟信号： 1. 生成 PLL 模块在 Quartus II 中： 打开 IP Components。 file:///C:/intelFPGA_lite/18.0/quartus/common/help/w…...

编程日记 2025/5/25 7:50:00

中国量子计算机领域的发展现状与展望

中国量子计算机领域的发展现状与展望摘要随着全球科技竞争的加剧，量子计算作为前沿技术领域备受瞩目。中国在量子计算机的研发方面取得了显著进展，本文将深入探讨中国量子计算机领域的现状、取得的成果、面临的挑战以及未来的发展方向，并…...

编程日记 2025/5/25 3:36:54

html（超文本标记语言）

声明！ 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下，如涉及侵权马上删除文章，笔记只是方便各位师傅的学习和探讨，文章所提到的网站以及内容，只做学习交流，其他均与本人以及泷羽sec团队无关&…...

编程日记 2025/5/25 14:11:27

如何在Windows系统上安装和配置Maven

Maven是一个强大的构建和项目管理工具，广泛应用于Java项目的自动化构建、依赖管理、项目构建生命周期控制等方面。在Windows系统上安装Maven并配置环境变量，是开发者开始使用Maven的第一步。本文将详细介绍如何在Windows系统上安装和配置Maven&#xff0…...

编程日记 2025/5/24 9:11:52

基于Python Scrapy的豆瓣Top250电影爬虫程序

Scrapy安装 Python实现一个简单的爬虫程序（爬取图片）_python简单扒图脚本-CSDN博客创建爬虫项目创建爬虫项目： scrapy startproject test_spider 创建爬虫程序文件： >cd test_spider\test_spider\spiders >scrapy g…...

编程日记 2025/5/25 14:15:01

mysql,数据库数据备份

mysql 一.数据库备份概念1.备份分类2.备份策略3.备份三要素二.完全备份操作1.物理备份(还原),冷备份2.逻辑备份,温备份三.percona软件的xtrabackup工具备份(2备份,3还原),增量,差异1.percona软件安装2.增量备份(还原)3.差异备份四.binlog日志1.binlog日志概念2.查看binlog日志信…...

编程日记 2025/5/19 13:56:43

模仿elementui的Table，实现思路

vue2子组件使用render，给子子组件插槽传值和elementui的Table一样使用render 在 Vue 2 中，子组件使用render函数向子子组件插槽传值可以通过以下步骤实现： 1、创建子组件首先创建一个子组件，在子组件中使用render函数来渲染内容…...

编程日记 2025/5/20 6:46:16

Android Studio AI助手---Gemini

从金丝雀频道下载最新版 Android Studio，以利用所有这些新功能，并继续阅读以了解新增内容。 Gemini 现在可以编写、重构和记录 Android 代码 Gemini 不仅仅是提供指导。它可以编辑您的代码，帮助您快速从原型转向实现，实现常见的…...

编程日记 2025/5/25 2:33:56

大模型+安全实践之春天何时到来？

引子：距《在大模型实践旅途中摸了下上帝的脚指头》一文发布近一年，2024年笔者继续全情投入在大模型＋安全上，深度参与了一些应用实践，包括安全大模型首次大规模应用在国家级攻防演习、部分项目的POC直到项目落地，也推动了一些场景安全大模型应用从0到3的孵化上市。这一年也…...

编程日记 2025/5/25 14:25:03

ACL技术---访问控制列表

是一种策略。对于网络中的流量而言，通常有两种处理方式允许拒绝 ACL 的原理配置了 ACL 的网络设备会根据事先设定好的报文匹配规则对经过该设备的报文进行匹配，然后对报文执行预先设定好的处理动作。 ACL 的功能访问控制：在设备…...

编程日记 2025/5/19 11:57:26

第25周：文献阅读

目录摘要 Abstract 文献阅读现有问题提出方法创新点方法论实验研究数据集数据预处理仿真实验评价指标实验结果分析总结摘要本篇论文提出了一种基于深度学习框架的风速预测方法——SSA-BiLSTM网络，旨在提高风速预测的精确性。研究使…...

编程日记 2025/5/25 14:44:32

BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出）

Matlab实现BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出） 目录 Matlab实现BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出）分类效果基本描述…...

编程日记 2025/5/25 14:32:12

docker数据卷

什么是数据卷？ 在容器中是无法通过vi命令对一个容器中的资源做修改的，这个时候就需要通过数据卷将文件中的内容映射到宿主机，在宿主机修改的文件会更新到容器中，并且容器被删除后不会把数据卷删除，数据卷中的数据会被持…...

编程日记 2025/5/22 21:42:33

Linux下基于最新稳定版ESP-IDF5.3.2开发esp32s3入门任务间的通讯-信号量【入门三】

继续上一篇任务创建【Linux下基于最新稳定版ESP-IDF5.3.2开发esp32s3入门任务创建【入门二】-CSDN博客】今天要实现再创建一个任务。【二值和互斥都进行测试】 ①、通过任务A发送一个信号量，另一个任务得到信号量后再发送helloworld。 ②、两个任务通过互斥信…...

编程日记 2025/5/23 23:12:07

使用C#绘制具有平滑阴影颜色的曼德布洛特集分形

示例使用复数类在 C# 中轻松绘制曼德布洛特集分形解释了如何通过迭代方程绘制曼德布洛特集：...

编程日记 2025/5/23 23:12:04

Unittest01|TestCase

一、入门 1、新建测试文件打开pycharm→左上角新建项目→选择项目路径→选择python解释器→创建→点击新建好的项目，右键新建python文件→测试文件（py文件）命名必须以test开头 2、创建测试用例定义测试类：导入unittest模块→…...

编程日记 2025/5/25 14:33:48

Django实现异步视图asyncio请求

随着现代Web应用程序对性能和响应速度的需求不断增加，开发者们越来越倾向于采用异步编程来提升应用的效率和用户体验。在传统的Web开发框架中，通常采用同步请求方式，这意味着每一个请求都需要等待前一个请求完成后才能继续处理。对于高并发的请求，可能会出现性能瓶颈。而Dj…...

编程日记 2025/5/21 14:37:15

Apache Samza开源的分布式流处理框架

Apache Samza 是一个开源的分布式流处理框架，用于处理实时数据流和分布式任务。它最初由 LinkedIn 开发，并在 2014 年捐赠给 Apache 软件基金会。Samza 的设计目标是为开发人员提供一个易用、可靠、高效的流处理工具。以下是其关键特点和架构的简介：核心特点简单的编程模…...

编程日记 2025/5/21 22:33:33

Linux实验报告5-shell脚本编程进阶

目录一：实验目的二：实验内容 1 编写脚本，实现将当前目录中所有子目录的名称输出到屏幕上。 2 首先以你的姓氏的拼音为开头在当前用户的主目录下新建3个文件和2个子目录，如zi1，zi2，zi3以及子目录zi.d和…...

编程日记 2025/5/24 10:18:57

YOLO系列正传（四）YOLOv3论文精解(下)——损失函数推导与其他优化项

系列文章 YOLO系列基础 YOLO系列基础合集——小白也看得懂的论文精解-CSDN博客 YOLO系列正传 YOLO系列正传（一）类别损失与MSE损失函数、交叉熵损失函数-CSDN博客 YOLO系列正传（二）YOLOv3论文精解(上)——从FPN到darknet-53-C…...

编程日记 2025/5/20 21:59:19

【漏洞复现】CVE-2023-37461 Arbitrary File Writing

漏洞信息 NVD - cve-2023-37461 Metersphere is an opensource testing framework. Files uploaded to Metersphere may define a belongType value with a relative path like ../../../../ which may cause metersphere to attempt to overwrite an existing file in the d…...

编程日记 2025/5/23 23:12:01

一. 树(非线性结构）

1.1 树的概念与结构

1.2 树的表示

二. 二叉树

2.1 二叉树的概念与结构

2.2 特殊的二叉树

2.3 二叉树的存储结构

三. 实现顺序结构的二叉树

3.1 堆的概念与结构

相关文章：