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

【二叉树前沿篇】树

【二叉树前沿篇】树

  • 1 树的概念
  • 2. 树的相关概念
  • 3. 树的表示
  • 4. 树在实际中的运用(表示文件系统的目录树结构)


在这里插入图片描述


1 树的概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的

在这里插入图片描述

  • 树有一个特殊的结点,称为根结点根节点没有前驱结点
  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
     
    Tips: 树形结构中,子树之间不能有交集,否则就不是树形结构。
     
    在这里插入图片描述

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)棵互不相交的树的集合称为森林;


3. 树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系
实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法

代码实现:

typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};

在这里插入图片描述


4. 树在实际中的运用(表示文件系统的目录树结构)

在这里插入图片描述

上述中,首先找到第2行的第一个孩子bin,bin在通过兄弟节点找到第二行其他兄弟节点。
又因为第2行第一个节点的孩子指针为空,所以结束不在向下访问。
接下来就是第2行第2个节点通过孩子指针找到第3行第1个节点,然后在通过兄弟节点找到其他兄弟节点。
其他节点不断重复上述过程,最后找到所以数据。


在这里插入图片描述
在这里插入图片描述

相关文章:

【二叉树前沿篇】树

【二叉树前沿篇】树 1 树的概念2. 树的相关概念3. 树的表示4. 树在实际中的运用&#xff08;表示文件系统的目录树结构&#xff09; 1 树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是…...

python3 0基础学习----数据结构(基础+练习)

python 0基础学习笔记之数据结构 &#x1f4da; 几种常见数据结构列表 &#xff08;List&#xff09;1. 定义2. 实例&#xff1a;3. 列表中常用方法.append(要添加内容) 向列表末尾添加数据.extend(列表) 将可迭代对象逐个添加到列表中.insert(索引&#xff0c;插入内容) 向指定…...

计算机科学中的“旅行商问题”

题目&#xff1a;旅行商问题&#xff08;Traveling Salesman Problem&#xff09; 当初为何收藏&#xff1a;我收藏了这个题目是因为它是一个经典而富有挑战性的组合优化问题&#xff0c;涉及到计算机科学、算法设计和实际应用领域。我认为这个问题可以展示出算法设计的重要性…...

QT:自定义控件(Connect使用,子控件连接)

自定义控件封装&#xff1a; 1.添加新文件&#xff08;设计师界面类&#xff09;&#xff0c;创建子页面 &#xff0c;放自己想要的控件 2.在主页面中使用子控件 :新建一个widget-![在这里插入图片描述](https://img-blog.csdnimg.cn/95ed8015343e4c56a3914853950eff4c.png#pi…...

目录——车载网络安全

本文主要汇总车载网络安全专栏文章,以方便各位读者阅读。 ISO21434 概述(一) ISO21434 组织网络安全管理(二) ISO21434 项目网络安全管理(三) ISO21434 分布式网络安全(四) SO21434 持续进行的网络安全(五) ISO21434 概念阶段网络安全(六)...

Visual Studio 如何放大代码字体的大小

1.打开Visual Studio&#xff0c;新建一个程序&#xff0c;一段代码&#xff0c;为接下去的操作做好准备。单击菜单栏的【工具】选项。 2.在跳出来菜单中找到【选项】&#xff08;一般在最后一项&#xff09;&#xff0c;然后单击。跳出新的窗口。 3.跳出新的窗口后&#xff…...

Verilog同步FIFO设计

同步FIFO(synchronous)的写时钟和读时钟为同一个时钟&#xff0c;FIFO内部所有逻辑都是同步逻辑&#xff0c;常常用于交互数据缓冲。 异步FIFO&#xff1a;数据写入FIFO的时钟和数据读出FIFO的时钟是异步的(asynchronous) 典型同步FIFO有三部分组成: &#xff08;1&#xff0…...

Php“牵手”lazada商品详情页数据采集方法,lazadaAPI接口申请指南

lazada详情接口 API 是开放平台提供的一种 API 接口&#xff0c;它可以帮助开发者获取商品的详细信息&#xff0c;包括商品的标题、描述、图片等信息。在电商平台的开发中&#xff0c;详情接口API是非常常用的 API&#xff0c;因此本文将详细介绍详情接口 API 的使用。 一、la…...

Sentinel 规则持久化

