【数据结构】树的概念
Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。
🌈个人主页:主页链接
🌈算法专栏:专栏链接
我会一直往里填充内容哒!
🌈LeetCode专栏:专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出
🌈代码仓库:Gitee链接
🌈点击关注=收获更多优质内容🌈
![]()
本章来记录下最近新学习的树的基础概念以及基础公式,大概会分为几个章节讲完。
目录
1.初识树
树的相关定义:
在结构中的存储:
2.二叉树的概念
特殊的二叉树:
满二叉树:
完全二叉树:
二叉树公式:
题目:
完结撒花:
1.初识树
树之所以被称为树是因为
现实生活中的树是长这样的:

数据结构中树是长这样的,看起来就像将其倒过来而形成的。所以在数据结构中,我们把长这样形状(由一个根,若干个节点与叶子组合起来,且各个节点之间有且只有一条路到达根)称为树

除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继。 也就是说,每一颗子树都是不相交的。
这里引入一些概念:
除根节点外,每个节点有且只有一个父节点
一颗N个节点的树有N-1条边
树的相关定义:
节点的度:该节点拥有的子树个数.如A为6
叶子:度为0的节点
父亲节点/孩子节点:若一个节点有子节点,则该节点为子节点的父亲节点,反之该子节点为孩子节点
兄弟节点:两个拥有同样父亲的节点
节点层次/树的深度(高度):该节点距离根的层数称为层次,根为第一层.深度为最大的层次
节点祖先:从根到该节点所经分治的所有节点.例如A为所有节点的祖先
节点子孙:与祖先定义相反:以某节点为根,则其所有子节点都为其节点子孙

在结构中的存储:
因为树的定义为:一个节点可以拥有若干个子节点.所以我们没有办法通过一个节点来直接记录其所有子节点.所以我们通常才用以下这种模式来记录.

也就是一个节点中有两个指针分别指向子节点与其兄弟节点.还有一个变量来存储数据
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
2.二叉树的概念
相比于树,二叉树具有以下特点:每个数的度为[0,1,2]三种可能,也就是一个节点最多有两个子节点.
且二叉树的两个节点顺序不能颠倒,具有左右节点的概念

特殊的二叉树:
满二叉树:
同一层下都有/无子节点,在概念上来看就是,节点总数为2^k-1其就为满二叉树

完全二叉树:
除去最后一层,为满二叉树,最后一层从左向右分布子节点.满二叉树为特殊的完全二叉树

二叉树公式:
根的深度为1,部分教材上为0,但若这棵树是空树(没有节点)按照教材上的定义,此时深度还是为0嘛?所以统一按1来计算
双亲节点计算:(child-1)/2
左儿子:(parent*2+1)
右儿子:(parent*2+2)

对于一颗非空二叉树,其一层上最多有2^(h-1)个节点,反之其深度为log(n+1)
深度为h的二叉树,其节点最大总数为2^h-1,
二叉树度为0的节点为n0,度为1的节点为n1,度为2的节点为n2,则有以下关系:n0=n2+1
题目:

用到n0=n2+1的公式,则n0=200

