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

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

news 2025/7/6 6:43:48

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\leqslant$ $2^{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的树（度表示该结点有多少个孩子（分支）） 任意结点的度<m(最多m个孩子) 至少又一个结点度m(有m个孩子) 一定是非空树，至少有m1个结点 •m叉树任意结点的度<m(最多有m个孩子) 允许所…...

编程日记 2023/8/23 7:46:49

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

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

编程日记 2023/8/23 7:45:47

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

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

编程日记 2023/8/23 7:44:45

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

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

编程日记 2023/8/23 7:43:44

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

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

编程日记 2023/8/23 7:42:43

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

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

编程日记 2023/8/23 7:41:41

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

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

编程日记 2023/8/23 7:40:40

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

...

编程日记 2023/8/23 7:39:40

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

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

编程日记 2023/8/23 7:38:39

合宙Air724UG LuatOS-Air LVGL API-概念

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

编程日记 2023/8/23 7:37:37

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

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

编程日记 2023/8/23 7:36:36

python学习-文件管理

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

编程日记 2023/8/23 7:35:34

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

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

编程日记 2023/8/23 7:34:32

机器视觉之光流

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

编程日记 2023/8/23 7:33:31

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

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

编程日记 2023/8/23 7:32:29

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

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

编程日记 2023/8/23 7:31:27

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

SpringbootQueryDsl技术 1、添加依赖  <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-jpa</artifactId> </dependency>  <dependenc…...

编程日记 2023/8/23 7:30:26

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

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

编程日记 2023/8/23 7:29:25

JVM理论知识

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

编程日记 2023/8/23 7:28:22

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

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

编程日记 2023/8/23 7:27:21

conda相比python好处

Conda 作为 Python 的环境和包管理工具，相比原生 Python 生态（如 pip 虚拟环境）有许多独特优势，尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处： 一、一站式环境管理&#xff1a…...

编程新知 2025/6/15 5:36:36

Lombok 的 @Data 注解失效，未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误，它们的含义、原因和解决方法都有显著区别。以下是详细对比： 1. HTTP 406 (Not Acceptable) 含义： 客户端请求的内容类型与服务器支持的内容类型不匹…...

编程新知 2025/6/29 5:59:21

深入浅出：JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出：JavaScript 中的 window.crypto.getRandomValues() 方法在现代 Web 开发中，随机数的生成看似简单，却隐藏着许多玄机。无论是生成密码、加密密钥，还是创建安全令牌，随机数的质量直接关系到系统的安全性。Jav…...

编程新知 2025/6/15 19:02:54

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个？3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制半数机制（过半机制&#xff0…...

编程新知 2025/7/4 6:03:35

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时，需结合业务场景设计数据流转链路，重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点： 一、核心对接场景与目标商品数据同步场景：将1688商品信息…...

编程新知 2025/6/23 4:26:05

相机Camera日志分析之三十一：高通Camx HAL十种流程基础分析关键字汇总（后续持续更新中）

【关注我，后续持续新增专题博文，谢谢！！！】上一篇我们讲了：有对最普通的场景进行各个日志注释讲解，但相机场景太多，日志差异也巨大。后面将展示各种场景下的日志。通过notepad++打开场景下的日志，通过下列分类关键字搜索，即可清晰的分析不同场景的相机运行流程差异…...

编程新知 2025/6/15 13:22:13

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA：通过低成本全身远程操作学习双手移动操作传统模仿学习（Imitation Learning）缺点：聚焦与桌面操作，缺乏通用任务所需的移动性和灵活性本论文优点：（1）在ALOHA…...

编程新知 2025/7/6 2:59:21

JVM虚拟机：内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机（Java Virtual Machine 简称：JVM）是运行所有 Java 程序的抽象计算机，是 Java 语言的运行环境，实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息，使得 Java 程序只需生成在 JVM 上运行的目标代码（字节码），就可以…...

编程新知 2025/6/27 10:36:03

解读《网络安全法》最新修订，把握网络安全新趋势

《网络安全法》自2017年施行以来，在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂，网络攻击、数据泄露等事件频发，现行法律已难以完全适应新的风险挑战。 2025年3月28日，国家网信办会同相关部门起草了《网络安全…...

编程新知 2025/7/4 13:57:24

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析负载(Workload)是 Caliper 性能测试的核心部分，它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。一、负载模块基本结构一个典型的负载模块(如 workload.js)包含以下基本结构： use strict;/…...

编程新知 2025/6/21 12:54:36

1.树的度和m叉树

2.m叉树第i层至多有个结点或度为m的树第i层至多有个结点

3.高度为h的m叉树至多个结点

4.高度为h的m叉树至少有h个结点（高度为h，度为m的树至少有h+m-1个结点）

5.具有n个结点的m叉树的最小高度为

6.二叉树

相关文章：

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

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

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