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

数据结构:完全二叉树开胃菜小练习

目录

一.前言

二.完全二叉树的重要结构特点

三.完全二叉树开胃菜小练习

1.一个重要的数学结论

2.简单的小练习


一.前言

关于树及完全二叉树的基础概念(及树结点编号规则)参见:http://t.csdn.cn/imdraicon-default.png?t=N176http://t.csdn.cn/imdra

完全二叉树是一种非常重要的数据结构:

n个结点的完全二叉树结点编号是从0~(n-1)连续排列的(假设根结点的编号为0),因此将完全二叉树映射到内存中线性存储结构中内存利用效率十分的高(数组下标和树结点编号建立绝对映射关系).

最经典的完全二叉树线性存储结构就是大小根堆(堆排序的数据结构基础)

二.完全二叉树的重要结构特点

  • 假设一个结点总数为n完全二叉树T的高度为k,为了满足各结点编号是0~(n-1)连续排列的结构定义,完全二叉树1~(k-1)层所有结点构成的子结构是一颗满二叉树(也就意味着完全二叉树的所有叶结点分布在树的最后一层(第k层)):
  • 假设一个结点总数为n完全二叉树T的高度为k,为了满足各结点编号是0~(n-1)连续排列的结构定义,完全二叉树的第k层(最后一层)的叶节点必须是连续排列的(也就是意味着结点总数为奇数的完全二叉树不存在出度为1的分枝结点,结点总数为偶数的完全二叉树有且仅有一个出度为1的分枝结点)

三.完全二叉树开胃菜小练习

1.一个重要的数学结论

  • 对任何一棵二叉树, 如果出度为0其叶结点个数为N0出度为2的分枝结点个数为N2(包括根) ,则有 N0= N2+1

该结论具体证明参见小青菜的博客 :http://t.csdn.cn/imdraicon-default.png?t=N176http://t.csdn.cn/imdra

2.简单的小练习

  • 现有一颗具有 2n 个结点的完全二叉树T,求其叶结点的个数

求解:

设T出度为0的结点个数为N0(即叶结点的个数),

出度为1的结点个数为N1,

出度为2的结点个数为N2。

根据本篇第二章中的结构分析可知,N1要么为1,要么为0

  1. N1 = 0,根据关系式N0 = N2 + 1,可得:2n = N0 + N1 + N2,化简可得N0 = (2n+1)/2,N0不为整数,因此该种情况排除
  2. N1 =1,根据关系式N0 = N2 + 1,可得:2n = N0 + N1 + N2,化简可得N0 = n,满足题意

因此T叶节点个数为n

  • 一棵完全二叉树的结点总数为531个,求这棵树的高度

求解:

设该树的高度为k

根据本篇第二章中的结构分析可知,该树前k-1层构成一颗满树(根据等比数列求和公式满树总结点个数为2^(k-1)-1)

2^9 = 512<531<2^10 = 1024,因此k-1 = 9,可以求得该二叉树的高度为10

  • 现有一颗具有767个结点的完全二树T,求其叶子结点个数

求解:

设T出度为0的结点个数为N0(即叶结点的个数),

出度为1的结点个数为N1,

出度为2的结点个数为N2。

根据本篇第二章中的结构分析可知,N1要么为1,要么为0

  1. N1 = 0,根据关系式N0 = N2 + 1,可得:767 = N0 + N1 + N2,化简可得N0 = 384,满足题意
  2. N1 =1,根据关系式N0 = N2 + 1,可得:767 = N0 + N1 + N2,化简可得N0 = 767/2,N0不为整数,因此该种情况排除

因此T叶节点个数为384

 

 

 

相关文章:

数据结构:完全二叉树开胃菜小练习

