【数据结构】详解二叉树
文章目录
- 1.树的结构及概念
- 1.1树的概念
- 1.2树的相关结构概念
- 1.3树的表示
- 1.4树在实际中的应用
- 2.二叉树的结构及概念
- 2.1二叉树的概念
- 2.2特殊的二叉树
- 2.2.1满二叉树
- 2.2.2完全二叉树
- 2.3 二叉树的性质
- 2.4二叉树的存储结构
- 2.4.1顺序结构
- 2.4.2链表结构
1.树的结构及概念
1.1树的概念
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
有一个特殊的结点,称为根结点,根结点没有前驱结点除根结点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
因此,树是递归定义的
1.2树的相关结构概念
在一个树中,有下面几种结构概念:
结点的度:一个结点含有的子树的个数称为该结点的度; 如上图:A的为6,我们用一张图来更好的了解:
叶结点或终端结点:度为0的结点称为叶结点; 如上图:B、C、H、I…等结点为叶结点
非终端结点或分支结点:度不为0的结点; 如上图:D、E、F、G…等结点为分支结点
双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点
孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点
兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点
树的度:一棵树中,最大的结点的度称为树的度; 如上图:树的度为6
结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推;
树的高度或深度:树中结点的最大层次; 如上图:树的高度为4
堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:H、I互为兄弟结点
结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先
子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙
森林:由m(m>0)棵互不相交的树的集合称为森林;
这里面的概念我们不需要全都记住,标黄的需要我们重点关注以下;
1.3树的表示
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点 struct Node* pNextBrother; // 指向其下一个兄弟结点 DataType data; // 结点中的数据域
};
在这个方法中,我们用firstchild指针找当前节点的第一个孩子节点(A),再用pnextbrother指针找到后续的孩子节点(B,C)找完之后接着用firstchild找到D,然后重复上面的操作,直到找完为止;
1.4树在实际中的应用
2.二叉树的结构及概念
2.1二叉树的概念
二叉树(Binary Tree) 是由n个结点构成的有限集(n≥0),该集合:
- 或者为空;
- 由一个根结点加上两棵别称为左子树和右子树的二叉树组成;
由上图我们可以得知:
1.一个二叉树不存在度大于2的结点。
2.二是结点的子树有左右之分,不能随意调换,调换后又是一棵新的二叉树。
对于任意一个二叉树都是由以下几种情况复合而成的;
2.2特殊的二叉树
2.2.1满二叉树
满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是
说,如果一个二叉树的层数为K,且结点总数是,则它就是满二叉树。
2.2.2完全二叉树
完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。
对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
** 要注意的是满二叉树是一种特殊的完全二叉树**。
2.3 二叉树的性质
- 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2^( i-1) 个结点.
- 若规定根结点的层数为1,则深度为h的二叉树的最大结点数是2^h -1.
- 对任何一棵二叉树, 如果度为0其叶结点个数为 n,度为2的分支结点个数为 m
,则有n=m+1;- 若规定根结点的层数为1,具有n个结点的满二叉树的深度,h= . (ps:是log以2
为底,n+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否则无右孩子;
2.4二叉树的存储结构
2.4.1顺序结构
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
- 顺序存储
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空
间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺
序存储在物理上是一个数组,在逻辑上是一颗二叉树。
2.4.2链表结构
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是:
链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所
在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面学到高阶数据结构如红黑树等会用到三叉链。
相关文章:
【数据结构】详解二叉树
文章目录 1.树的结构及概念1.1树的概念1.2树的相关结构概念1.3树的表示1.4树在实际中的应用 2.二叉树的结构及概念2.1二叉树的概念2.2特殊的二叉树2.2.1满二叉树2.2.2完全二叉树 2.3 二叉树的性质2.4二叉树的存储结构2.4.1顺序结构2.4.2链表结构 1.树的结构及概念 1.1树的概念…...
MapDB:轻量级、高性能的Java嵌入式数据库引擎
MapDB:轻量级、高性能的Java嵌入式数据库引擎 在今天的软件开发中,嵌入式数据库因其轻便、高效和易于集成而备受欢迎。对于Java开发者来说,MapDB无疑是一个值得关注的选项。MapDB是一个纯Java编写的嵌入式数据库引擎,它提供了高性…...
Rye: 一个革新的Python包管理工具
文章目录 Rye: 一个革新的Python包管理工具Rye的诞生背景Rye的核心特性Rye的安装与使用Rye的优势与挑战Rye的未来展望结语 Rye: 一个革新的Python包管理工具 在Python生态系统中,包管理一直是一个复杂且令人头疼的问题。随着Python社区的不断发展,出现了…...
如何在C#代码中判断当前C#的版本和dotnet版本
代码如下: using System.Reflection; using System.Runtime.InteropServices;var csharpVersion typeof(string).Assembly.GetCustomAttributes(typeof(AssemblyFileVersionAttribute), false).OfType<AssemblyFileVersionAttribute>().FirstOrDefault()?.…...
Linux 36.3@Jetson Orin Nano之系统安装
Linux 36.3Jetson Orin Nano之系统安装 1. 源由2. 命令行烧录Step 1:下载Linux 36.3安装程序Step 2:下载Linux 36.3根文件系统Step 3:解压Linux 36.3安装程序Step 4:解压Linux 36.3根文件系统Step 5:安装应用程序Step …...
案例实践 | 基于长安链的首钢供应链金融科技服务平台
案例名称-首钢供应链金融科技服务平台 ■ 建设单位 首惠产业金融服务集团有限公司 ■ 用户群体 核心企业、资金方(多为银行)等合作方 ■ 应用成效 三大业务场景,共计关联29个业务节点,覆盖京票项目全部关键业务 案例背景…...
Vue3实战笔记(55)—Vue3.4新特性揭秘:defineModel重塑v-model,拥抱高效双向数据流!
文章目录 前言defineModel() 基本用法总结 前言 v-model 可以在组件上使用以实现双向绑定。 从 Vue 3.4 开始,推荐的实现方式是使用 defineModel() 宏 defineModel() 基本用法 定义defineModel(): <!-- Child.vue --> <script setup> con…...
C++ | Leetcode C++题解之第123题买卖股票的最佳时机III
题目: 题解: class Solution { public:int maxProfit(vector<int>& prices) {int n prices.size();int buy1 -prices[0], sell1 0;int buy2 -prices[0], sell2 0;for (int i 1; i < n; i) {buy1 max(buy1, -prices[i]);sell1 max(…...
微信小程序中Button组件的属性值和用法详解
在微信小程序开发中,Button组件是非常常用的UI组件之一,它可以让用户进行交互操作,比如提交表单、跳转页面等。了解Button组件的属性值和用法对于开发者来说至关重要。 1. Button组件简介 简要介绍Button组件在小程序中的作用和重要性&…...
等保测评 | 等保测评简介及流程具体是什么?
等保测评是指对信息系统进行安全性评估和测试,以确保其符合国家相关等级保护要求。在当前信息时代,各类机构和企业面临着日益严峻的网络安全风险,等保测评成为了保障信息系统安全的重要手段之一。本文将介绍等保测评的基本概念、流程和重要性…...
CompassArena 司南大模型测评--代码编写
测试角度 要说测试模型,对咱们程序员来说,那自然是写代码的能力强不强比较重要了。那么下面我们以 leetcode 中的一道表面上是困难题的题目来考考各家大模型,看看哪个才应该是咱们日常写程序的帮手。 部分模型回答 问题部分如下截图&#…...
叉积和法向量学习笔记
目录 叉积用的内积 相似点 给定平面上的两个向量 A 和 B,叉积和法向量相等吗 理解这点的关键: 结论: 叉积判断平面内两个向量是否相交 叉积(Cross Product)和法向量(Normal Vector)确实有…...
YZW900规格书
title: “深圳市沃进科技有限公司” 深圳市沃进科技有限公司 TOP视图 特性 异地组网,远程访问有线/无线备份单模双卡备份5G转有线,5G转WIFI2.4G5.8G双频WIFI三网口,WAN/LAN可切换软硬件看门狗智能防掉线云平台、客户端远程管理安装支架安装铝…...
9岁学生学什么编程好一些:探索编程启蒙的奥秘
9岁学生学什么编程好一些:探索编程启蒙的奥秘 在数字时代,编程已逐渐成为一项基本技能。对于9岁的学生来说,选择适合的编程课程或平台,对于培养逻辑思维、创新思维以及解决问题的能力至关重要。那么,9岁学生学什么编程…...
Java反射实战指南:反射机制的终极指南
1. 反射机制简介 在Java中,反射机制提供了一种强大的工具,用于在运行时检查类、接口、字段和方法。但它的重要性不止于此,它允许程序动态加载、探索和使用编译时完全未知的代码。这种能力是Java语言支持的一种“动态”特性,使得J…...
高效训练超越LoRA,北航发布MoRA
什么!LoRA我都没有学懂,又出现了MoRA??? LoRA作为当下最火热的大语言模型参数高效微调技术,正在以前所未有的速度迭代更新。从最初的LoRA到陆续推出的LoRA、DoRA、AsyLoRA等变体,LoRA家族可谓是…...
【Spring】Spring之依赖注入源码解析(上)
目录 Spring中到底有几种依赖注入的方式? 手动注入 自动注入 XML的autowire自动注入 Autowired注解的自动注入 寻找注入点 桥接方法 注入点进行注入 字段注入 Set方法注入 Spring中到底有几种依赖注入的方式? 首先分两种: 手动注…...
HBase 常用 shell 操作
下面给大家介绍一些HBase 常用 shell 操作,各位看官看好了啦,我要献丑了。 进入 HBase 客户端命令操作界面 $ bin/hbase shell查看帮助命令 > help查看当前数据库中有哪些表 > list创建一张表 创建 user 表,包含 info、data 两个列…...
【区分vue2和vue3下的element UI InputNumber 计数器组件,分别详细介绍属性,事件,方法如何使用,并举例】
在 Vue 2 中,Element UI 提供了 el-input-number 组件作为计数器组件,用于处理数字输入。而在 Vue 3 中,Element Plus 同样提供了类似的组件,但可能有一些属性、事件或方法的细微差异。下面我将分别介绍 Vue 2 的 Element UI 和 V…...
科普健康短视频:成都鼎茂宏升文化传媒公司
科普健康短视频:引领健康知识新潮流 在数字化时代的浪潮中,短视频以其短小精悍、直观易懂的特点,迅速成为大众获取信息的重要渠道。其中,科普健康短视频更是凭借其科学、权威、实用的内容,吸引了大量关注健康的观众。…...
Amis源码构建 sdk版本
建议在linux环境下构建(mac环境下也可以),需要用到sh脚本(amis/build.sh)。 Js sdk打包是基于fis进行编译打包的,具体可见fis-conf.js: amis-master源码下载:https://github.com/baidu/amis g…...
【MySQL数据库】:MySQL复合查询
目录 基本查询回顾 多表查询 自连接 子查询 单行子查询 多行子查询 多列子查询 在from子句中使用子查询 合并查询 前面我们讲解的mysql表的查询都是对一张表进行查询,在实际开发中这远远不够。 基本查询回顾 【MySQL数据库】:MySQL基本查…...
PS Mac Photoshop 2024 for Mac[破]图像处理软件[解]PS 2024安装教程[版]
Mac分享吧 文章目录 效果一、准备工作二、开始安装1、Anticc简化版安装1.1双击运行软件,安装1.2 解决来源身份不明的开发者问题**此代码为打开:系统偏好设置 – 隐私与安全性,中的【任何来源】,如下图:**1.3 再次运行…...
深入URP之Shader篇16: UNITY_BRANCH和UNITY_FLATTEN
Shader中的if分支 我们在shader中写if语句,例如: if(a>0){//do some cool thing }else{//do other cool thing }实际上,编译器会进行优化,以及处理成多种不同的情况。比如编译器会将if和else展开,分别执行其中的代…...
5.25.1 用于组织病理学图像分类的深度注意力特征学习
提出了一种基于深度学习的组织病理学图像分类新方法。我们的方法建立在标准卷积神经网络 (CNN) 的基础上,并结合了两个独立的注意力模块,以实现更有效的特征学习。 具体而言,注意力模块沿不同维度推断注意力图,这有助于将 CNN 聚焦于关键图像区域,并突出显示判别性特征通…...
uni-app+php 生成微信二维码 分销海报
主要代码如下,可直接复制调试参数: //查询当前用户是否有分销海报public function user_poster(){$this->checkAuth();//查询会员信息$user $this->getUserInfoById($this->user_id);if(!empty($user[distribution_img])){$result[data] $use…...
已解决java.lang.annotation.AnnotationFormatError: 注解格式错误的正确解决方法,亲测有效!!!
已解决java.lang.annotation.AnnotationFormatError: 注解格式错误的正确解决方法,亲测有效!!! 亲测有效 报错问题解决思路 解决方法解决方法1. 检查注解定义2. 验证注解使用位置3. 检查注解参数4. 更新依赖库5. 示例代码 解决思路…...
使用 EBS 和构建数据库服务器并使用应用程序与数据库交互
实验 4:使用 EBS 实验概览 本实验着重介绍 Amazon Elastic Block Store (Amazon EBS),这是一种适用于 Amazon EC2 实例的重要底层存储机制。在本实验中,您将学习如何创建 Amazon EBS 卷、将其附加到实例、向卷应用文件系统,然后进…...
pom文件新增依赖时异常问题定位技巧
今天新增复制两个依赖到项目时,莫名其妙一个爆红artifactId和version,另一个爆红version,但放其他项目却正常,非常莫名其妙。经过一番折腾,终于发现不知道什么时候不小心多写了一个单独的导致的,但是这个异…...
【小白专用24.5.30已验证】Composer安装php框架thinkPHP6的安装教程
一、框架介绍 1、框架简介和版本选择 Thinkphp是一种基于php的开源web应用程序开发框架ThinkPHP框架,是免费开源的、轻量级的、简单快速且敏捷的php框架。你可以免费使用TP框架,甚至可以将你的项目商用; ThinkPHP8.0 是目前框架正式版的最新版…...
ch4网络层---计算机网络期末复习(持续更新中)
网络层概述 将分组从发送方主机传送到接收方主机 发送方将运输层数据段封装成分组 接收方将分组解封装后将数据段递交给运输层网络层协议存在于每台主机和路由器上 路由器检查所有经过它的IP分组的分组头 注意路由器只有3层(网络层、链路层、物理层) 网络层提供的服务 一…...
数据库(12)——DQL聚合查询
常见的聚合函数 将一列数据作为一个整体,进行纵向计算。 函数功能count统计数量max最大值min最小值avg平均值sum求和 语法 SELECT 聚合函数 (字段列表)FROM 表名; 示例 这是我们的原始表: 求人物总数 select count(id) from in…...
MYSQL四大操作——查!查!查!
目录 简洁版: 详解版: SQL通用语法: 分类: 1. DDL —库 1.1 查询: 1.2 创建: 1.3 删除 1.4 使用库 2. DDL—表 2.1 查询 2.1.1 查询当前库的所有表: 2.1.2 查询表结构 : 2.1.…...
Linux静态库与动态库加载
了解库: 关于库相比大家之前肯定使用过,比如C/C里面的标准库,STL里面的各种库,我们在调用STL里的容器时都需要使用库,那么库到底是什么呢? 库的本质就是可执行程序的"半成品" 我们先来回顾一下代…...
Whisper-AT:抗噪语音识别模型(Whisper)实现通用音频事件标记(Audio Tagger)
本文介绍一个统一音频标记(Audio Tagger)和语音识别(ASR)的模型:Whisper-AT,通过冻结Whisper的主干,并在其之上训练一个轻量级的音频标记模型。Whisper-AT在额外计算成本不到1%的情况下…...
K8s:Pod初识
Pod Pod是k8s处理的最基本单元。容器本身不会直接分配到主机上,封装为Pod对象,是由一个或多个关系紧密的容器构成。她们共享 IPC、Network、和UTS namespace pod的特征 包含多个共享IPC、Network和UTC namespace的容器,可直接通过loaclhos…...
HCIP-Datacom-ARST自选题库__MAC【14道题】
一、单选题 1.缺省情况下,以下哪种安全MAC地址类型在设备重启后表项会丢失? 黑洞MAC地址 Sticky MAC地址 安全动态MAC地址 安全静态MAC地址 2.华为交换机MAC地址表中的动态sticky MAC地址的默认老化时间是多少秒? 300 不会老化 400 500 3.华为交换机MA…...
Go基础编程 - 03 - init函数、main函数、_(下划线)
目录 1. init 函数2. main 函数3. init 函数与 main 函数异同4. _ (下划线)示例 1. init 函数 Go语言中,init 函数用于包(package)的初始化。具有以下特征: 1. init 函数用于程序执行前包的初始化,如初始化变量等。2…...
【TensorFlow深度学习】LeNet-5卷积神经网络实战分析
LeNet-5卷积神经网络实战分析 LeNet-5卷积神经网络实战分析:从经典模型到现代实践LeNet-5的历史背景LeNet-5网络架构实战代码解析实战分析结论 LeNet-5卷积神经网络实战分析:从经典模型到现代实践 在深度学习的历程中,LeNet-5无疑是一座里程…...
错误发生在尝试创建一个基于有限元方法的功能空间时
问题: index cell.index(#直接使用从0开始的索引if0<1ndex<10: #正集流体 subdomains_x[cell,index(] 1 fem1 /usr/bin/python3.8 /home/wy/PycharmProjects/pythonProject2/fem1.pyUnknown ufl object type FiniteElementTraceback (aost recent call last)…...
【八股】Hibernate和JPA:理解它们的关系
在Java开发中,持久化框架是至关重要的工具,它们帮助开发者将Java对象与关系数据库中的数据进行映射和管理。Hibernate和JPA(Java Persistence API)是两个广泛使用的持久化框架。那么,Hibernate和JPA之间到底是什么关系…...
C++类型参数技术以及常见的类型擦除容器
文章目录 一、类型擦除的作用二、常见的类型擦除容器1.std::any2.std::function3.std::shared_ptr\<void\>和 std::unique_ptr\<void\>4.总结 三、实现一个any参考 类型擦除(Type Erasure)是一种编程技术,通过它可以在运行时存储…...
SpringBoot如何缓存方法返回值?
Why? 为什么要对方法的返回值进行缓存呢? 简单来说是为了提升后端程序的性能和提高前端程序的访问速度。减小对db和后端应用程序的压力。 一般而言,缓存的内容都是不经常变化的,或者轻微变化对于前端应用程序是可以容忍的。 否…...
C#的web项目ASP.NET
添加实体类和控制器类 using System; using System.Collections.Generic; using System.Linq; using System.Web;namespace WebApplication1.Models {public class Company{public string companyCode { get; set; }public string companyName { get; set; }public string com…...
Spring MVC 源码分析之 DispatcherServlet#getHandlerAdapter 方法
前言: 前面我们分析了 Spring MVC 的工作流程源码,其核心是 DispatcherServlet#doDispatch 方法,我们前面分析了获取 Handler 的方法 DispatcherServlet#getHandler 方法,本篇我们重点分析一下获取当前请求的适配器 HandlerAdapt…...
假设检验学习笔记
1. 假设检验的基本概念 1.1. 原假设(零假设) 对总体的分布所作的假设用表示,并称为原假设或零假设 在总体分布类型已知的情况下,仅仅涉及总体分布中未知参数的统计假设,称为参数假设 在总体分布类型未知的情况下&#…...
vue3 watch学习
watch的侦听数据源类型 watch的第一个参数为侦听数据源,有4种"数据源": ref(包括计算属性) reactive(响应式对象) getter函数 多个数据源组成的数组。 //ref const xref(0)//单个ref watch(x,(newX)>{console.…...
推荐的Pytest插件
推荐的Pytest插件 Pytest的插件生态系统非常丰富,以下是一些特别推荐的Pytest插件: pytest-sugar 这个插件改进了Pytest的默认输出,添加了进度条,并立即显示失败的测试。它不需要额外配置,只需安装即可享受更漂亮、更…...
C语言 | Leetcode C语言题解之第124题二叉树中的最大路径和
题目: 题解: /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/ int max; int dfs(struct TreeNode* root){if(!root) return 0;int left dfs(root->left…...
Linux综合实践(Ubuntu)
目录 一、配置任务 1.1 配置该服务器的软件源为中科大软件源 1.2 安装相关软件openssh-server和vim 1.3 设置双网卡,网卡1为NAT模式,网卡2为桥接模式(桥接模式下,使用静态ip,该网卡数据跟实验室主机网络设置相似,除…...