文章目录 Sentinel 规则持久化一、修改order-service服务1.引入依赖2.配置nacos地址 第二步修改非常麻烦&#xff0c;可以略过&#xff0c;直接使用已经打好包的来使用二、修改sentinel-dashboard源码1. 解压2. 修改nacos依赖3. 添加nacos支持4. 修改nacos地址5. 配置nacos数据…...

元宇宙时代超高清视音频技术白皮书关于流媒体协议和媒体传输解读

流媒体协议 元宇宙业务场景对流媒体传输的实时性和互动性提出了更高的要求&#xff0c;这就需要在传统的 RTMP、SRT、 HLS 等基础上增加实时互动的支持。实时互动&#xff0c;指在远程条件下沟通、协作&#xff0c;可随时随地接入、实时地传递虚实融合的多维信息&#xff0c;身…...

【计算机设计大赛】国赛一等奖项目分享——基于多端融合的化工安全生产监管可视化系统

文章目录 一、计算机设计大赛国赛一等奖二、项目背景三、项目简介四、系统架构五、系统功能结构六、项目特色&#xff08;1&#xff09;多端融合&#xff08;2&#xff09;数据可视化&#xff08;3&#xff09;计算机视觉&#xff08;目标检测&#xff09; 七、系统界面设计&am…...

深入理解【二叉树】

&#x1f4d9;作者简介&#xff1a; 清水加冰&#xff0c;目前大二在读&#xff0c;正在学习C/C、Python、操作系统、数据库等。 &#x1f4d8;相关专栏&#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 &#x1f44d…...

RequestRespons

文章目录 Request&Respons1 Request和Response的概述2 Request对象2.1 Request继承体系2.2 Request获取请求数据2.2.1 获取请求行数据2.2.2 获取请求头数据2.2.3 获取请求体数据2.2.4 获取请求参数的通用方式 2.3 IDEA快速创建Servlet2.4 请求参数中文乱码问题2.4.1 POST请…...

UniApp 使用命令创建页面的详细指南

系列文章目录 文章目录 系列文章目录前言一、安装Uni-CLI二、创建页面三、页面创建命令四、页面结构五、页面使用总结 前言 UniApp是一款跨平台的前端框架&#xff0c;可以用于开发同时运行在多个平台&#xff08;如微信小程序、H5、App等&#xff09;的应用程序。本文将详细介…...

Opencv 图像的读取与写入

目录 导入cv2 读取图像数据 创建一个窗口 waitKey方法 关闭所有窗口 完整示例 保存图片 示例 导入cv2 # 导入opencv包 import cv2 读取图像数据 cv2.imread(path, flag) 参数说明&#xff1a; path&#xff1a;要读取的图像文件的路径。 flag&#xff08;可选&#…...

关于rinex3.x广播星历文件中时间系统的说明

文章目录 rinex广播星历文件介绍广播星历介绍rinex3.x多系统广播星历文件中的时间系统写在最后 rinex广播星历文件介绍 rinex星历文件是一种ascii字符文件&#xff0c;可以存放广播星历和精密星历&#xff0c;被广泛用于GNSS数据处理。 本文主要介绍广播星历文件。 对于rinex…...

Ansible 实战

Ansible 实战 1. httpd 角色 目录 rootubuntu1904:~#tree -f httpd/ httpd ├── httpd/default │ └── httpd/default/main.yml ├── httpd/files │ ├── httpd/files/httpd.conf │ └── httpd/files/index.html ├── httpd/handlers │ └── http…...

三、单元测试

三、单元测试 好的单元测试必须遵守 AIR 原则 A&#xff1a;Automatic&#xff08;自动化&#xff09;I&#xff1a;Independent&#xff08;独立性&#xff09;R&#xff1a;Repeatable&#xff08;可重复&#xff09; 单元测试应该是全自动执行的&#xff0c;并且非交互式的…...

“Spring管理JavaBean的过程及Bean的生命周期“

目录 引言1.弹簧容器2. Bean的生命周期2.1 配置javaBean2.2. 解析Bean的定义2.3 检查是否需要添加自己的功能2.4 初始化2.5 实现Aware接口2.6 扩展2.7. 销毁 3. 单例模式和原型模式3.1. 单例模式3.2. 原型模式 4. 总结 引言 Spring框架是一个非常流行的Java应用程序框架&#…...

@mouseover不起作用,并没有触发

我的错误代码如下&#xff1a; <el-rowv-for"version in item.version_list":key"version.id":class"{ blue-background: versionItem.id version.id }"mouseover.native"version.isHovered true"mouseleave.native"version…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...