数据结构之树的性质总结

节点的度:该节点拥有的孩子个数

叶子节点:度为0的节点

层数:根节点为第一层,根的子节点为第二层,以此类推

所有树的性质:所有节点的总度数等于节点数减一

完全m叉树性质

完全m 叉树,节点的度数最大为m ,且必须按照从上到下从左到右的顺序依次填满,叶子节点只出现在倒数第一层和倒数第二层,如以下为一个完全三叉树

(1)第i 层最多拥有的节点个数为

(2)d 层的完全m 叉树最多拥有的节点个数为

假设完全m 叉树有n 个节点

(3) n 个结点的完全m 叉树的深度为 , ceil 表示向上取整

(4) 当i<d 时,第i 层节点个数为

d 层的节点个数为

(5)在满m 叉树中,一个编号为p 的结点(编号从1开始),它的深度是 ,它的父节点编号为 ,易得该结点的第k-1 个孩子的编号为p*k ,所以推导出该结点的第i 个孩子的编号为  

(6)对于n 个结点的二叉树,按从上到下,从左到右依次给结点编号

i 的双亲结点为i//2 ,若n<2i ,则i 是叶子结点,若n≥2i ,则其左孩子为2i ,若n≥2i+1 ,则其右孩子是结点2i+1 ,若n<2i+1 ,则其无左孩子

(7) n 个结点的不同二叉树有

经典例题

已知一个二叉树有x0 个叶子结点,则该二叉树的总结点数至少是

需要最少的结点,则除了叶子结点外其它结点度数都为2,设度数为2的结点有x2 个,则根据度数性质:所有节点的总度数等于节点数减一

所以该二叉树的总结点数至少是

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Hello算法】 > 第 2 关 >数据结构 之 数组与链表

数据结构 之 数组与链表 1&#xff1a;Understanding data structures &#xff01;——了解数据结构——1.1&#xff1a;Classification-分类-1.2&#xff1a;Type-类型- 2&#xff1a;Arrays are the bricks that make up the wall of data structures *——数组是组成数据结…

ActiveMQ介绍及linux下安装ActiveMQ

ActiveMQ介绍 概述 ActiveMQ是Apache软件基金下的一个开源软件&#xff0c;它遵循JMS1.1规范&#xff08;Java Message Service&#xff09;&#xff0c;是消息队列服务&#xff0c;是面向消息中间件&#xff08;MOM&#xff09;的最终实现&#xff0c;它为企业消息传递提供高…

Linux_iptables防火墙学习笔记

文章目录 iptables 概述四表五链iptables 安装启动iptables 配置详解iptables配置文件iptables配置语法iptables常用实例查看规则修改默认规则保存和备份规则恢复备份的规则清空规则放行SSH服务在ubuntu14.04中iptables规则持久化 iptables 概述 主机型 对主机进行保护 网络型…

Linux第89步_了解异步通知及其结构和函数

1、了解“异步通知” “异步通知”的核心就是信号。信号是采用软件模拟的“中断”&#xff0c;它由“驱动程序”主动向“应用程序”发送信号&#xff0c;并报告自己可以访问了&#xff0c;“应用程序”收到信号以后&#xff0c;就从“驱动设备”中读取或者写入数据。整个过程就…

JSON数据格式讲解与cJSON库的使用

文章目录 写在前面一、安装cJSON二、使用cJSON1、使用的文件2、如何传输数据&#xff1a;**** 三、JSON语法四、cJSON函数讲解1、cJSON结构体 **2、cJSON结构体与字符串之间的转换&#xff08;重要&#xff09;2.1、标题将cJSON结构体转换为字符串(常用)2.2、将字符串转为cJSON…

浅尝 express + ORM框架 prisma 的结合

一、prisma起步 安装&#xff1a; npm i prisma -g查看初始化帮助信息&#xff1a; prisma init -h查看初始化帮助信息结果&#xff1a; Set up a new Prisma projectUsage$ prisma init [options] Options-h, --help Display this help message --datasource-provider …

MQ概览及Kafka详解

文章目录 概览MQ优点MQ缺点常见MQ对比JMS消息模型点对点模式发布订阅模式 kafka基础架构发布订阅工作流程生产者生产者文件存储生产者分区策略生产者数据可靠性保证生产者数据一致性保证生产者ack机制ExactlyOnce生产者发送消息流程 消费者消费者分区分配策略消费者消费数据问题…

平价健身运动耳机哪个好?真实分享五款高性能产品

在挑选这些耳机时&#xff0c;我们应该综合考虑了音质、舒适度、耐用性、稳定性以及价格等多个因素&#xff0c;无论你是跑步爱好者、健身达人还是户外运动者&#xff0c;接下来就让我们一起探索高性能平价健身运动耳机有哪些吧&#xff0c;都是我真实使用分享的哦。 第一款&am…

