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

C++数据结构-树的概念及分类介绍(基础篇)

1.什么是树

树是数据结构中的一种,其属于非线性数据结构结构的一种,我们前文所提到的数据结构多数都是线性的,这也是较为简单的数据结构,而接下来的树与图均属于非线性数据结构,也是概念极多的一类。

树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点,还(很可能)有多个附加结点,所有结点构成一个多级分层结构。

树的定义:n个节点组成的有限集合。n=0,空树;n>0,1个根节点,m个互不相交的有限集,每个子集为根的子树。

如图所示,图为一颗树:

ce0d53bc0b5d4df78a047de0549f8d94.png

2.树的基本术语

l  节点的度:树中某个节点的子树的个数。

l  树的度:树中各节点的度的最大值。

l  分支节点:度不为零的节点。

l  叶子节点:度为零的节点。

l  路径:i->j;路径长度:路径经过节点数目减1。

l  孩子节点:某节点的后继节点;双亲节点:该节点为其孩子节点的双亲节点(父母节点);兄弟节点:同一双亲的孩子节点;子孙节点:某节点所有子树中的节点;祖先节点:从树节点到该节点的路径上的节点。

l  节点的层次:根节点为第一层(以此类推);树的高度:树中节点的最大层次。

有序树:树中节点子树按次序从左向右安排,次序不能改变;无序树:与之相反

l  森林:互不相交的树的集合。

3.树的性值

l  树的节点树为所有节点度数加1(加根节点)。

l  度为m的树中第i层最多有m^(i-1)个节点。

l  高度为h的m次树至多(m^h-1)/(m-1)个节点。

l  具有n个节点的m次树的最小高度为logm( n(m-1) + 1 )  向上取整。

4. 二叉树简介

二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

如图

249e9a3fa6594bc7936b9d0991e63c54.png

如图,每一个结点中最多拥有一个左结点和一个右结点,并没有多余的结点,这是很明显的二叉树的特征

5. 二叉树的特点

由二叉树定义以及图示分析得出二叉树有以下特点:

1)每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。

2)左子树和右子树是有顺序的,次序不能任意颠倒。

3)即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

6. 二叉树的性质

二叉树具有以下几种特征

性质1:二叉树第i层上的结点数目最多为 2的(i-1)次方个节点(i≥1)。

性质2:深度为k的二叉树至多有2的k次方-1个结点(k≥1)。

性质3:包含n个结点的二叉树的高度至少为log2 (n+1)。

性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1。

7. 几种特殊的二叉树

l 斜树

斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

bb51ffdd55054faab8aa950dd5d639cc.png

如图为一颗左斜树

l 满二叉树

满二叉树:在一棵二叉树中。如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

满二叉树的特点有:

1)叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

2)非叶子结点的度一定是2。

3)在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。

af8e448ba4e14c15b9175dabcfbb6f50.png

如图为一颗满二叉树

l 完全二叉树

完全二叉树:对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。

8b412b69dbd74a00b504eacda16cf9dc.png

如图为一颗完全二叉树

 

 

 

相关文章:

C++数据结构-树的概念及分类介绍(基础篇)

1.什么是树 树是数据结构中的一种&#xff0c;其属于非线性数据结构结构的一种&#xff0c;我们前文所提到的数据结构多数都是线性的&#xff0c;这也是较为简单的数据结构&#xff0c;而接下来的树与图均属于非线性数据结构&#xff0c;也是概念极多的一类。 树是由结点或顶…...

职场 Death Note

场景一 测试&#xff1a;哎&#xff0c;怎么会这样呢&#xff1f;时间没到&#xff0c;他怎么就变成这个样子了呢&#xff1f;一副大惊小怪&#xff0c;整个办公室都是他的声音 开发&#xff1a;对对对&#xff0c;我代码问题&#xff0c;别BB了。 你直接说这个地方不对&#…...

Vue3.0组合式API:computed计算属性、watch监听器、watchEffect高级监听器

1、computed() 计算属性 在模板中绑定表达式只能用于简单的运算。如果运算比较复杂&#xff0c;可以使用 Vue.js 提供的计算属性&#xff0c;通过计算属性可以处理比较复杂的逻辑。 1.1 计算属性的应用 通过计算属性可以实现各种复杂的逻辑&#xff0c;包括运算、函数调用等…...

RAII 与 std::lock_guard 在 C++ 中的应用:自动化互斥锁管理与线程安全

目录 1. RAII&#xff08;资源获取即初始化&#xff09;概述 RAII 的优点 2. std::lock_guard 的工作原理 2.1 构造函数 2.2 析构函数 2.3 关键特性 3. 为什么 std::lock_guard 能自动管理锁的生命周期 3.1 RAII 原则的应用 3.2 异常安全 3.3 简化代码和减少错误 4.…...

风格汇:奢华风格在UI设计中如何被定义的。

在UI设计中&#xff0c;奢华风格通常指的是一种高端、豪华、精致的设计风格&#xff0c;旨在营造出奢华、豪华的视觉效果&#xff0c;给用户带来高品质、高档次的感受。 奢华风格的UI设计通常会运用一些富丽堂皇的元素和效果&#xff0c;例如金色、银色、贵族紫、华丽的字体、华…...

Vue2 qrcode+html2canvas 实现二维码的生成和保存

1.安装 npm install qrcode npm install html2canvas 2.引用 import QRCode from qrcode import html2canvas from html2canvas 效果&#xff1a; 1. 二维码生成&#xff1a; 下载二维码图片&#xff1a; 二维码的内容&#xff1a; 实现代码&#xff1a; <template>…...

