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

二叉树(上)

   “路虽远,行则将至”

❤️主页:小赛毛

目录

1.树概念及结构

1.1树的概念

1.2 树的相关概念

 1.3 树的表示(树的存储)

2.二叉树概念及结构

2.1概念

2.2现实中的二叉树

2.3 特殊的二叉树:

2.4 二叉树的性质 

3.二叉树的顺序结构及实现

3.1 二叉树的顺序结构

3.2 堆的概念及结构

3.3 堆的实现

3.2.1 堆向下调整算法

 3.2.2堆的创建

前言:

在进入今天的正题之前,我们先来回顾一下我们已经学过的知识:

顺序的本质是什么呢?数组

但是呢,顺序表在这里是有一些缺陷的:

1.中间或者头部插入删除数据要挪动数据,效率低

2.空间不够,只能扩容。扩容有消耗

3.倍数扩容,用不完,存在空间浪费

当然,有利有弊,优点:

1.下标随机访问。排序 二分查找适合

2.CPU高速缓存命中率比较高

在我们学完顺序表之后呢,我们当时顺序就学了链表:

在这里呢,我们要请出链表的典型代表——带头结点的双向循环链表 同志来参加。

优点:

1.任意位置插入删除效率高

2.按需申请释放,不存在扩容

缺点:

1.不能下标随机访问

2.CPU高速缓存命中率低


1.树概念及结构

1.1树的概念

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

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

1.2 树的相关概念

  • 节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的为6
  • 叶节点或终端节点:度为0的节点称为叶节点;如上图:BCHI...等节点为叶节点
  • 非终端节点或分支节点:度不为0的节点;如上图:DEFG...等节点为分支节点
  • 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;如上图:AB的父节点
  • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;如上图:BA的孩子节点
  • 兄弟节点:具有相同父节点的节点互称为兄弟节点;如上图:BC是兄弟节点
  • 树的度:一棵树中,最大的节点的度称为树的度;如上图:树的度为6
  • 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
  • 树的高度或深度:树中节点的最大层次;如上图:树的高度为4
  • 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:HI互为兄弟节点
  • 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
  • 森林:由mm>0)棵互不相交的树的集合称为森林;(并查集里面就是多棵树)

 1.3 树的表示(树的存储)

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了, 既然保存值域,也要保存结点和结点之间 的关系 ,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法
下面就给大家展示一下这个贼🐂🍺的方法( 左孩子、右兄弟表示法):
struct TreeNode
{int val;struct TreeNode* firstchild;//第一个孩子节点struct TreeNode* nextbroyher;//指向其下一个兄弟节点
}

双亲表示法(只存储父亲的下标或指针)

在很多地方,双亲表示法一般就是用数组的方式直接玩 

这个地方就可以很容易判断出来有几棵树,有几个兄弟。

于是否,两个节点在不在同一棵树,如何判断?

找根,根相同就在同一棵树


其实呢,在实际生活中,我们用的最多的实际上是二叉树

2.二叉树概念及结构

2.1概念

从上图可以看出:
1. 二叉树不存在度大于 2 的结点 (最多两个孩子 也可以是一个或零个)
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
注意:对于任意的二叉树都是由以下几种情况复合而成的:

2.2现实中的二叉树

2.3 特殊的二叉树:

1. 满二叉树 (假设它有h层,每一层都是满的) :一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是2的k次方-1 则它就是满二叉树。
2. 完全二叉树 :完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为 K 的,有n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 n 的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.4 二叉树的性质 

 

1.若规定根节点的层数为 1 ,则一棵非空二叉树的 i 层上最多有 2^(i-1)个结点.
2. 若规定根节点的层数为 1 ,则 深度为 h 的二叉树的最大结点数是2^h-1
3. 对任何一棵二叉树 , 如果度为 0 其叶结点个数为n0  , 度为 2 的分支结点个数为n2  , 则有 n0=n2 + 1
4. 若规定根节点的层数为 1 ,具有 n 个结点的满二叉树的深度 h= log以 2 为底,n+1 为对数
5. 对于具有 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 否则无右孩子

3.二叉树的顺序结构及实现

3.1 二叉树的顺序结构

  parent = (child-1) / 2

任意位置通过下标可以找父亲或者孩子

