当前位置: 首页 > 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 帮助 首先来看什么参数都没加…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...