目录 一.前言 二.完全二叉树的重要结构特点 三.完全二叉树开胃菜小练习 1.一个重要的数学结论 2.简单的小练习 一.前言 关于树及完全二叉树的基础概念(及树结点编号规则)参见:http://t.csdn.cn/imdrahttp://t.csdn.cn/imdra 完全二叉树是一种非常重要的数据结构: n个结点的…...

mybatis与jpa

1、官方文档 mybatis&#xff1a;mybatis-spring – jpa&#xff1a;https://springdoc.cn/spring-data-jpa/ 应用文档 jpa详解_java菜鸟1的博客-CSDN博客 JPA简介及其使用详解_Tourist-xl的博客-CSDN博客_jpa的作用 2、使用比较 mybatis一般用于互联网性质的项目&#x…...

js 求解《初级算法》66. 加一

一、题目描述 给定一个由 整数 组成的 非空 数组所表示的非负整数&#xff0c;在该数的基础上加一。最高位数字存放在数组的首位&#xff0c; 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外&#xff0c;这个整数不会以零开头。 示例 1&#xff1a; 输入&#xff1a…...

力扣-游戏玩法分析

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目&#xff1a;511. 游戏玩法分析二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他总结…...

ZZNUOJ_用C语言编写程序实现1186 : 奖学金(结构体专题)(附完整源码)

题目描述 某校发放奖学金共5种,获取条件各不同: 1.阳明奖学金,每人8000,期末平均成绩>80,且在本学期发表论文大于等于1篇; 2.梨洲奖学金,每人4000,期末平均成绩>85,且班级评议成绩>80; 3.成绩优秀奖,每人2000,期末平均成绩>90; 4.西部奖学金,…...

加油站ai系统视频监测 yolov5

加油站ai系统视频监测通过yolov5网络模型深度学习边缘计算技术&#xff0c;加油站ai系统视频监测对现场卸油过程中人员违规离岗、现场灭火器没有按要求正确摆放、以及卸油前需要遵守静电释放15分钟、打电话、明火烟雾情况、抽烟行为进行自动识别。YOLO系列算法是一类典型的one-…...

【JDK8新特性之Stream流-Stream结果收集案例实操】

