【数据结构】树的概念理解和性质推导(保姆级详解,小白必看系列)

目录

一、前言

🍎 为什么要学习非线性结构 ---- 树(Tree)

💦 线性结构的优缺点

 💦 优化方案 ----- 树(Tree)

💦 树的讲解流程

 二、树的概念及结构

🍐 树的概念

🍉 树的相关定义

 🍓 树的表示方法

 🍌 树在现实中的应用

 🍊 树的性质(超重要哦!!)

 💦 性质1:树中的节点数等于所有节点度数加 1

 💦 性质2:度为 m 的树中第 i 层至多有 m^i-1 个节点(i>=1)

 💦 性质3:高度为 h 的 m 叉树至多有  m^h-1/m-1 个节点​

 💦 性质4:具有n个结点的m叉树的最小高度为⌈logm(n*(m-1)+1)⌉

 三、共勉


一、前言

         在之前的几篇文章中已经详细的介绍了数据结构中的顺序表、链表、栈、队列、数组等,都是一对一的线性关系。本文将开始介绍一种新的数据结构 --------- (一对多的非线性关系)。

         那么肯定有 老铁 要发问啦,有线性结构去存储数据,为什么还要用非线性的结构去存储呢 ?它们之间有什么区别呢 ? 接下里我将依次给大家解惑,让大家真正的搞懂数据结构,学习起来才有动力。

🍎 为什么要学习非线性结构 ---- 树(Tree)

💦 线性结构的优缺点

在线性结构中,无论是顺序存储,还是链式存储,线性表均有其优缺点:

🔑顺序表优点:

1️⃣:顺序存储可以在 O(1) 的时间内找到特定次序的元素(下标的随机访问)

2️⃣:CPU 高速缓存,命中率较高

🔑顺序表缺点: 

1️⃣:顺序存储在,数据中间、头部 的插入和删除元素需要挪动大量元素,需要时间O(n)

2️⃣:  顺序存储时,会出现空间不足,只能进行空间的扩容(异地扩容代价比较大)


🔑链表优点:

1️⃣:在任意位置进行数据的插入和删除的效率高,所需时间为O(1)

2️⃣:  按需申请空间和释放,不存在扩容

🔑链表的缺点:

1️⃣:在寻找特定次序的元素需要从链表头部向后查找,需要时间O(n)

2️⃣:  CPU高速缓存,命中率低 


⭐ :其实链表和顺序表是一个互补的数据结构
⭐ :链表详解

⭐ :顺序表详解

 💦 优化方案 ----- 树(Tree)

⭐:树形结构:很好的结合了顺序表和链表的优点,可以在O(logn)的时间内完成查找、更新、插入、删除等操作,在实际的应用中,很多算法可以借助于树形结构高效的实现很多功能。

💦 树的讲解流程

此时此刻大家肯定很想了解什么是,在本篇博客中,并不能把所有树的结构在此篇文章中进行详细的介绍,我会通过步步延申的方式去讲解树。


树 ➡ 二叉树➡ 搜索二叉树 ➡ 平衡搜索二叉树 (AVL树和红黑树) ➡ M叉多叉平衡搜索树 (B树和B+树)

 

 二、树的概念及结构

🍐 树的概念

1️⃣:是一种非线性的数据结构,它是由 n (n>=0) 个有限结点组成一个具有层次关系的集合。

2️⃣: 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下。树根可以发出多个分支,每个分支也可以继续发出分支,树枝之间是不想交的。
3️⃣ :树有一个特殊的结点,称为
根结点,根节点没有前驱结点

4️⃣:除根节点外,其余结点被分为 M (M>0) 个互不相交的集合 T1、T2 … 、Tm,其中每一个集合 Ti (1<=i<=m) 又是一棵结构与树类似的子树,每棵子树的根结点有且只有一个前驱,可以有0个或多个后继

5️⃣:因此,树是递归定义的

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

▶  子树 是不相交的

▶  除了根节点外,每个节点有且仅有一个父节点

▶  一棵 N 个节点的树有 N-1 条连

🍉 树的相关定义

1️⃣ 节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A 的为6

2️⃣ 叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点

3️⃣ 非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G…等节点为分支节点

4️⃣ 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A 是 B 的父节点

5️⃣ 孩子节点或子节点:个节点含有的子树的根节点称为该节点的子节点; 如上图:B 是 A 的孩子节点

6️⃣ 兄弟节点:具有相同父节点的节点互称为兄弟节点 (这里指的是亲兄弟,而非表堂兄弟); 如上图:B、C 是兄弟节点

7️⃣ 树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为 6

8️⃣ 节点的层次:从根开始定义起,根为第 1 层,根的子节点为第 2 层, 以此类推;如上图:树的层次为 4

9️⃣ 树的高度或深度:树中节点的最大层次 (这里有 2 种说法:其一,根算 0,其二,根算 1); 如上图:树的高度为 4
   这里推荐理解其二,因为:
  
当要算空树的高度是多少时,按其一的理解,高度是 -1;按其二的理解,高度是 0
   当要算只有一个根节点的树的高度是多少时,按其一的理解,高度是 0;按其二的理解,高度是 1