那如果不是满二叉树或者完全二叉树的话,还适合这个规律吗?显然不可以

那我们这里可以进行总结:

满二叉树 或者 完全二叉树适合用数组存储


3.2 堆的概念及结构

堆的性质:
堆中某个节点的值总是不大于或不小于其父节点的值;
堆总是一棵完全二叉树。

3.3 堆的实现

3.2.1 堆向下调整算法

 我们在这里先来说明一下:

栈:线性表,后进先出

堆:非线性表,完全二叉树

小堆:树中任意一个父亲都 ≤ 孩子

大堆:树中任意一个父亲都 ≥ 孩子

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
intarray[] = {27,15,19,18,28,34,65,49,25,37};

 

底层:

  • 物理结构:数组
  • 逻辑结构:完全二叉树

小堆,底层数组是否升序呢?不一定

小堆的根是整棵树的最小值

 3.2.2堆的创建

下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。
inta[] = {1,5,3,8,7,6}; 

 

相关文章:

二叉树(上)

“路虽远&#xff0c;行则将至” ❤️主页&#xff1a;小赛毛 目录 1.树概念及结构 1.1树的概念 1.2 树的相关概念 1.3 树的表示&#xff08;树的存储&#xff09; 2.二叉树概念及结构 2.1概念 2.2现实中的二叉树 2.3 特殊的二叉树&#xff1a; 2.4 二叉树的性质 3.二叉树的顺…...

Excel怎么批量生成文件夹

Excel怎么批量生成文件夹的链接: https://jingyan.baidu.com/article/ea24bc398d9dcb9b63b3312f.html...

c++ 学习之 静态成员变量和静态成员函数

文章目录 前言正文静态成员变量初始化操作如何理解共享一份数据访问权限 静态成员函数访问方式静态成员函数只能访问静态成员变量访问权限 前言 静态成员分为 1&#xff09;静态成员变量 所有对象共享一份数据在编译阶段分配空间类内声明&#xff0c;类外初始化 2&#xff09…...

C程序需要按下回车键才能读取字符

当编写涉及从终端输入字符的C程序时&#xff0c;有时会遇到需要按下回车键才能读取字符的问题。这是因为默认情况下&#xff0c;终端通常处于行缓冲模式&#xff0c;需要等待用户按下回车键才会将输入的字符发送给正在运行的程序。这可能会导致一些不便&#xff0c;尤其是当程序…...

x86体系结构(WinDbg学习笔记)

寄存器 eaxAccumulator累加器ebxBase register基寄存器ecxCounter register计数器寄存器edxData register - can be used for I/O port access and arithmetic functions数据寄存器-可用于I/O端口访问和算术函数esiSource index register源索引寄存器ediDestination index reg…...

Hadoop的第二个核心组件:MapReduce框架第四节

Hadoop的第二个核心组件&#xff1a;MapReduce框架 十、MapReduce的特殊应用场景1、使用MapReduce进行join操作2、使用MapReduce的计数器3、MapReduce做数据清洗 十一、MapReduce的工作流程&#xff1a;详细的工作流程第一步&#xff1a;提交MR作业资源第二步&#xff1a;运行M…...

算法通关村第十九关——最少硬币数

LeetCode322.给你一个整数数组 coins,表示不同面额的硬币&#xff0c;以及一个整数 amount&#xff0c;表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额&#xff0c;返回-1。你可以认为每种硬币的数量是无限的。 示例1&…...

Linux ifconfig只显示 lo 网卡,没有ens网卡解决方案

项目场景&#xff1a; 虚拟机中linux无网络问题 问题描述 之前在调试linux的时候&#xff0c;由于一些不太清楚的误操作&#xff0c;导致ubuntu linux出现无网络问题&#xff0c;现象如下 ifconfig 只显示了 lo 网卡 lo 网卡&#xff1a;它是本地环回接口。 这意味着您的虚…...

Java复习-26-枚举

枚举&#xff08;替换多例设计&#xff09; 目的&#xff08;使用场景&#xff09; 不用也没啥 定义一个描述性别的类&#xff0c;那么该对象只有两个:男、 女。或者描述颜色基色的类&#xff0c;可以使用: 红色、绿色、蓝色。 功能 用于定义有限个数对象的一种结构&#x…...

