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

数据结构-----树的易错点

1.树的度和m叉树

•度为m的树(度表示该结点有多少个孩子(分支))

任意结点的度<=m(最多m个孩子)

至少又一个结点度=m(有m个孩子)

一定是非空树,至少有m+1个结点

•m叉树

任意结点的度<=m(最多有m个孩子)

允许所有结点的度都<m

可以是空树

2.m叉树第i层至多有m^{i-1}个结点或度为m的树第i层至多有m^{i-1}个结点

二叉树第i层至多有2^{i-1}个结点

3.高度为h的m叉树至多\frac{m^{h}-1}{m-1}个结点

高度为h的二叉树至多有2^{h}-1个结点

注: 

在这里,树的高度和深度可以看作相同的概念,因为这里侧重于树有几层,但是如果侧重于结点,那么高度和深度的概念就不同了

树的深度:(从上往下数)

  • 节点 D、E 和 F 的深度都为 2,因为从根节点 A 到节点 D ,E,F需要经过 2 条边。

树的高度:(从下往上数)

  • 节点 D、E 和 F 的高度都为 1,因为它们都到达任意叶子节点的路径长度最短,只需要经过 1 条边。

总的来说:

  • 树的深度是指从根节点到某个节点的路径长度。
  • 树的高度是指从某个节点到达任意叶子节点的最长路径长度。

4.高度为h的m叉树至少有h个结点(高度为h,度为m的树至少有h+m-1个结点)

 

5.具有n个结点的m叉树的最小高度为\log _{m}^{(n(m-1)+1)}

最小高度----每一个结点都有m个孩子

\frac{m^{h-1}-1}{m-1}< n\leq\frac{m^{h}-1}{m-1}

m^{h-1}<n(m-1)+1\leq m^{h}

h-1<\log _{m}^{(n(m-1)+1)}\leq h

h_{min}=\log _{m}^{(n(m-1)+1)}(向上取整)

6.二叉树

(1).设非空二叉树中度为0,1,和2的结点个数分别为n0,n1,n2,则n0=n2+1(叶子节点的个数要比二分支节点的个数多一个)

假设结点总数为n

①n=n0+n1+n2

②n=n1+2n2+1(树的节点数=总度数+1)

(2).满二叉树

高度为h的二叉树,有2^{h}-1个结点

1.只有最后一层有叶子结点

2.不存在度为1的结点

3.按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1,结点i的父节点为i/2(向下取整)

6/2=3,7/2(向下取整)=3,所以6,7的父节点为3

(3).完全二叉树

将叶子节点从大到小删去的,都可以称为完全二叉树,例如

右下角的图,6号结点在满二叉树中本来应该为7,所以序号变了,不是完全二叉树

得出结论

完全二叉树不一定是满二叉树,满二叉树一定是完全二叉树

①只有最后两层可以有叶子节点

②最多只有1个度为1的结点

③按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1,结点i的父节点为i/2(向下取整)

④如果一个完全二叉树有n个结点,那么i\leq \frac{n}{2}(向下取整)为分支节点,i\geq \frac{n}{2}(向下取整)为叶子节点

⑤如果某个节点只有1个结点,那么这个结点只可能是左孩子,不会是右孩子

⑥两个结论均正确

•具有n个(n>0)结点的完全二叉树的高度h(深度)为\log _{2}^{(n+1)}(向上取整)

推导过程

高为(h)的满二叉树共有2^{h}-1个结点

高为(h-1)的满二叉树共有2^{h-1}-1个结点

2^{h-1}-1<n\leqslant2^{h}-1

2^{h-1}<n+1\leq 2^{h}

h-1<\log _{2}^{(n+1)}\leqslant h

•具有n个(n>0)结点的完全二叉树的高度h(深度)为\log _{2}^{(n)}+1(向下取整)

高为h的完全二叉树至少2^{h-1}个结点

高为h的完全二叉树至少2^{h}-1个结点

2^{h-1}\leqslant n \leqslant 2^{h}-1

2^{h-1}\leqslant n < 2^{h}

h-1\leqslant \log _{2}^{n}<h

h= \log _{2}^{(n)}+1(向下取整)

⑦对于完全二叉树,可以优结点数n,推出度为0,1和2的结点个数为n0,n1和n2