Web3与社会契约:去中心化治理的新模式

在数字化时代&#xff0c;技术不断为我们提供新的可能性&#xff0c;而Web3技术作为一种基于区块链的创新&#xff0c;正在引领着互联网的下一波变革。它不仅改变了我们的经济模式和商业逻辑&#xff0c;还对社会契约和权力结构提出了全新的挑战和思考。本文将深入探讨Web3的基…

如何在CentOS安装Firefox并结合内网穿透工具实现公网访问本地火狐浏览器

文章目录 1. 部署Firefox2. 本地访问Firefox3. Linux安装Cpolar4. 配置Firefox公网地址5. 远程访问Firefox6. 固定Firefox公网地址7. 固定地址访问Firefox Firefox是一款免费开源的网页浏览器&#xff0c;由Mozilla基金会开发和维护。它是第一个成功挑战微软Internet Explorer浏…

折叠面板组件(vue)

代码 <template><div class"collapse-info"><div class"collapse-title"><div class"title-left">{{ title }}</div><div click"changeHide"> <Button size"small" v-if"sho…

node后端上传文件到本地指定文件夹

实现 第一步&#xff0c;引入依赖 const fs require(fs) const multer require(multer) 第二步&#xff0c;先设置一个上传守卫&#xff0c;用于初步拦截异常请求 /*** 上传守卫* param req* param res* param next*/ function uploadFile (req, res, next) {// dest 值…

如何在SFTP工具中使用固定公网地址远程访问内网Termux系统

文章目录 1. 安装openSSH2. 安装cpolar3. 远程SFTP连接配置4. 远程SFTP访问4. 配置固定远程连接地址 SFTP&#xff08;SSH File Transfer Protocol&#xff09;是一种基于SSH&#xff08;Secure Shell&#xff09;安全协议的文件传输协议。与FTP协议相比&#xff0c;SFTP使用了…

MVVM、MVC、MVP的区别

MVC、MVP 和 MVVM 是三种常见的软件架构设计模式&#xff0c;主要通过分离关注点的方式来组织代码结构&#xff0c;优化开发效率。 在开发单页面应用时&#xff0c;往往一个路由页面对应了一个脚本文件&#xff0c;所有的页面逻辑都在一个脚本文件里。页面的渲染、数据的获取&a…

Day01-环境准备与镜像案例

Day01-环境准备与镜像案例 1. 容器架构1.1 Iaas Paas Saas (了解)1.2 什么是容器1.3 容器vs虚拟机1.4 Docker极速上手指南1&#xff09;配置docker源(用于安装docker)2&#xff09;docker下载镜像加速的配置3&#xff09;自动补全 1.5 Docker C/S架构1.6 Docker的镜像管理1&…

每日练习——leetcode402. 移掉 K 位数字和17. 电话号码的字母组合

目录 402. 移掉 K 位数字 题目描述 解题思路 代码实现 17. 电话号码的字母组合 题目描述 解题思路 代码实现 402. 移掉 K 位数字 题目描述 给你一个以字符串表示的非负整数 num 和一个整数 k &#xff0c;移除这个数中的 k 位数字&#xff0c;使得剩下的数字最小。请…

为了保护版权,有大量图片需要加logo水印怎么办?快速批量加水印 一键可批量加水印几十张 几百张

一&#xff0c;加水印必要性 在数字化时代&#xff0c;图片作为信息传递的重要媒介&#xff0c;其保护和管理显得尤为重要。而给图片添加水印则是一种有效的方式&#xff0c;它不仅能够防止图片被未经授权地复制和盗用&#xff0c;还能够标明图片的来源和版权信息&#xff0c;…

【Spring】依赖注入(DI)时常用的注解@Autowired和@Value

目录 1、Autowired 自动装配 1.1、要实现自动装配不是一定要使用Autowired 1.2、Autowired的特性 &#xff08;1&#xff09;首先会根据类型去spring容器中找(bytype),如果有多个类型&#xff0c;会根据名字再去spring容器中找(byname) &#xff08;2&#xff09;如果根据名…

springcloud-fegin 组件调用

一、Feign 概述 Feign是Netflix开发的声明式、模板化的HTTP客户端&#xff0c; Feign可以帮助我们更快捷、优雅地调用HTTP API。 在Spring Cloud中&#xff0c;使用Feign非常简单——创建一个接口&#xff0c;并在接口上添加一些注解&#xff0c;代码就完成了。Feign支持多种…

llama-factory SFT系列教程 (二),大模型在自定义数据集 lora 训练与部署

文章目录 简介支持的模型列表2. 添加自定义数据集3. lora 微调4. 大模型 lora 权重&#xff0c;部署问题 参考资料 简介 文章列表&#xff1a; llama-factory SFT系列教程 (一)&#xff0c;大模型 API 部署与使用llama-factory SFT系列教程 (二)&#xff0c;大模型在自定义数…