🔟 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I 互为兄弟节点

1️⃣1️⃣ 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A 是所有节点的祖先

1️⃣2️⃣ 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是 A 的子孙

1️⃣3️⃣ 森林:由 m(m>0) 棵互不相交的树的集合称为森林,并查集就是一个森林
 

 🍓 树的表示方法

1️⃣: 树结构相对线性表就比较复杂了,要存储表示起来比较麻烦,既要保存值域,也要保存结点和结点之间的关系。

2️⃣: 实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法

 ⚠ 注意:对于树的定义其实并不好定义,因为其中有许多未知的因素

1️⃣明确说明树的度是多少,比如树的度是 6

struct TreeNode
{int data;//这种结构其实是很浪费的,因为最大的度是6,但往下可能并没有那么多struct TreeNode* subs[6];//指针数组
}

⚠ 注意:这种结构其实是很浪费的,因为最大的度是6,但往下可能并没有那么多

 2️⃣:双亲表示法

struct TreeNode
{int data;struct TreeNode* parent;
}

⚠ 注意:这种结构主要应用在------并查集

 3️⃣:左孩子右兄弟表示法 (比较实用)

typedef int DataTpye;
struct Node
{struct Node* _firstChild1;//第一个孩子节点(如有多个孩子,那么只指向最左边的)struct Node* _pNextBrother;//指向下一个兄弟节点DataType _data;//节点中的数据域
}

 🍌 树在现实中的应用

❗ 以下为 Linux 下的目录树 ❗

由此可知,在用树表示目录数据结构中,从根目录到任何数据文件,仅有唯一一条路径可以达到,因为树的结构不是相交的。

 🍊 树的性质(超重要哦!!)

 

💦 性质1:树中的节点数等于所有节点度数加 1

✨:从上图可知,有 12 个节点  ,A的度为:3, B的度为2, C 的度为1, D的度为2, E的度为1, F的度为0, G的度为2, H的度为0 , I的度为0,J的度为0,K的度0,L的度为0。


✨:由性质 1 可知 树的节点个数 = 每个节点的度数 + 1 

所以上图 树的节点数 = (3+2+1+2+1+0+2+0+0+0+0+0)+1 = 12

 💦 性质2:度为 m 的树中第 i 层至多有 m^i-1 个节点(i>=1)


 💦 性质3:高度为 h 的 m 叉树至多有  m^h-1/m-1 个节点


 

 💦 性质4:具有n个结点的m叉树的最小高度为⌈logm(n*(m-1)+1)⌉



 

 三、共勉

以下就是我对数据结构---的理解,如果有不懂和发现问题的小伙伴,请在评论区说出来哦,同时我还会继续更新对数据结构-------二叉树请持续关注我哦!!!!!  

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/145682.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QCefView 简介

什么是QCefView QCefView 是为 Qt 开发的一个封装集成了CEF(Chromium Embedded Framework)库的Wdiget UI组件。使用QCefView可以充分发挥CEF丰富强大的Web能力&#xff0c;快速开发混合架构的应用程序。它不需要开发者理解CEF的细节&#xff0c;能够在Qt中更容易的使用CEF&…

NLP 项目:维基百科文章爬虫和分类 - 语料库阅读器

塞巴斯蒂安 一、说明 自然语言处理是机器学习和人工智能的一个迷人领域。这篇博客文章启动了一个具体的 NLP 项目&#xff0c;涉及使用维基百科文章进行聚类、分类和知识提取。灵感和一般方法源自《Applied Text Analysis with Python》一书。 在接下来的文章中&#xff0c;我将…

Android 编译插桩操纵字节码

本文讲解如何编译插桩操纵字节码。 就使用 ASM 来实现简单的编译插桩效果&#xff0c;通过插桩实现在每一个 Activity 打开时输出相应的 log 日志。实现思路 过程主要包含两步&#xff1a; 1、遍历项目中所有的 .class 文件​ 如何找到项目中编译生成的所有 .class 文件&#…

初识多线程

一、多任务 现实中太多这样同时做多件事的例子了&#xff0c;例如一边吃饭一遍刷视频&#xff0c;看起来是多个任务都在做&#xff0c;其实本质上我们的大脑在同一时间依旧只做了一件事情。 二、普通方法调用和多线程 普通方法调用只有主线程一条执行路径 多线程多条执行路径…

xPortPendSVHandler任务切换流程

