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

数据结构之堆和二叉树的简介

1.

1.1 树的概念与结构

如图所示,树是⼀种非线性的数据结构,它是由 n (n>=0) 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
有⼀个特殊的结点,称为根结点,根结点没有前驱结点。
除根结点外,其余结点被分成 M(M>0) 个互不相交的集合 T1 T2 …… Tm ,其中每⼀个集合
Ti(1 <= i <= m) 又 是⼀棵结构与树类似的子树。每棵子树的根结点有且只有⼀个前驱,可以
0 个或多个后继。因此,树是递归定义的。

注意:

1.树形结构中,子树之间不能有交集,否则就不是树形结构 !!!(相交了称为图,而不是树)

2.除了根结点外,每个结点有且仅有⼀个父结点

3. ⼀棵N个结点的树有N-1条边

1.2 树相关术语

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

1.3 树的表示

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

示例说明:

2. 二叉树

2.1 概念与结构

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

从上图可以看出⼆叉树具备以下特点:
1. 二叉树不存在度大于 2 的结点
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
注意:对于任意的⼆叉树都是由以下几种情况复合而成的

 

2.2 特殊的二叉树

2.2.1 满二叉树

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

2.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) ( log 以2为底,          n+1 为对数)

2.3 二叉树存储结构

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

2.3.1 顺序结构

