【二叉树前沿篇】树

【二叉树前沿篇】树

  • 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个节点,然后在通过兄弟节点找到其他兄弟节点。
其他节点不断重复上述过程,最后找到所以数据。


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

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python项目实战:基于napari的3D可视化(点云+slice)

文章目录 一、napari 简介二、napari 安装与更新三、napari【巨巨巨大的一个BUG】四、napari 使用指南4.1、菜单栏&#xff08;File View Plugins Window Help&#xff09;4.2、Window&#xff1a;layer list&#xff08;参数详解&#xff09;4.3、Window&#xff1a;layer…

grafana-zabbix基础操作篇------导入数据源

文章目录 一、grafana的安装1.1、下载地址1.2、下载后导入所安装机器1.3、yum安装解决依赖1.4、启动grafana1.5、查看端口是否启用&#xff08;端口默认3000&#xff09;1.6、浏览器访问 二、添加zabbix数据源2.1、导入数据源 **下一篇 我们讲讲构建仪表板的操作** 今天&#x…

SAP ABAP SQL查询语句-内连接与左连接使用

SQL查询语句-内连接与左连接使用 程序: data:begin of itab OCCURS 0,material type /bic/oizmaterial,batch type /bi0/oibatch,brd type /bic/oizzbrd,cpquabu type /bi0/oicpquabu,end of itab. *&**例一: clear: itab[]. select * into corresponding fields…

OpenLayers实战,OpenLayers判断点位是否与多边形有交集,判断车辆是否在电子围栏内

专栏目录: OpenLayers实战进阶专栏目录 前言 OpenLayers实战,OpenLayers判断点位是否与多边形有交集,可以用于判断车辆是否在电子围栏内,船舶是否在锚泊位中等常用案例。 在实际GIS地图业务开发中,一般是不会在前端实现是否在电子围栏这种计算的。 如果有人让你在前端实…

【数据结构】 单链表面试题讲解

文章目录 引言反转单链表题目描述示例&#xff1a;题解思路代码实现&#xff1a; 移除链表元素题目描述&#xff1a;示例思路解析&#xff1a; 链表的中间结点题目描述&#xff1a;示例&#xff1a;思路解析代码实现如下&#xff1a; 链表中倒数第k个结点题目描述示例思路解析&…

SpringBoot统⼀功能处理

前言&#x1f36d; ❤️❤️❤️SSM专栏更新中&#xff0c;各位大佬觉得写得不错&#xff0c;支持一下&#xff0c;感谢了&#xff01;❤️❤️❤️ Spring Spring MVC MyBatis_冷兮雪的博客-CSDN博客 本章是讲Spring Boot 统⼀功能处理模块&#xff0c;也是 AOP 的实战环节&…

Redis 扩展资料

Redis 扩展资料 1.缓存简介2.缓存分类3.常⻅缓存使⽤4.Redis 数据类型和使⽤5.持久化6.常⻅⾯试题7.Redis 集群&#xff08;选学&#xff09; 1.缓存简介 2.缓存分类 3.常⻅缓存使⽤ 4.Redis 数据类型和使⽤ 5.持久化 Redis 和 Memcached 有什么区别&#xff1f; 6.常⻅⾯试…

Java日志框架-JUL

JUL全称Java util logging 入门案例 先来看着入门案例&#xff0c;直接创建logger对象&#xff0c;然后传入日志级别和打印的信息&#xff0c;就能在控制台输出信息。 可以看出只输出了部分的信息&#xff0c;其实默认的日志控制器是有一个默认的日志级别的&#xff0c;默认就…

Linux命令200例:nc非常有用的网络工具(常用)

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;全栈领域新星创作者✌。CSDN专家博主&#xff0c;阿里云社区专家博主&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &…

PHP-MD5注入

0x00 前言 有些零散的知识未曾关注过&#xff0c;偶然捡起反而更加欢喜。 0x01 md5 注入绕过 md5函数有两个参数&#xff0c;第一个参数是要进行md5的值&#xff0c;第二个值默认为false&#xff0c;如果为true则返回16位原始二进制格式的字符串。意思就是会将md5后的结果当…

MVCC 是否彻底解决了事物的隔离性 ?