GEE 教程:利用Google Dynamic数据进行逐月指定区域的土地分类数据提取分析

目录 简介 数据 代码 结果 简介 利用Google Dynamic数据进行逐月指定区域的土地分类数据提取分析 数据 Google Dynamic数据是指由Google自动生成、自动更新的数据,它不需要人工干预,而是通过算法和机器学习技术从各种来源获取并解析数据。这些数据可以是来自互联网上的…...

Nginx 负载均衡:优化网站性能与可扩展性的利器

在当今高流量的互联网时代&#xff0c;网站的性能和可扩展性成为了衡量其成功与否的关键因素之一。随着用户量的不断增加&#xff0c;单一服务器往往难以承受巨大的访问压力&#xff0c;这时就需要引入负载均衡技术来分散请求&#xff0c;提高系统的整体性能和可靠性。Nginx&am…...

【Python基础】Python错误和异常处理(详细实例)

本文收录于 《Python编程入门》专栏&#xff0c;从零基础开始&#xff0c;分享一些Python编程基础知识&#xff0c;欢迎关注&#xff0c;谢谢&#xff01; 文章目录 一、前言二、Python中的错误类型三、Python异常处理机制3.1 try-except语句3.2 try-except-else语句3.3 try-fi…...

如何查看串口被哪个程序占用?截止目前最方便的方法

痛点&#xff1a;串口因为某种原因被占用&#xff0c;如何找到罪魁祸首&#xff1f; 做开发的小伙伴们&#xff0c;经常会遇到这样的问题&#xff1a;串口因为某种原因被占用&#xff0c;导致无法通讯&#xff0c;但是又找不到被哪个程序占用。只有重启电脑&#xff0c;才能解…...

深入理解SpringBoot(一)----SpringBoot的启动流程分析

1、SpringApplication 对象实例化 SpringApplication 文件 public static ConfigurableApplicationContext run(Object[] sources, String[] args) {// 传递的source其实就是类Bootstrapreturn new SpringApplication(sources).run(args);// 实例化一个SpringApplication对象执…...

MySql基础-单表操作

1. MYSQL概述 1.1 数据模型 关系型数据库 关系型数据库(RDBMS)&#xff1a;建立在关系模型基础上&#xff0c;由多张相互连接的二维表组成的数据库。 特点&#xff1a; 使用表存储数据&#xff0c;格式统一&#xff0c;便于维护 使用SQL语言操作&#xff0c;标准统一&…...

【STM32系统】基于STM32设计的SD卡数据读取与上位机显示系统(SDIO接口驱动、雷龙SD卡)——文末资料下载

基于STM32设计的SD卡数据读取与上位机显示系统 演示视频&#xff1a; 基于STM32设计的SD卡数据读取与上位机显示系统 简介&#xff1a;本研究的主要目的是基于STM32F103微控制器&#xff0c;设计一个能够读取SD卡数据并显示到上位机的系统。SD卡的数据扇区读取不仅是为了验证存…...

SpringBoot开发——整合Redis

文章目录 1、创建项目&#xff0c;添加Redis依赖2、创建实体类Student3、创建Controller4、配置application.yml5、整合完成 Redis ( Remote Dictionary Server &#xff09;是一个开源的内存数据库&#xff0c;遵守 BSD 协议&#xff0c;它提供了一个高性能的键值&#xff08…...

OpenCV结构分析与形状描述符(17)判断轮廓是否为凸多边形的函数isContourConvex()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 测试轮廓的凸性。 该函数测试输入的轮廓是否为凸的。轮廓必须是简单的&#xff0c;即没有自相交。否则&#xff0c;函数的输出是不确定的。 cv:…...

P5425 [USACO19OPEN] I Would Walk 500 Miles G

*原题链接* 很离谱的题。首先可以想到暴力连边&#xff0c;整个图为一个完全图&#xff0c;将所有的边选出来&#xff0c;然后从小到大一条条加入&#xff0c;当剩下集合数量 <K 的时候就结束。答案为加入的最后一条边的大小。如果用prim算法的话时间复杂度为。足以通过此题…...

Java高级Day41-反射入门

115.反射 反射机制 1.根据配置文件re.properties指定信息&#xff0c;创建Cat对象并调用hi方法 SuppressWarnings({"all"}) public class ReflectionQuestion {public static void main(String[] args) throws IOException {//根据配置文件 re.properties 指定信息…...

在Linux系统上使用Docker部署java项目

一.使用Docker部署的好处&#xff1a; 在Linux系统上使用Docker部署项目通常会大大简化部署流程&#xff0c;因为Docker可以将应用程序及其依赖打包到一个独立的容器中。 Docker打包应用程序时会将其与所有依赖项&#xff08;操作系统、库等&#xff09;一起打包。这样&#…...

【C++】标准库IO查漏补缺

【C】标准库 IO 查漏补缺 文章目录 系统I/O1. 概述2. cout 与 cerr3. cerr 和 clog4. 缓冲区5. 与 printf 的比较 系统I/O 1. 概述 标准库提供的 IO 接口&#xff0c;包含在 iostream 文件中 输入流: cin输出流&#xff1a;cout / cerr / clog。 输入流只有一个 cin&#x…...

python简单易懂的lxml读取HTML节点及常用操作方法

python简单易懂的lxml读取HTML节点及常用操作方法 1. 初始化和基本概念 lxml 是一个强大的pyth库&#xff0c;用于处理XML和HTML文档。它提供了类似BeautifulSoup的功能&#xff0c;但性能更高。在使用lxml时&#xff0c;通常会先解析HTML或XML文档&#xff0c;得到一个Eleme…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...