用到n0=n2+1的公式,2n=n2+1+n2+n1 根据完全二叉树的定义,n1只会有0个或者1个.所以n0=n
完结撒花:
🌈本篇博客的内容【数据结构:树的概念】已经结束。
🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。
🌈诸君,山顶见!
相关文章:
【数据结构】树的概念
Halo,这里是Ppeua。平时主要更新C语言,C,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接 我会一直往里填充内容哒! &…...
Qt Glog toStdWString转char* 中文乱码
#include <QTextCodec>void LogWriter::init(void) {InitGoogleLogging("ui-fundus");char log_path[256] {0};FLAGS_stderrthreshold GLOG_INFO; // INFO WARNING ERROR FATAL, 是输出到stderr(app Output/cli)的阀值FLAGS_alsologtostderr false; // 当这…...
基于线性Kalman观测器(LKF)的2、4、7自由度悬架主动控制合集
目录 前言 1. 1/4车悬架仿真分析 2. 1/2车悬架仿真分析 3. 整车车悬架仿真分析 3.1 KF观测状态 3.2性能指标 4 .KF调参总结 5.文章总结 前言 对于kalman的原理介绍在上篇文章中已经做了详尽剖析,本篇进行实战,将其应用于悬架系统,其实…...
第二章 作业(6789B)【编译原理】
第二章 作业【编译原理】前言推荐第二章 作业678911最后前言 以下内容源自《编译原理》 仅供学习交流使用 推荐 无 第二章 作业 6 6.令文法G6为 N→D|ND D→0|1|2|3|4|5|6|7|8|9 (1)G6的语言L(G6)是什么? (2)给出句子0127、34和568的最左推导和最右推导。 (…...
【java】连续最大和、统计回文
目录 1.连续最大和 2.统计回文 1.连续最大和 链接:连续最大和_牛客题霸_牛客网 (nowcoder.com) 描述:一个数组有 N 个元素,求连续子数组的最大和。 例如:[-1,2,1],和最大的连续子数组为[2,1],其和为 3 输…...
AI真的快让我们失业了,从ChatGPT到Midjourney
参考文章: https://mp.weixin.qq.com/s/3RdHPPhYgDfB6KY6Y9Sk2A跟AI有关的新闻,一个接着一个。前一天你还和往常一样进入梦乡,第二天醒来就能被新的AI新闻“炸弹”震得心惊。 以ChatGPT为代表的AI语言模型,以Midjourney为代表的…...
JVM学习 GC垃圾回收机制 (堆内存结构、GC分类、四大垃圾回收算法)
🤖 作者简介:努力的clz ,一个努力编程的菜鸟 🐣🐤🐥 👀 文章专栏:《JVM 学习笔记》 ,本专栏会专门记录博主在学习 JVM 中学习的知识点,以及遇到的问题。 …...
ChatGPT 有哪些神奇的使用方式?
ChatGPT在语言处理领域有着非常广泛的应用,可以用来进行语音识别、文本摘要、问答系统、机器翻译、智能客服、情感分析、智能写作等方面的应用。随着技术的不断发展和进步,ChatGPT在未来的应用场景和领域也将会有更加广泛的拓展和应用。ChatGPT可以应用于…...
【JavaEE】Java设计模式-单例模式(饿汉式与懒汉式)
目录 1.设计模式是啥? 2.单例模式 2.1什么是单例模式 2.2饿汉模式 2.3懒汉模式 3.懒汉模式与饿汉模式的区别 3.1.线程安全方面 3.2.资源加载和性能 4.如何保证懒汉模式的线程安全 1.设计模式是啥? 设计模式是前人经过总结,通过…...
(算法基础)朴素版Prim算法
适用情景在最小生成树问题当中,涉及到权重和最小值。并且这个图是稠密图(n^2 ~ m)的情形下时间复杂度O(N^2)算法解释先得知道一下什么是无向图的生成树,树总该知道的吧,生成树就是包含这个无向图中的n个点,并且有n-1条边ÿ…...
第十四届蓝桥杯三月真题刷题训练——第 23 天
目录 第 1 题:长草 题目描述 输入描述 输出描述 输入输出样例 运行限制 代码: 思路: 第 2 题:蓝肽子序列_LCS_最长公共子序列dp问题 题目描述 输入描述 输出描述 输入输出样例 运行限制 代码: 思路&am…...
基于springboot实现医院信息管理系统【源码+论文】
基于springboot实现医院信管系统演示开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包…...
CODESYS增量式PID功能块(ST完整源代码)
增量式PID的详细算法公式和博途源代码,请参看下面的文章链接: 博途1200/1500PLC增量式PID算法(详细SCL代码)_博图scl语言pid增量编码器_RXXW_Dor的博客-CSDN博客SMART200PLC增量式PID可以参看下面这篇博文,文章里有完整的增量式PID算法公式,这里不在赘述西门子SMARTPLC增量…...
代码质量提升,代码扫描 review 之 Codacy 工具使用
目录一、什么是Codacy二、GitHub 上使用 Codacy三、Codacy上导入GitHub项目一、什么是Codacy Codacy 是用于代码 review 检测(即代码审查)的工具,目前支持对40多种编程语言检测,如 c、c、c#、java 、python、javascript 等。 Codacy 可用于 GitHub 和 …...
Centos Linux 正确安装 Redis 的方式
官方文档 Getting started with Redis | Redis 第一步 、下载源代码 源代码的下载方式有很多种,可以去源代码仓库下载,或者使用下面的命令下载 wget https://download.redis.io/redis-stable.tar.gz 第二步 、编译代码 tar -xzvf redis-stable.tar.…...
C++Primer第五版【阅读笔记】
CPrimer第五版 阅读笔记 第1章开始1.1 编写一个简单的C程序1.1.1 编译、运行程序1.2 初识输入输出第1章开始 学习一门新的程序设计语言的最好方法就是练习编写程序。 1.1 编写一个简单的C程序 每个C程序都包含一个或多个函数,其中一个必须命名为 main,…...
ERD Online 4.0.11 在线数据库建模、元数据协作平台(免费、私有部署)
ERD Online 是全球第一个开源、免费在线数据建模、元数据管理平台。提供简单易用的元数据设计、关系图设计、SQL查询等功能,辅以版本、导入、导出、数据源、SQL解析、审计、团队协作等功能、方便我们快速、安全的管理数据库中的元数据。 4.0.11 ❝ :memo: fix(erd):…...
3.数组算法、动态规划
文章目录数组算法1.数组表示2.基本操作3.插入操作算法实例1实例2输出3.删除操作算法实例1输出4.搜索操作算法实例2输出5.更新操作算法实3例输出2.动态规划对照实例1数组算法 Array是一个容器,可以容纳固定数量的项目,这些项目应该是相同的类型。大多数数…...
项目管理工具哪个好?最新排名
项目管理工具当下已经成为项目团队的重要榜首,一款合适好用的项目管理工具可以帮助处理很多机械化工作,将管理者更多精力投入到更有价值的工作中,还可以帮助团队组织和计划项目,跟踪进度,处理预算和协作。该如何挑选帮…...
650. 只有两个键的键盘——【Leetcode每日一题】
650. 只有两个键的键盘 最初记事本上只有一个字符 A 。你每次可以对这个记事本进行两种操作: Copy All(复制全部):复制这个记事本中的所有字符(不允许仅复制部分字符)。Paste(粘贴)…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
java高级——高阶函数、如何定义一个函数式接口类似stream流的filter
java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用(Math::max) 2 函数接口…...
【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)
旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据!该数据集源自2025年4月发表于《地理学报》的论文成果…...
Python环境安装与虚拟环境配置详解
本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南,适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者,都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...
前端工具库lodash与lodash-es区别详解
lodash 和 lodash-es 是同一工具库的两个不同版本,核心功能完全一致,主要区别在于模块化格式和优化方式,适合不同的开发环境。以下是详细对比: 1. 模块化格式 lodash 使用 CommonJS 模块格式(require/module.exports&a…...