完全二叉树最多只有一个度为1的结点,即

n1=0或1

n0=n2+1--->n0+n1一定为奇数

若完全二叉树有2k个结点,则必有n1=1,n0=k,n2=k-1

若完全二叉树有2k个结点,则必有n1=0,n0=k,n2=k-1

(4).二叉排序树

1.左子树上所有结点的关键字均小于根结点的关键字;

3.左子树和右子树又各是一棵二叉排序树。

(5).平衡二叉树

树上任一结点的左子树和右子树深度(高度)之差不超过1

相关文章:

数据结构-----树的易错点

1.树的度和m叉树 •度为m的树&#xff08;度表示该结点有多少个孩子&#xff08;分支&#xff09;&#xff09; 任意结点的度<m(最多m个孩子) 至少又一个结点度m(有m个孩子) 一定是非空树&#xff0c;至少有m1个结点 •m叉树 任意结点的度<m(最多有m个孩子) 允许所…...

写之前的项目关于使用git remote -v 找不到项目地址的解决方案

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、报错解析1. 报错内容2. 报错翻译3. 报错解析&#xff08;1&#xff09;使用git branch来查看git仓库有几个分支&#xff08;2&#xff09;使用git remote -v&am…...

STM32 F103C8T6学习笔记9:0.96寸单色OLED显示屏—自由取模显示—显示汉字与图片

今日学习0.96寸单色OLED显示屏的自由取模显示: 宋体汉字比较复杂&#xff0c;常用字符可以直接复制存下来&#xff0c;毕竟只有那么几十个字母字符&#xff0c;但汉字实在太多了&#xff0c;基本不会全部放在单片机里存着&#xff0c;一般用到多少个字就取几个字的模&#xff…...

直播平台源码搭建协议讲解篇:传输控制协议TCP

简介&#xff1a; 由于直播平台在当今时代发展的越来越迅速&#xff0c;使得直播平台的技术功能越来越智能&#xff0c;让用户在直播平台中能够和其他用户进行实时互动&#xff0c;让用户可以获取到全世界最新的资讯&#xff0c;让一些用户可以作为主播获得工作&#xff0c;让…...

中文编码问题:raw_input输入、文件读取、变量比较等str、unicode、utf-8转换问题

最近研究搜索引擎、知识图谱和Python爬虫比较多&#xff0c;中文乱码问题再次浮现于眼前。虽然市面上讲述中文编码问题的文章数不胜数&#xff0c;同时以前我也讲述过PHP处理数据库服务器中文乱码问题&#xff0c;但是此处还是准备简单做下笔记。方便以后查阅和大家学习。 …...

基于Jenkins自动打包并部署Tomcat环境

目录 1、配置git主机 2、配置jenkins主机 3、配置web主机 4、新建Maven项目 5、验证 Jenkins 自动打包部署结果 Jenkins 的工作原理是先将源代码从 SVN/Git 版本控制系统中拷贝一份到本地&#xff0c;然后根据设置的脚本调用Maven进行 build&#xff08;构建&#xff09;。…...

开利网络受邀参与御盛马术庄园发展专委会主题会议

近日&#xff0c;开利网络受邀参与深度合作客户御盛马术庄园组织的首届发展专委会主体会议&#xff0c;就马术庄园发展方向进行沟通&#xff0c;数字化也是重要议题之一。目前&#xff0c;御盛马术庄园已经完成数字化系统的初步搭建&#xff0c;将通过线上线下相结合的方式搭建…...

【HarmonyOS北向开发】-05 ArkTS开发语言-ArkTS开发实践

...

无类别域间路由(Classless Inter-Domain Routing, CIDR):理解IP网络和子网划分(传统的IP地址类ABCDE:分类网络)

文章目录 无类别域间路由&#xff08;CIDR&#xff09;&#xff1a;理解IP网络和子网划分引言传统的IP地址类关于“IP地址的浪费” IP地址与CIDRIP地址概述网络号与主机号CIDR记法&#xff08;网络 网络地址/子网掩码&#xff09;网络和广播地址 CIDR的优势减少路由表项缓解IP…...

合宙Air724UG LuatOS-Air LVGL API-概念