一.JDK8新特性之Stream流-Stream结果收集以及案例实操 二.Stream结果收集(collect函数)-实例实操 2.1 结果收集到集合中 /*** Stream将结果收集到集合中以及具体的实现 collect*/Testpublic void test01(){// 收集到List中 接口List<Integer> list Stream.of(1, 2, 3…...

Fiddler 抓包工具

HTTP代理所谓的http代理&#xff0c;其实就是代理客户机的http访问&#xff0c;主要代理浏览器访问页面。代理服务器是介于浏览器和web服务器之间的一台服务器&#xff0c;有了它之后&#xff0c;浏览器不是直接到Web服务器去取回网页而是向代理服务器发出请求&#xff0c;Requ…...

2023最新版网络安全保姆级指南,手把手带你从零基础进阶渗透攻防工程师

前言 一份网络攻防渗透测试的学习路线&#xff0c;不藏私了&#xff01; 1、学习编程语言(phpmysqljshtml) 原因&#xff1a; phpmysql可以帮助你快速的理解B/S架构是怎样运行的&#xff0c;只有理解了他的运行原理才能够真正的找到问题/漏洞所在。所以对于国内那些上来就说…...

排序基础之选择排序法

目录 前言 一、什么是选择排序 二、实现选择排序 三、使用泛型扩展 四、使用自定义类型测试 前言 今天天气不错&#xff0c;这么好的天气不干点啥实在是有点可惜了&#xff0c;于是乎&#xff0c;拿出键盘撸一把&#xff01; 来&#xff0c;今天来学习一下排序算法中的选…...

2.24测试用例

一.测试模型1.V模型特点:1.明确标注了测试的类型2.明确标注了测试阶段和开发阶段的对应关系缺点:测试后置2.W模型也叫双v模型,测试阶段全流程介入缺点:1.上一阶段完成.下一个阶段才能开始2.开发模型和测试模型也保持着一种线性的前后关系3.重文档,重过程,不支持敏捷模式二.设计…...

面试必刷101 Java题解 -- part 1

练习地址 面试必刷101-牛客1、链表反转2、链表内指定区间反转**3. 链表中的节点每k个一组翻转**4、**合并两个排序的链表**5、**合并k个已排序的链表**6、**判断链表中是否有环****7、链表中环的入口结点**8、链表中倒数最后k个结点**9、删除链表的倒数第n个节点****10、两个链…...

Python---关联与继承

专栏&#xff1a;python 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;Python在学&#xff0c;希望能够得到各位的支持&#xff01;&#xff01;&#xff01; 关联与继承前言has a关联关系is a继承关系子类不添加__init__子类添加__init__前言 has a关联关系 has - a 是在…...

数据库行业的 “叛逆者”:大数据已“死”,MotherDuck 当立

“大数据”已死——现今我们最重要的事情不是担心数据大小&#xff0c;而是专注于我们将如何使用它来做出更好的决策。数据库行业发展至今&#xff0c;在数据层面有很多的加速和变革&#xff0c;尤其是过去几年的云数仓爆炸式增长&#xff0c;带来了行业的很多变化。毫无疑问&a…...

Linux->进程优先级

目录 1. 优先级的概念 2. 优先级的运作方式 3. Linux下查看进程优先级以及调整 3.1 查看进程优先级 3.2 修改进程优先级 1. 优先级的概念 1. cpu资源分配的先后顺序&#xff0c;就是指进程的优先权&#xff08;priority&#xff09;。 2. 优先权高的进程有优先执行权利。配…...

loki 日志管理的安装部署使用

loki介绍 Loki是 Grafana Labs 团队最新的开源项目&#xff0c;是一个水平可扩展&#xff0c;高可用性&#xff0c;多租户的日志聚合系统。它的设计非常经济高效且易于操作&#xff0c;因为它不会为日志内容编制索引&#xff0c;而是为每个日志流编制一组标签。 不对日志进行…...

CTFer成长之路之反序列化漏洞

反序列化漏洞CTF 1.访问url&#xff1a; http://91a5ef16-ff14-4e0d-a687-32bdb4f61ecf.node3.buuoj.cn/ 点击下载源码 本地搭建环境并访问url&#xff1a; http://127.0.0.1/www/public/ 构造payload&#xff1a; ?sindex/index/hello&ethanwhoamiPOST的参数&#…...

Python学习-----模块5.0(文件管理大师-->os模块)

目录 前言&#xff1a; 1.os.getcwd() 2. os.listdir(path) 3.os.walk(path) 4.os.path.exists(path) 5.os.mkdir(path) 6.os.makedirs(path,exist_okTrue) 7.os.rmdir(path) 8.os.remove(path) 9.os.path.join(p1,p2) 10.os.path.split(path) 11.os.path.isdi…...

第45届世界技能大赛“网络安全”赛项浙江省选拔赛竞赛任务书

第45届世界技能大赛浙江省选拔赛竞赛任务书 一、竞赛时间 8:00-17:00&#xff0c;共计9小时。 二、竞赛阶段 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 模块A 任务1 数据库安全加固 8:00-10:00 50 任务2 文件MD5校验 50 任务3 Linux系统服务渗透测试及安全加…...

【uniapp微信小程序】跨平台使用echarts的方案选择踩坑

一、前言 使用Uniapp&#xff08;vue&#xff09;开发微信小程序&#xff0c;想用echarts图表实现类似github热力图的效果。 简要列一些可行或不可行的方案。 二、方案对比 1. 【应用】&#xff1a;微信小程序原生开发 有echarts官网提供的跨平台方案&#xff1a;在微信小程…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...

Springboot 高校报修与互助平台小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;高校报修与互助平台小程序被用户普遍使用&#xff0c;为…...