__asm void xPortPendSVHandler( void ) { extern uxCriticalNesting; extern pxCurrentTCB; extern vTaskSwitchContext; PRESERVE8 mrs r0, psp isb//指令同步命令&#xff0c; ldr r3, pxCurrentTCB /* Get the location of the current TCB. */ ldr r2, [r3]//r2保存…

【面试经典150 | 矩阵】螺旋矩阵

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;模拟方法二&#xff1a;按层模拟 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于…

flink选择slot

flink选择slot 在这个类里修改 package org.apache.flink.runtime.resourcemanager.slotmanager.SlotManagerImpl; findMatchingSlot(resourceProfile)&#xff1a;找到满足要求的slot&#xff08;负责从哪个taskmanager中获取slot&#xff09;对应上图第8&#xff0c;9&…

[vue-admin-template实战笔记]

1.克隆项目 git clone gitgitee.com:panjiachen/vue-admin-template.git 2.安装依赖 npm install 3.运行项目就会自动打开网页&#xff0c;并且热部署插件 npm run dev 4.查看代码 //将vue-admin-template拖入到idea中即可查看代码 1)并且发现&#xff0c;常用的东西已经集…

从零手搓一个【消息队列】创建核心类, 数据库设计与实现

文章目录 一、创建核心类1, 交换机2, 交换机类型3, 队列4, 绑定5, 交换机转发 & 绑定规则6, 消息7, 消息属性 二、数据库设计1, 使用 SQLite2, 使用 MyBatis2.1, 创建 Interface2.2, 创建 xml 文件 三、硬盘管理 -- 数据库1, 创建 DataBaseManager 类2, init() 初始化数据库…

什么是AI客流量算法?如何应用在实际场景中?

客流量分析算法简而言之就是一种利用数据分析和机器学习技术进行人流量统计、预测和分析的算法。它能够根据不同的数据来源&#xff0c;如摄像头、传感器等&#xff0c;对特定区域内的客流量进行实时监测和分析&#xff0c;并通过对历史数据的综合分析&#xff0c;提供客流趋势…

ARM-day2

1、1到100累加 .text .global _start_start:MOV r0, #1ADD r1,r0, #1fun:ADD r0,r0,r1ADD r1,r1, #1cmp r1, #0x65moveq PC,LRbl funstop:b stop.end2、思维导图

Java基础---第十篇

系列文章目录 文章目录 系列文章目录一、说说Java 中 IO 流二、 Java IO与 NIO的区别(补充)三、java反射的作用于原理一、说说Java 中 IO 流 Java 中 IO 流分为几种? 按照流的流向分,可以分为输入流和输出流; 按照操作单元划分,可以划分为字节流和字符流; 按照流的角色…

java导出word(含图片、表格)

1.pom 引入 <!--word报告生成依赖--><dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>4.1.2</version></dependency><dependency><groupId>org.apache.poi</groupI…

【单片机】12-串口通信和RS485

1.通信有关的常见概念 区分&#xff1a;串口&#xff0c;COM口&#xff0c;UART&#xff0c;USART_usart和串口区别-CSDN博客 串口、COM口、UART口, TTL、RS-232、RS-485区别详解-CSDN博客 1.什么是通信 &#xff08;1&#xff09;人和人之间的通信&#xff1a;说话&#xff…

腾讯云 Cloud Studio 实战训练营结营活动获奖公示

点击链接了解详情 “腾讯云 Cloud Studio 实战训练营” 是由腾讯云联合 CSDN 推出的系列开发者技术实践活动&#xff0c;通过技术分享直播、动手实验项目、优秀代码评选、有奖征文活动等&#xff0c;让广大开发者沉浸式体验腾讯云开发者工具 Cloud Studio 的同时&#xff0c;实…

《数据结构、算法与应用C++语言描述》-栈的应用-开关盒布线问题

开关盒布线问题 问题描述 在开关盒布线问题中&#xff0c;给定一个矩形布线区域&#xff0c;其外围有若干管脚。两个管脚之间通过布设一条金属线路来连接。这条金属线路称为电线&#xff0c;它被限制在矩形区域内。两条电线交叉会发生电流短路。因此&#xff0c;电线不许交叉…

Python异步框架大战:FastAPI、Sanic、Tornado VS Go 的 Gin

一、前言 异步编程在构建高性能 Web 应用中起着关键作用&#xff0c;而 FastAPI、Sanic、Tornado 都声称具有卓越的性能。本文将通过性能压测对这些框架与Go的Gin框架进行全面对比&#xff0c;揭示它们之间的差异。 原文&#xff1a;Python异步框架大战&#xff1a;FastAPI、Sa…

【智能家居项目】裸机版本——项目介绍 | 输入子系统(按键) | 单元测试

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《智能家居项目》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 目录 &#x1f3c0;项目简介&#x1f3c0;输入子系统(按键)⚽应用层⚽设备层⚽ 内核层抽象层⚽…

每日一练-Q1-大数加法-20231001

目录 1.题目描述 2.输入描述 3.示例提示 4.问题分析 5.通过代码 1.题目描述 大数一直是一个c语言的一个难题。 现在我们需要你手动模拟出大数加法过程。 请你给出两个大整数加法结果。 2.输入描述 第一行输入整数n&#xff0c;第二行输入整数m。 (1<number<1e100)…

在nodejs中如何防止ssrf攻击

在nodejs中如何防止ssrf攻击 什么是ssrf攻击 ssrf&#xff08;server-side request forgery&#xff09;是服务器端请求伪造&#xff0c;指攻击者能够从易受攻击的Web应用程序发送精心设计的请求的对其他网站进行攻击。(利用一个可发起网络请求的服务当作跳板来攻击其他服务)…