概念 在 LVGL 中&#xff0c;用户界面的基本构建块是对象。例如&#xff0c;按钮&#xff0c;标签&#xff0c;图像&#xff0c;列表&#xff0c;图表或文本区域。 属性 基本属性 所有对象类型都共享一些基本属性&#xff1a; Position (位置) Size (尺寸) Parent (父母) Cli…...

【C语言】位段,枚举和联合体详解

目录 1.位段 1.1 什么是位段 1.2 位段的内存分配 1.3 位段的跨平台问题 2.枚举 2.1 枚举类型的定义 2.2 枚举的优点 3. 联合&#xff08;共用体&#xff09; 3.1 联合类型的定义 3.2 联合的特点 3.3 联合大小的计算 1.位段 1.1 什么是位段 位段的声明和结构体是类…...

python学习-文件管理

文件管理 shutil 文件拷贝 shutil.copy(src,dst) 注&#xff1a;srcrE:\python\.vscode\文件操作 windows上运行时候&#xff0c;如果不加r&#xff0c;上述文件路径在代码运行时会报错&#xff0c;因为其会先将双引号”“去掉&#xff0c;然后系统看到了文件路径中有\nc&…...

【LeetCode 算法】Number of Ways of Cutting a Pizza 切披萨的方案数-记忆化

文章目录 Number of Ways of Cutting a Pizza 切披萨的方案数问题描述&#xff1a;分析代码递归 Tag Number of Ways of Cutting a Pizza 切披萨的方案数 问题描述&#xff1a; 给你一个 rows x cols 大小的矩形披萨和一个整数 k &#xff0c;矩形包含两种字符&#xff1a; A…...

机器视觉之光流

光流&#xff08;Optical Flow&#xff09;是计算机视觉领域的一个重要概念&#xff0c;用于描述图像中物体的运动模式。光流可以用来跟踪图像中物体的运动&#xff0c;检测运动中的物体&#xff0c;或者在机器视觉任务中估计物体的速度和位移。 光流的基本思想是根据图像像素…...

C++:list使用以及模拟实现

list使用以及模拟实现 list介绍list常用接口1.构造2.迭代器3.容量4.访问数据5.增删查改6.迭代器失效 list模拟实现1.迭代器的实现2.完整代码 list介绍 list是一个类模板&#xff0c;加<类型>实例化才是具体的类。list是可以在任意位置进行插入和删除的序列式容器。list的…...

深度学习基础知识-pytorch数据基本操作

1.深度学习基础知识 1.1 数据操作 1.1.1 数据结构 机器学习和神经网络的主要数据结构&#xff0c;例如 0维&#xff1a;叫标量&#xff0c;代表一个类别&#xff0c;如1.0 1维&#xff1a;代表一个特征向量。如 [1.0&#xff0c;2,7&#xff0c;3.4] 2维&#xff1a;就是矩…...

Springboot使用QueryDsl实现融合数据查询

SpringbootQueryDsl技术 1、添加依赖 <!--基于JPA--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-jpa</artifactId> </dependency> <!--QueryDSL支持--> <dependenc…...

解决方案 | 电子签打通消费电子行业数智化经营通路

技术迭代不断驱动产业快速增长&#xff0c;从PC电脑到手机平板、再到可穿戴设备的兴起&#xff0c;每一次设备的迭代都代表着技术为产品注入了新的发展动能。与此同时&#xff0c;消费电子设备迭代更新周期的不断缩短&#xff0c;市场增长疲缓等因素&#xff0c;也对行业的流转…...

JVM理论知识

一、JVM内存结构 java的内存模型主要分为5个部分&#xff0c;分别是&#xff1a;JVM堆、JVM栈、本地栈、方法区还有程序计数器&#xff0c;他们的用途分别是&#xff1a; JVM堆&#xff1a;新建的对象都会放在这里&#xff0c;他是JVM中所占内存最大的区域。他又分为新生区还…...

idea - 报错 Mybatis提示Tag name expected的问题< 小于号 无法识别

问题&#xff1a;Mybatis提示Tag name expected 原因&#xff1a; 当我们在mapper中编写sql语句的时候会发现使用"<“符号会提示一个Tag name expected。这是因为xml文件中不识别”<"符号和“&”符号。防止与xml本身的元素命名混淆&#xff0c;导致无法解…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...