数据结构(五)——树的基本概念

五、树

5.1 树的基本概念

5.1.1 树的定义

树是n(n>=0)个结点的有限集合结点数为0的树称为空树

非空树的特性

  • 有且仅有一个根节点
  • 没有后继的结点称为“叶子结点”(或终端结点)
  • 有后继的结点称为“分支结点”(或非终端结点)
  • 除了根节点外,任何一个结点都有且仅有一个前驱
  • 每个结点可以有0个或多个后继。

5.1.2 树的基本术语

树的属性

  • 结点的层次(深度)——从上往下数 (默认从1开始)
  • 结点的高度——从下往上数
  • 树的高度(深度)——总共多少层
  • 结点的度——有几个孩子(分支)★
  • 树的度——各结点的度的最大值   ★

有序树——逻辑上看,树中结点的各子树从左至右是有次序的,不能互换
无序树——逻辑上看,树中结点的各子树从左至右是无次序的,可以互换

森林。森林是m(m≥0)棵互不相交的树的集合。m为0时是“空森林”

5.1.3 树的常考性质 

常见考点1:结点数=总度数+1
结点的度—结点有几个孩子(分支)

常见考点2:度为m的树、m叉树 的区别

        树的度——各结点的度的最大值                      m叉树——每个结点最多只能有m个孩子的树

度为m的树m叉树
任意结点的度 ≤ m(最多m个孩子)任意结点的度 ≤ m(最多m个孩子)
至少有一个结点度 = m(有m个孩子)允许所有结点的度都 < m
一定是非空树,至少有m+1个结点可以是空树

常见考点3:度为m的树第 i 层至多有 m^{i-1} 个结点(i≥1)
                    m叉树第 i 层至多有 m^{i-1}  个结点(i≥1) 

常见考点4:高度为h的m叉树至多有 \frac{m^h-1 }{m-1}个结点。
等比数列求和公式:a+aq+aq^{2}+...+aq^{n-1}=\frac{a(1-q^{n}) }{1-q}

常见考点5:高度为h的m叉树至少有 h 个结点。
                    高度为h、度为m的树至少有 h+m-1 个结点

常见考点6:具有n个结点的m叉树的最小高度为[log_{m}(n(m - 1) + 1)]
高度最小的情况——所有结点都有m个孩子

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

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

相关文章

Java项目基于SpringBoot和Vue的时装购物系统的设计与实现

今天要和大家聊的是一款基于SpringBoot和Vue的时装购物系统。 💕💕作者:李同学 💕💕个人简介:混迹在java圈十年有余,擅长Java、微信小程序、Python、Android等,大家有这一块的问题可…

OPPO 后端二面,凉凉。。。

美众议院通过 TikTok 法案 之前我们讲了 老美要求字节跳动在 165 天内剥离短视频应用 TikTok,当时的最新进度是 TikTok 给 1.7 亿美国用户发弹窗,发动用户群众给国会打电话进行抗议。 但显然这点力度的抗议并不会造成什么实质影响。 昨晚,美国…

SpringBoot与SpringCloud的版本对应详细版

