数据结构中树的一些基本概念

前言:带你认识二叉树从基本概念开始,步步深入。

目录

树的概念和其中比较重要的基本概念

对概念的深度解析:

树的结构应该如何实现呢?

树的分类:

完全二叉树与满二叉树:


树的概念和其中比较重要的基本概念

资源来源于:树(数据结构名词)_百度百科 (baidu.com)

定义:

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

空树:空集合也是树,称为空树。空树中没有节点

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;

节点的度:一个节点含有的子节点的个数称为该节点的度;

叶节点或终端节点度为0的节点称为叶节点;

非终端节点或分支节点:度不为0的节点;

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

兄弟节点:具有相同父节点的节点互称为兄弟节点;

树的度:一棵树中,最大的节点的度称为树的度;

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度树中节点的最大层次

堂兄弟节点:双亲在同一层的节点互为堂兄弟;

节点的祖先:从根到该节点所经分支上的所有节点;

子孙:以某节点为根的子树中任一节点都称为该节点的子孙;

森林:由(m>=0)棵互不相交的树的集合称为森林。


对概念的深度解析:

1,任何一棵树都可以看成 根+N棵子树

图解:

2,树的高度或深度

树的层次的两种定义方式,根的那一层为0或为1

综上,更建议,只是建议用第一种定义方式 

3.树与非树

树:子树是不想交的

非树:子树是相交的

比如,


树的结构应该如何实现呢?

左孩子右兄弟:

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


树的分类:

二叉树:每个节点最多含有两个子树的树称为二叉树;

满二叉树:叶节点除外的所有节点均含有两个子树的树被称为满二叉树;

完全二叉树:除最后一层外,所有层都是满节点,且最后一层缺右边连续节点的二叉树称为完全二叉树;

满二叉树的一些结论:

n:节点的个数

h:树的高度

节点的个数:n = 2^h-1 

树的高度:  h = log2(n+1)

推理: 从第1层的节点个数开始一直加到第n层

2^0+2^1+……+2^(h-1) = 2^h-1

完全二叉树与满二叉树:

满二叉树和完全二叉树适合用数组存储:

因为即使用数组存储也可以通过数组的下标区分出不同元素间的父子关系。

如下图:有以下三个关系可以确定父子关系

leftchild = 2 * parent+1;(左孩子的下标等于父节点下标乘2加1)

rightchild = 2* parent +2;(右孩子的下标等于父节点下标乘2加2)

parent = (child-1)/2;(父亲节点的下标等于任意孩子节点的下标减1除2)

注意:下一篇博客会介绍堆,堆的逻辑结构就是 满二叉树和完全二叉树,通过堆还能实现堆排序。

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

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

相关文章

嵌入式进阶——数码管

🎬 秋野酱:《个人主页》 🔥 个人专栏:《Java专栏》《Python专栏》 ⛺️心若有所向往,何惧道阻且长 文章目录 数码管结构移位寄存器原理图移位寄存器数据流程移位寄存器控制流程移位寄存器串联实现数码管显示 数码管结构 共阴与共阳 共阳数码…

Java SE基础知识(11)

知识梳理: 记不住就看API帮助文档中的pattern类 开发过程中,正则表达式一般不自己写,安装插件any-rule 选择自己想要的正则表达式格式,稍作修改即可

科学提效|AI融入零售业,未来零售的创新之旅

零售业正经历着由人工智能(AI)引领的转型浪潮。AI在零售和消费品(CPG)行业的应用前景广阔,它正以多种创新方式重塑行业的运作模式。且随着技术的不断进步,AI在零售业的应用将变得更加广泛和深入。AI不仅能够…

解锁Facebook的神秘密码:探索社交媒体的奥秘

在当今数字时代,社交媒体已经渗透到我们生活的方方面面。Facebook,作为这个领域中最为瞩目的平台之一,不仅连接着全球数十亿用户,还承载着庞大的信息流和交流网络。然而,Facebook的背后是一个充满着技术和隐私的世界&a…

汇凯金业:纸黄金和实物黄金的价格有什么区别

纸黄金和实物黄金的价格主要受到全球黄金市场行情的影响,二者的基础价格并无太大差异,但在具体交易时,可能会存在一些价格上的区别,这些差异主要来自以下几个方面: 交易费用与管理费:纸黄金交易通常需要支…

Jenkins配置(插件/角色/凭证)

目录 传送门前言一、Jenkins插件管理1、更换为国内下载源2、中文汉化插件下载(不推荐)3、低版本Jenkins爆红插件安装4、低版本Jenkins插件持续报错解决办法 二、Jenkins用户角色三、Jenkins凭证管理(svn/git)1、Username with pas…

k8s集群安装后CoreDNS 启动报错plugin/forward: no nameservers found

安装k8s过程中遇到的问题: 基本信息 系统版本:ubuntu 22.04 故障现象: coredns 报错:plugin/forward: no nameservers found 故障排查: #检查coredns的配置,发现有一条转发到/etc/resolv.conf的配置…