顺序结构存储就是使用数组来存储,⼀般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费,完全二叉树更适合使用顺序结构存储。
现实中我们通常把堆(⼀种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,⼀个是数据结构,⼀个是操作系统中管理内存的⼀块区域分段。

2.3.2 链式结构

二叉树的链式存储结构是指,⽤链表来表示⼀棵⼆叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链。后面会学到高阶数据结构如红黑树等会用到三叉链。
简介到此结束,后续堆的实现内容请关注下一篇文章!

相关文章:

数据结构之堆和二叉树的简介

1.树 1.1 树的概念与结构 如图所示&#xff0c;树是⼀种非线性的数据结构&#xff0c;它是由 n &#xff08;n>0&#xff09; 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下的。 …...

微信小程序上传图片添加水印

微信小程序使用wx.chooseMedia拍摄或从手机相册中选择图片并添加水印&#xff0c; 代码如下&#xff1a; // WXML代码&#xff1a;<canvas canvas-id"watermarkCanvas" style"width: {{canvasWidth}}px; height: {{canvasHeight}}px;"></canvas&…...

xshell5找不到匹配的host key算法

xshell5找不到匹配的host key算法&#xff0c;是因为电脑客户端不支持服务器的算法&#xff0c;因此需要再服务器增加算法。 下面以Ubuntu系统为例&#xff0c;修改下面的文件 sudo vim /etc/ssh/sshd_config 增加下面算法 KexAlgorithms diffie-hellman-group-exchange-…...

Linux中安装Tomcat

文章目录 一、Tomcat介绍1.1、Tomcat是什么1.2、Tomcat的工作原理1.3、Tomcat适用的场景1.4、Tomcat与Nginx、Apache比较1.4.1、优势1.4.2、劣势1.4.3、定位功能 1.5、Tomcat 的主要组件1.6、Tomcat 的主要配置文件 二、Tomcat安装2.1、查看可用的JDK2.2、安装OpenJDK 112.3、配…...

RV1126音视频学习(二)-----VI模块

文章目录 前言2.RV1126的视频输入vi模块2.1什么是VI模块2.3RV1126VI模块主要APIRK_MPI_SYS_Init()RK_MPI_VI_SetChnAttrRK_MPI_VI_EnableChnRK_S32 RK_MPI_VI_DisableChnRK_MPI_VI_StartStreamRK_MPI_SYS_GetMediaBufferRK_MPI_MB_GetPtrRK_MPI_MB_GetSizeRK_MPI_MB_ReleaseBuf…...

「C/C++」C++17 之 std::string_view 轻量级字符串视图

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…...

Linux内核-内核模块内核参数

作者介绍&#xff1a;简历上没有一个精通的运维工程师。希望大家多多关注作者&#xff0c;下面的思维导图也是预计更新的内容和当前进度(不定时更新)。 我们的Linux进阶部分&#xff0c;到目前为止&#xff0c;已经讲过&#xff1a;硬件&#xff0c;日常运维&#xff0c;基础软…...

中电信翼康工程师:我在 Apache SeaTunnel 社区的贡献之旅

贡献者Github ID&#xff1a;luckyLJY 文章整理&#xff1a;曾辉 Apache SeaTunnel 作为一款强大的数据同步和转换工具&#xff0c;凭借其部署易用性、容错机制、数据源支持、性能优势、功能丰富性以及活跃的社区支持&#xff0c;成为了数据工程师们不可或缺的利器。 因其具有的…...

【ESP32S3】VSCode 开发环境搭建

ESP32S3 有多种开发方式&#xff0c;主流的有 Eclipse 和 VSCode 两种。本文来介绍一下基于 VSCode 的开发环境搭建。 VSCode 环境需要依赖于 ESP-IDF 插件&#xff0c;因此需要在 VSCode 插件市场中搜索并安装 ESP-IDF 插件&#xff1a; 安装完成后侧边栏会多出一个 ESP-IDF …...

大模型,多模态大模型面试问题基础记录24/10/24

大模型&#xff0c;多模态大模型面试问题基础记录24/10/24 问题一&#xff1a;LoRA是用在节省资源的场景下&#xff0c;那么LoRA具体是节省了内存带宽还是显存呢&#xff1f;问题二&#xff1a;假如用pytorch完成一个分类任务&#xff0c;那么具体的流程是怎么样的&#xff1f;…...

使用TimeShift备份和恢复Ubuntu Linux

您是否曾经想过如何备份和恢复您的Ubuntu或Debian系统&#xff1f;TimeShift是一个强大的备份和还原工具。TimeShift允许您创建系统快照&#xff0c;提供了一种在出现意外问题或系统故障时恢复到先前状态的简便方式。您可以使用RSYNC或BTRFS创建快照。 有了这个介绍&#xff0…...

win7现在还能用吗_哪些配置的电脑还可以安装win7系统

2024年了都&#xff0c;win7现在还能用吗&#xff1f;答案是肯定的。那么哪些配置的电脑还可以安装win7系统呢&#xff1f;下面就针对这两个问题详细分区。 win7现在还能用吗&#xff1f; Windows 7系统虽然已经停止官方支持&#xff0c;但仍然可以使用。以下是关于Windows 7系…...

基于GPT的智能客服落地实践

&#x1f4cd;前言 在日常生活中&#xff0c;「客服」这个角色几乎贯穿着我们生活的方方面面。比如&#xff0c;淘宝买东西时&#xff0c;需要客服帮你解答疑惑。快递丢失时&#xff0c;需要客服帮忙找回。报名参加培训课程时&#xff0c;需要客服帮忙解答更适合的课程…… 基…...

Sourcetree和GitLab的结合使用

一、写在前面 为什么是Sourcetree和GitLab&#xff1f;因为遇到的坑最少&#xff0c;在不用梯子的情况下&#xff0c;推送速度还可以。 这篇文章主要介绍的是&#xff0c;怎么把自己写的代码文件打包放到GitLab上去&#xff0c;方便别人下载使用&#xff0c;也方便自己在另一…...

双十一开启极速达夜派;黑神话获泰国年度最佳游戏;AI 模型可帮助识别 17000 多种疾病的候选药物....| 网易数智日报

双 11 菜鸟在北京、上海、广州、杭州等城市开启「预售极速达夜派」服务 10 月 21 日&#xff0c;菜鸟在北京、上海、广州、杭州等城市开启「预售极速达夜派」服务&#xff0c;批量大促包裹实现小时级送达。 据介绍&#xff0c;在消费者支付尾款前&#xff0c;菜鸟供应链就已经…...

深入理解JAVA虚拟机(一)

介绍JAVA虚拟机的运行时数据区域 按照物理结构来划分&#xff1a;java虚拟机主要由以下几部分构成栈、堆和程序计数器&#xff0c;其中栈又可以分为虚拟机栈VM stack 和 本地方法栈 Native Method Statck&#xff0c;堆可以划分方法区和普通的堆内存。按照逻辑划分线程私有空间…...

从Excel文件中读取数据

笔记 import openpyxl # 打开工作簿 workbookopenpyxl.load_workbook(景区天气.xlsx) # 选择要操作的工作表 sheetworkbook[景区天气] # 表格数据是二维列表&#xff0c;先遍历的是行&#xff0c;后遍历的是列 lst[] # 存储的是行数据 for row in sheet.rows:sublst[] # 存储单…...

深入剖析MySQL的索引机制及其选型

在数据库管理系统中&#xff0c;索引是一种重要的优化工具&#xff0c;用于加速数据的检索和查询处理。在MySQL中&#xff0c;合理使用索引可以显著提高数据库的性能。本文将深入探讨MySQL的索引机制&#xff0c;包括不同类型索引的优势、劣势及在实际使用中的选型策略。 1. 什…...

校园表白墙源码修复版

此校园表白墙源码基于thinkphp&#xff0c;因为时代久远有不少bug&#xff0c;经本人修复已去除大部分bug&#xff0c;添加了美化元素。 https://pan.quark.cn/s/1f9b3564c84b https://pan.baidu.com/s/1bb9vu9VV2jJoo9-GF6W3xw?pwd7293 https://caiyun.139.com/m/i?2hoTc…...

Android 内存优化——常见内存泄露及优化方案

看到了一篇关于内存泄漏的文章后&#xff0c;就想着分享给大家&#xff0c;最后一起学习&#xff0c;一起进步&#xff1a; 如果一个无用对象&#xff08;不需要再使用的对象&#xff09;仍然被其他对象持有引用&#xff0c;造成该对象无法被系统回收&#xff0c;以致该对象在…...

Qt6.7.2中使用OpenSSL的坑

最近编写Qt Quick项目&#xff0c;使用Qt6.7.2版本&#xff0c;CMAKE编译&#xff0c;开始QtCreator运行代码都没有问题&#xff0c;访问https也正常&#xff0c;但打出安装包后一试&#xff0c;发现https访问不了&#xff0c;尴尬&#xff01;&#xff01; 查看了相关日志发现…...

Mybatis-08.基础操作-删除

一.删除 接口方法 package com.gjw.mapper;import com.gjw.pojo.Emp; import org.apache.ibatis.annotations.Delete; import org.apache.ibatis.annotations.Mapper;import java.util.List;Mapper public interface EmpMapper {// 根据ID删除数据Delete("delete from e…...

通过FDM升级Firepower

1.基本说明 本文主要主要介绍如何通过FDM来升级Firepower设备&#xff0c;这里以FPR1010设备为例&#xff0c;那么什么事Firepower、FDM呢&#xff1f;在开始之前&#xff0c;进行简单的介绍。 Firepower&#xff1a;思科 Firepower 是网络安全和流量管理产品的集成套件&…...

使用 Kibana 将地理空间数据导入 Elasticsearch 以供 ES|QL 使用

作者&#xff1a;来自 Elastic Craig Taverner 如何使用 Kibana 和 csv 采集处理器将地理空间数据采集到 Elasticsearch 中&#xff0c;以便在 Elasticsearch 查询语言 (ES|QL) 中进行搜索。Elasticsearch 具有强大的地理空间搜索功能&#xff0c;现在 ES|QL 也具备这些功能&am…...

demo说明

代码说明 MDIO总线的注册和初始化&#xff1a;分配并注册MDIO总线&#xff0c;用于与PHY设备通信。 网络设备的创建&#xff1a;分配网络设备&#xff08;如以太网接口&#xff09;。 PHY设备连接&#xff1a;通过phy_connect函数连接PHY设备&#xff0c;指定回调函数my_adj…...

【c++篇】:从基础到实践--c++内存管理技巧与模版编程基础

✨感谢您阅读本篇文章&#xff0c;文章内容是个人学习笔记的整理&#xff0c;如果哪里有误的话还请您指正噢✨ ✨个人主页&#xff1a;余辉zmh–CSDN博客 ✨ 文章所属专栏&#xff1a;c篇–CSDN博客 文章目录 前言一.c/c内存分布二.c/c的动态内存管理方式2.1.c语言的动态内存管…...

如何减小 Maven 项目生成的 JAR 包体积 提升运维效率

在使用 Maven 构建 Java 项目时&#xff0c;有时需要减小生成的 JAR 包的体积&#xff0c;以提高部署效率或减少资源消耗。以下是一些有效的方法来减小 JAR 包的体积&#xff1a; 排除不必要的依赖打包时&#xff0c;依赖jar包独立于应用jar包 1. 排除不必要的依赖 通过排除项目…...

Python自动化会议记录与摘要生成

前言 在现代工作环境中&#xff0c;会议是团队沟通和决策的重要方式。然而&#xff0c;整理会议记录和生成摘要往往是一项耗时且容易出错的任务。幸运的是&#xff0c;借助Python编程语言以及一些强大的库&#xff0c;我们可以自动化这一过程&#xff0c;让机器帮助我们完成这…...

SwiftUI 中 List 或 Form 子视图关联的 swipeAction 导致展开动画异常的解决

问题现象 小伙伴们都知道,在 SwiftUI 中更快捷的增强 List 或 Form 子视图(Cell)交互功能的方法是使用 swipeAction 修改器。不过,对其使用稍有不慎也会横生枝节。 如上图所示,不适当的设置 Cell 视图布局会使 swipeAction 无法生成正确的收缩和展开动画。对此我们有什么…...

Apache Paimon Catalog

Paimon Catalog可以持久化元数据&#xff0c;当前支持两种类型的metastore&#xff1a; 文件系统&#xff08;默认&#xff09;&#xff1a;将元数据和表文件存储在文件系统中。hive&#xff1a;在 hive metastore中存储元数据。用户可以直接从 Hive 访问表。 2.2.1 文件系统…...

现在还用dw做网站设计么/站长网站统计

进程间通信之管道篇 一&#xff1a;管道实现原理 在 Linux 中&#xff0c; 管道是一种使用非常频繁的通信机制。 从本质上说&#xff0c;管道也是一种文件&#xff0c;但它又和一般的文件有所不同&#xff0c;管道可以克服使用文件进行通信的两个问题&#xff0c;具体表现为&a…...

网站开发公司制作平台/百度一下首页登录

众所周知&#xff0c;程序员最不爱用鼠标了&#xff0c;因为用鼠标慢吞吞的影响工作效率&#xff0c;还一点都不酷。今天给小伙伴们分享15个非常实用的快捷键&#xff0c;让大家在使用电脑工作和学习时&#xff0c;爽的飞起&#xff01;AltTab切换应用。在日常工作中&#xff0…...

贵阳网站制作工具/悟空建站seo服务

题目 给你一个仅包含小写英文字母和 ‘?’ 字符的字符串 s&#xff0c;请你将所有的 ‘?’ 转换为若干小写字母&#xff0c;使最终的字符串不包含任何 连续重复 的字符。 注意&#xff1a;你 不能 修改非 ‘?’ 字符。 题目测试用例保证 除 ‘?’ 字符 之外&#xff0c;…...

做淘宝客如何建立网站/网络营销怎么推广

操作系统有那些服务器 内容精选换一换切换操作系统是为您的云服务器重新切换一个系统盘。切换完成后云服务器的系统盘ID会发生改变&#xff0c;并删除原有系统盘。如果云服务器当前使用的操作系统不能满足业务需求(如软件要求的操作系统版本较高)&#xff0c;您可以选择切换云服…...

中国建设银行网站打不开/网络营销的模式有哪些?

为什么我上传一张特定的图片一直是这个异常&#xff0c;但是图片能上传到服务器&#xff0c;save保存方法也没执行成功没插入到数据库中&#xff0c;是不是跟我那个保存方法里面其他东西有关&#xff0c;这个跟图片大小无关&#xff0c;因为上传比它大的图片保存方法都能成功ja…...

做英文兼职的网站/站长工具seo综合查询访问

“树状视图控件”是一个显示项目层次列表的窗口&#xff0c;例如文档中的标题、索引中的条目或磁盘上的文件和目录。每个项目都由一个标签和一个可选的位图图像组成&#xff0c;每个项目都可以有一个与其相关联的子项目列表。通过单击项目&#xff0c;用户可以展开和折叠子项目…...