在实际开发过程中,我们需要详细到一一对应的版本关系:Spring 官方对应版本地址: (https://start.spring.io/actuator/info),建议用firefox浏览器打开,你会看见格式化好了json信息: 手动记录一些经本人实际…

【译】矢量数据库 101 - 什么是矢量数据库?

原文地址:Vector Database 101 - What is a Vector Database? 1. 简介 大家好——欢迎回到 Milvus 教程。在上一教程中,我们快速浏览了每天产生的日益增长的数据量。然后,我们介绍了如何将这些数据分成结构化/半结构化数据和非结构化数据&…

使用WordPress在US Domain Center上建立招聘网站的详细教程

第一部分:介绍招聘网站 招聘网站是指用于发布招聘信息、吸引求职者、进行简历筛选和管理招聘流程的网站。在WordPress中,您可以轻松地创建一个功能齐全的招聘网站,以便企业能够方便地管理招聘流程,并为求职者提供信息和应聘渠道。…

论文浅尝 | GPT-RE:基于大语言模型针对关系抽取的上下文学习

笔记整理:张廉臣,东南大学硕士,研究方向为自然语言处理、信息抽取 链接:https://arxiv.org/pdf/2305.02105.pdf 1、动机 在很多自然语言处理任务中,上下文学习的性能已经媲美甚至超过了全资源微调的方法。但是&#xf…

力扣Lc18--- 168. Excel表列名称(java版)-2024年3月19日

1.题目描述 2.知识点 注1:StringBuilder 对象的 insert() 方法用于在字符串的指定位置插入字符或字符序列。这里的第一个参数是插入位置的索引,而第二个参数是要插入的字符或字符序列。 public class InsertExample {public static void main(String[…

彻底学会系列:一、机器学习之梯度下降(2)

1 梯度具体是怎么下降的? ∂ J ( θ ) ∂ θ \frac{\partial J (\theta )}{\partial \theta} ∂θ∂J(θ)​(损失函数:用来衡量模型预测值与真实值之间差异的函数) 对损失函数求导,与学习率相乘,按梯度反方…

搭建基于 Snowflake 的 CI/CD 最佳实践!

Snowflake 提供了可扩展的计算和存储资源,和基于 SQL 的界面 Snowsight,方便用户进行数据操作和分析。然而,如果用户想将自己的 CI/CD 流程与 Snowflake 集成时,会发现一些不便之处(尤其相比其 SnowSight 优秀的查询能…

三段提交的理解

三阶段提交是在二阶段提交上的改进版本,3PC 最关键要解决的就是协调者和参与者同时挂掉的问题,所以3PC把2PC的准备阶段再次一分为二,这样三阶段提交。 处理流程如下 : 阶段一 协调者向所有参与者发出包含事务内容的 canCommit …

无人机助力违法毒品种植智能监测预警,基于轻量级YOLOv5n开发构建无人机航拍场景下的农村田园场景下非法种植罂粟花检测预警识别系统

打击毒品人人有责,毒品带来的危害是人尽皆知的,我们不仅自身要严厉拒绝接触任何形式的毒品,更要言传身教告诫他人不要与任何形式的任何渠道的毒品有关联,但是在实际生活中,在一些偏远的乡村、田园、山丘、村落等地方&a…

Markdown 最全语法指南 —— 看这一篇就够了

目录 一. 前言 二. Markdown 标题语法 三. Markdown 段落语法 四. Markdown 换行语法 五. Markdown 强调语法 六. Markdown 引用语法 七. Markdown 列表语法 八. Markdown 代码语法 九. Markdown 分隔线语法 十. Markdown 链接语法 十一. Markdown 图片语法 十二. Markdown 转义…

【技术栈】Redis 企业级解决方案

​ SueWakeup 个人主页:SueWakeup ​​​​​​​ 系列专栏:学习技术栈 ​​​​​​​ ​​​​​​​ ​​​​​​​ ​​​​​​​ ​​​​​​​ ​​​​​​​ ​​​​​​​ 个性签名&…

php 对接Pangle海外广告平台收益接口Reporting API

今天对接的是Pangle广告reporting api接口,拉取广告收益回来自己做统计。记录分享给大家 首先是文档地址,进入到Pangle后台就能看到文档地址以及参数: 文档地址:https://www.pangleglobal.com/zh/integration/reporting-api-v2 在这里插入图片…

[SWPU2019]Web4

[SWPU2019]Web4 PDO注入(堆叠注入) 首先发现一个登录框,但是不能注册进行抓包,发现json数据格式,猜测可能是sql注入或者xxe漏洞 输入 ’ 报错,但是输入"或者‘ “ 不报错->猜测为堆叠注入[[mysql…

6.shell中的计算

目录 概述实践shell结果 结束 概述 shell中计算 实践 shell #!/bin/bash # 计算 expr、let 都只能用于整形计算a3 bexpr $a 3 echo "b$b" cexpr $b / 3 echo "c$c"# let 命令 表达式 let "a10" echo "a10$a" let "a/10&quo…

拓展商城系统的未来:微服务维度的创新之路

随着电子商务的快速发展,传统的单体式商城系统在应对日益复杂的业务需求和用户体验方面逐渐显露出局限性。而基于微服务架构的商城系统,通过多维度的拆分和组合,正在为商城行业带来全新的创新和发展机遇。本文将深入探讨微服务维度下的商城系…

查找众数及中位数 - 华为OD统一考试(C卷)

OD统一考试(C卷) 分值: 100分 题解: Java / Python / C 题目描述 众数是指一组数据中出现次数量多的那个数,众数可以是多个。 中位数只是指把一组数据从小到大排列,最中间的那个数,如果这组数…

罗德与施瓦茨 FSU8频谱分析仪

181/2461/8938产品概述: Rohde & Schwarz FSU8是一款高性能频谱分析仪,在相位噪声、动态范围和测量精度方面具有出色的性能,可应对航空航天和国防领域的任何射频分析挑战,也可用于高达8 GHz的一般微波应用。 为了处理产品开…

端口如何映射到外网?

在现代信息化社会中,远程访问已经成为人们工作和生活中不可或缺的一部分。复杂的网络环境和网络限制可能会给远程连接带来不便。在这种情况下,端口映射到外网的技术应运而生。本文将介绍端口映射到外网的概念、应用场景以及一种优秀的解决方案——【天联…