重生奇迹mu增加敏捷的装备

穿龙炎。 1、游戏破坏方面。可以降低"敏捷"的武器,如果你是低敏捷穿龙炎,我推荐你拿它,穿龙炎配的,同时,它的攻击,我感觉是最稳定的。 2、好看方面。通常大家都穿它都是因为好看,但是很多高手也穿他,为什么?因为穿它好配点,高敏捷你可以穿,低敏捷你也可以穿它,视武…

会声会影破解版百度云(附安装教程) 会声会影下载免费中文版 会声会影2024激活码,注册机

会声会影是一款功能强大的视频与电影编辑软件,它拥有出色的色彩校正和视频氛围调整工具。这款软件对颜色、平度HSL调谐、色调曲线以及波形范围等细微变化有着敏锐的感知,能够轻松实现颜色的精确移动和校正。此外,会声会影还提供了丰富的功能&…

【量算分析工具-概述】GeoServer改造Springboot番外系列三

背景概述 GIS公司做软件产品,往往绕不开的是量算分析工具的开发和使用。例如做的比较好的火星科技的mars3d产品,如下图,但是往往这些工具都是利用Cesium框架进行前端计算的实现的,网上关于这些量算工具算法原理的文章少之又少&…

遥感信息SCI期刊,中科院1区,IF=7+,审稿速度非常快!

一、期刊名称 International Journal of Applied Earth Observation and Geoinformation 二、期刊简介概况 期刊类型:SCI 学科领域:遥感 影响因子:7.5 中科院分区:1区 三、期刊征稿范围 《国际应用地球观测和地理信息杂志》…

【深度学习】最强算法之:人工神经网络(ANN)

人工神经网络ANN 1、引言2、人工神经网络(ANN)2.1 定义2.1.1 定义2.1.2 应用场景 2.2 核心原理2.3 实现方式2.4 算法公式2.5 代码示例 3、总结 1、引言 小屌丝:鱼哥,看新闻没? 小鱼:新闻天天看,啥事大惊小怪的。 小屌…

【力扣刷题笔记第三期】Python 数据结构与算法

先从简单的题型开始刷起,一起加油啊!! 点个关注和收藏呗,一起刷题鸭!! 第一批题目 1.设备编号 给定一个设备编号区间[start, end],包含4或18的编号都不能使用,如:418、…

了解Hive 工作原理:Hive 是如何工作的?

一、概念 1、Hive Apache Hive 是一个分布式的容错数据仓库系统,可实现大规模分析和便于使用 SQL 读取、写入和管理驻留在分布式存储中的PB级数据。 Hive是建立在Hadoop之上的数据仓库框架,它提供了一种类SQL的查询语言—HiveQL,使得熟悉S…

.NET调用阿里云人脸识别1:1简易流程保姆级教学

需要注意的是,以下内容仅限基础调用 人脸比对1:1 功能说明 该功能是两张照片对比,比对两张照片是不是同一个人,至于应用到什么场景,可以参考阿里云的官方文档,我这边以大学生项目来说的话,比如员工打卡&a…

strstr的使⽤和模拟实现

strstr(function) Returnsa pointer to the irst occurrence of str2 in str1, or a null pointer if str2 is not part of str1. (函数返回字符串str2在字符串str1中第⼀次出现的位置)。 The matchingprocess doesnot include t…

如何通过虚拟人动画制作打响文旅信息资源?

随着科技的发展,虚拟人动画制作成为文旅产业数字化转型的重要手段。虚拟人动画制作可以将文化资源转化为生动的动画形式,为文旅资源的宣传和推广注入新的活力。如阿布扎比文旅部推出的数字虚拟形象“哈利法”,通过虚拟人动画制作形式&#xf…

漂流瓶挂机项目,聊天脚本赚钱新玩法,号称单机30-50+ (教程+软件)

一、项目简介: 漂流瓶挂机项目主要是通过使用探遇漂流瓶、音麦漂流瓶等聊天软件,为用户提供一个聊天赚钱的平台。男性用户需要充值后才能发送消息,而女性用户则可以通过接收消息赚取分红。男性用户发送给女性用户的消息费用大约在.1-.2元之间…

大数据开发面试题【Spark篇】

115、Spark的任务执行流程 driver和executor,结构式一主多从模式, driver:spark的驱动节点,用于执行spark任务中的main方法,负责实际代码的执行工作;主要负责:将代码逻辑转换为任务、在executo…

618值得买的东西有哪些?买什么最划算?超全品类大清单总结

平日里让许多人心动不已的收藏加购好物,是否常常因为价格昂贵而让人望而却步?然而,618活动期间的到来,恰恰为我们提供了一个难得的购物盛宴!相信在第一波活动中,许多消费者已经跃跃欲试,开始享受…