目录 1. 什么是 MVCC 2. MVCC 是否彻底解决了事物的隔离性 3. MySQL 中如何实现共享锁和排他锁 4. MySQL 中如何实现悲观锁和乐观锁 1. 什么是 MVCC MVCC&#xff08;Multi-Version Concurrency Control&#xff0c;多版本并发控制&#xff09;是一种多版本并发控制机制&…

vue项目使用qrcodejs2遇到Cannot read property ‘appendChild‘ of null

这个问题是节点还没创建渲染完就读取节点&#xff0c;这个时候应该先让节点渲染完成在生成&#xff0c;解决方法有以下两种 1、使用$nextTick&#xff08;&#xff09;方法进行&#xff0c;这个方法是用来在节点创建渲染完成后进行的操作 that.$nextTick(() > {let qrcode …

Java基础知识小结(内部类、BigInteger、枚举、接口、重写重载和序列化)

一、Java内部类 1、内部类 在Java中&#xff0c;也可以嵌套类&#xff08;类中的类&#xff09;。嵌套类的目的是将属于同一类的类分组&#xff0c;这使代码更具可读性和可维护性。 要访问内部类&#xff0c;请创建外部类的对象&#xff0c;然后创建内部类的对象&#xff1a;…

SpringBoot中优雅的实现隐私数据脱敏(提供Gitee源码)

前言&#xff1a;在实际项目开发中&#xff0c;可能会对一些用户的隐私信息进行脱敏操作&#xff0c;传统的方式很多都是用replace方法进行手动替换&#xff0c;这样会由很多冗余的代码并且后续也不好维护&#xff0c;本期就讲解一下如何在SpringBoot中优雅的通过序列化的方式去…

【框架类】—MVVM框架

一、MVVM框架有哪些 Vue.jsReact.jsAngular.js 二、对MVVM的认识 1. MVC是什么 全称 Model View Controller, 它采用模型(Model)-视图(View)-控制器(controller)的方法把业务逻辑、数据与界面显示分离 2. MVVM的定义 MVVM是一种软件架构模式&#xff0c;它代表了模型 --视…

深入理解JVM——垃圾回收与内存分配机制详细讲解

所谓垃圾回收&#xff0c;也就是要回收已经“死了”的对象。 那我们如何判断哪些对象“存活”&#xff0c;哪些已经“死去”呢&#xff1f; 一、判断对象已死 1、引用计数算法 给对象中添加一个引用计数器&#xff0c;每当有一个地方引用它时&#xff0c;计数器就加一&…

探索无限创造力的星辰大道,画出想象的浩瀚宇宙!-turtle

介绍 视频教程地址在此&#xff1a;https://www.bilibili.com/video/BV1Pm4y1H7Tb/ 大家好&#xff0c;欢迎来到本视频&#xff01;今天&#xff0c;我们将一同探索Python编程世界中的一个有趣而创意的库——Turtle库。无需专业绘画技能&#xff0c;你就可以轻松地用代码绘制…

人工智能在网络安全中的作用:当前的局限性和未来的可能性

人工智能 (AI) 激发了网络安全行业的想象力&#xff0c;有可能彻底改变安全和 IT 团队处理网络危机、漏洞和勒索软件攻击的方式。 然而&#xff0c;对人工智能的能力和局限性的现实理解至关重要&#xff0c;并且存在许多挑战阻碍人工智能对网络安全产生直接的变革性影响。 在…

概述、搭建Redis服务器、部署LNP+Redis、创建Redis集群、连接集群、集群工作原理

Top NSD DBA DAY09 案例1&#xff1a;搭建redis服务器案例2&#xff1a;常用命令限案例3&#xff1a;部署LNPRedis案例4&#xff1a;创建redis集群 1 案例1&#xff1a;搭建redis服务器 1.1 具体要求如下 在主机redis64运行redis服务修改服务运行参数 ip 地址192.168.88.6…

在 ubuntu 18.04 上使用源码升级 OpenSSH_7.6p1到 OpenSSH_9.3p1

1、检查系统已安装的当前 SSH 版本 使用命令 ssh -V 查看当前 ssh 版本&#xff0c;输出如下&#xff1a; OpenSSH_7.6p1 Ubuntu-4ubuntu0.7, OpenSSL 1.0.2n 7 Dec 20172、安装依赖&#xff0c;依次执行以下命令 sudo apt update sudo apt install build-essential zlib1g…