NLP(六十八)使用Optimum进行模型量化

本文将会介绍如何使用HuggingFace的Optimum&#xff0c;来对微调后的BERT模型进行量化&#xff08;Quantization&#xff09;。   在文章NLP&#xff08;六十七&#xff09;BERT模型训练后动态量化&#xff08;PTDQ&#xff09;中&#xff0c;我们使用PyTorch自带的PTDQ&…...

Tomcat多实例和负载均衡动静分离

目录 一、Tomcat多实例部署 二、负载均衡动静分离 2.1.动静分离 2.11 nginx负载均衡 192.168.30.203 2.22 Tomcat服务器&#xff1a;192.168.30.200&#xff1a;80 2.23 Tomcat服务器&#xff1a;192.168.30.100&#xff1a;80 2.24 配置nginx 192.168.30.203静态页面 2…...

企业ERP和泛微OA集成场景分析

轻易云数据集成平台&#xff08;qeasy.cloud&#xff09;为企业ERP和泛微OA系统提供了强大的互通解决方案&#xff0c;特别在销售、采购和库存领域的单据审批场景中表现出色。这些场景涉及到多个业务单据的创建和审批&#xff0c;以下是一些具体的应用场景描述&#xff1a; 采购…...

31 WEB漏洞-文件操作之文件包含漏洞全解

目录 文件包含漏洞原理检测类型利用修复 本地包含-无限制&#xff0c;有限制远程包含-无限制&#xff0c;有限制各种协议流玩法文章介绍读取文件源码用法执行php代码用法写入一句话木马用法每个脚本支持的协议玩法 演示案例某CMS程序文件包含利用-黑盒CTF-南邮大&#xff0c;i春…...

qmake.exe xxx.pro -spec win32-g++ 作用

作用 qmake.exe xxx.pro -spec win32-g的作用是使用win32-g构建系统规范来生成针对xxx.pro项目的构建脚本。 具体来说&#xff0c;这个命令的含义如下&#xff1a; qmake.exe&#xff1a;使用qmake命令行工具。xxx.pro&#xff1a;指定了要构建的项目文件&#xff0c;.pro文…...

SpringMVC实现增删改查

文章目录 一、配置文件1.1 导入相关pom依赖1.2 jdbc.properties&#xff1a;配置文件1.3 generatorConfig.xml&#xff1a;代码生成器1.4 spring-mybatis.xml &#xff1a;spring与mybatis整合的配置文件1.5 spring-context.xml &#xff1a;上下文配置文件1.6 spring-mvc-xml:…...

React 配置别名 @ ( js/ts 项目中通过 webpack.config.js 配置)

一、简介 在 Vue 项目当中&#xff0c;可以使用 来表示 src/&#xff0c;但在 React 项目中&#xff0c;默认却没有该功能&#xff0c;因此需要进行手动的配置来实现该功能。 别名主要解决的问题&#xff1a;每个页面都使用路径的方式进行引入&#xff0c;这样很麻烦&#xff…...

Android 在TextView前面添加多个任意View且不影响换行

实现效果如下&#xff1a; 如上&#xff0c;将头像后面的东西看作一个整体&#xff0c;因为不能影响后面内容的换行&#xff0c;且前面控件的长度是可变的&#xff0c;所以采用自定义View的方法来实现&#xff1a; /*** CSDN深海呐 https://blog.csdn.net/qq_40945489/articl…...

字符串相加

给定两个字符串形式的非负整数 num1 和num2 &#xff0c;计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库&#xff08;比如 BigInteger&#xff09;&#xff0c; 也不能直接将输入的字符串转换为整数形式。 示例 1&#xff1a; 输入&#xff…...

uni-app直播从0到1实战

1.安装开发工具 2.创建项目 参考&#xff1a;uniapp从零到一的学习商城实战_云澜哥哥的博客-CSDN博客...

Python UI自动化 —— pytest常用运行参数解析、pytest执行顺序解析

pytest常用Console参数&#xff1a; -v 用于显示每个测试函数的执行结果-q 只显示整体测试结果-s 用于显示测试函数中print()函数输出-x 在第一个错误或失败的测试中立即退出-m 只运行带有装饰器配置的测试用例-k 通过表达式运行指定的测试用例-h 帮助 首先来看什么参数都没加…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...