数据结构-思考完全二叉树

        我们知道在完全二叉树中 :

      (孩子下标-1)/ 2 ==  父节点下标

        父节点下标*2+1 = 左孩子节点

        父节点下标*2+2 = 右孩子节点        

        那我们该怎样理解以便之后不容易忘记呢?

        以下是我的思考过程:观察下边的完全二叉树的下标规律

        小结论一:首先可以轻易看出,完全二叉树的左孩子都是奇数,右孩子都是偶数

        我们想象俩个相邻的数字,一个奇数一个偶数 ,那么这俩个数除以2得到的商有俩种情况:

        若第一个数字为奇数 第二个数字为偶数(例如7,8)那么除以二后他俩的数字关系是差1

        若第一个数字为偶数 第二个数字为奇数(例如8,9)那么除以二后他俩的数字是相同的

        小结论二:俩个相邻的数字如果第一个是偶数,那么经过除以2的操作后结果是一样的

        还是观察完全二叉树的结构,会发现孩子节点下标每走俩格,父节点就对应的走一格

        ,他们的变化率恒定为俩倍关系,

        小结论三:孩子节点的变化与父节点的变化关系为二倍,只要在映射关系中符合二倍关系,只需证明某一个特殊值符合条件,即可证明式子的普适性

        我们找一个特殊的孩子节点:最右下角的节点

         我们如果设最后一行节点的数量为m,那么我们可以轻易的得出:

        第一行到倒数第二行的节点数和为m-1,道理类似与一个绳子无限折半;

        树的结点数为2m-1    ;

        最后一个结点的下标为2m-2(数组从0开始算);显然为偶数

        倒数第二个结点的下标为2m-3;显然为奇数

        倒数第二行的最后一个结点(以上俩个结点的父结点)下标为m-2;

        根据小结论2,对俩个孩子结点处理,处理为第一个偶数第二个奇数:

        具体方式为-1;

        左孩子-1 = 2m-4 为偶数

        右孩子-1 = 2m-3 为奇数

        观察可得(左孩子或右孩子-1)/2 = 父结点;特殊值成立

        因为该式子孩子权重为0.5,父结点权重为1 符合小结论三,固(孩子下标-1)/ 2 ==  父节点下标成立。

        核心:知道-1的目的为让俩个数的关系变为第一个为偶数的相邻的数字

        至于以下俩条:

        父节点下标*2+1 = 左孩子节点

        父节点下标*2+2 = 右孩子节点     

        我们继续用特殊数值延伸到普遍的办法:
        父结点:m-2;    左孩子2m-3    右孩子2m-2

        父结点*2 = 2m-4

        父结点(2m-4)+1 = 左孩子 = 2m-3

        父节点(2m-4)+2 = 右孩子 = 2m-2

        由小结论三个只式子成立  

        

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

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

相关文章

Docker HTTPS api V2 Manifest V 2, Schema 2 下的免装docker下载镜像的方法

目录 前言 下载镜像代码 使用方法 原代码中无法适配 Schema 2 的原因浅析 如何解决 相对原代码改动的东西 前言 本文提供代码主要是基于 https://github.com/NotGlop/docker-drag 提供的代码修改的。链接中提供的代码应该是是基于HTTPS api V2 Manifest V 2, Schema 1实…

如何使用pycrypt加密工具测试反病毒产品的检测性能

关于pycrypt pycrypt是一款基于Python 3语言开发的加密工具,广大研究人员可以使用该工具来尝试绕过任意类型的反病毒产品,以检测目标反病毒产品的安全性能。 功能介绍 1、目前已知反病毒产品检测率为0/40; 2、支持绕过任意EDR解决方案&#…

Nodejs+Socket.io+Web端完成聊天

前言 源码获取:nodeexpresssocket.ioweb: 聊天demo (gitee.com) 目录结构 后端依赖 启动方式 前端是html正常启动 后端是node app.js 后端app.js核心代码 const express require(express) const app express() var http require(http).Server(app) var io require(so…

AI网络爬虫-自动获取百度实时热搜榜

工作任务和目标&#xff1a;自动获取百度实时热搜榜的标题和热搜指数 标题&#xff1a;<div class"c-single-text-ellipsis"> 东部战区台岛战巡演练模拟动画 <!--48--></div> <div class"hot-index_1Bl1a"> 4946724 </div> …

uniapp+vue3+ts开发小程序或者app架构时候的UI框架选型

使用vue3tsviteuniapp开发小程序或者跨平台app的趋势越来越高&#xff0c;有一个顺手的UI的框架还是非常重要的&#xff0c;官方维护的 uni-ui&#xff0c;支持全端&#xff0c;而且有类型提示&#xff0c;目前已经内置到 GitHub - Sjj1024/uniapp-vue3: 使用uniapp和vue3 ts …

01-05.Vue自定义过滤器

目录 前言过滤器的概念过滤器的基本使用给过滤器添加多个参数 前言 我们接着上一篇文章01-04.Vue的使用示例&#xff1a;列表功能 来讲。 下一篇文章 02-Vue实例的生命周期函数 过滤器的概念 概念&#xff1a;Vue.js 允许我们自定义过滤器&#xff0c;可被用作一些常见的文本…

Photoshop插件(UXP)编写过程中,如何更新sp-checkbox的选中状态

✨问题说明 sp-checkbox是uxpSpectrum UXP Widgets下的一个小组件&#xff0c;内置样式大概是这样&#xff1a; 那么&#xff0c;如果用js动态的改变选中的状态&#xff0c;应该如何做呢&#xff1f; 如果直接是html来写&#xff1a; <sp-checkbox checked>Checked<…

部门来了个测试开发,听说是00后,上来一顿操作给我看蒙了...

公司新来了个同事&#xff0c;听说大学是学的广告专业&#xff0c;因为喜欢IT行业就找了个培训班&#xff0c;后来在一家小公司实习半年&#xff0c;现在跳槽来我们公司。来了之后把现有项目的性能优化了一遍&#xff0c;服务器缩减一半&#xff0c;性能反而提升4倍&#xff01…

Java——图书管理系统万字详解(附代码)

框架搭建 book包 将书相关的放到book包中&#xff0c;创建一个Book类用来设置书的属性&#xff0c;包括书名、作者、价格、类型、是否被借出等。 以上属性均被private所修饰 利用编译器生成构造方法&#xff08;不需要构造isBorrowed&#xff0c;因为其初始值为false&#…

代码审计--一道简单的文件包含题目的多种利用方式

NO.1 传统方法 首先来看下代码 <?php error_reporting(0); if(isset($_GET["file"])){include($_GET["file"]); }else{highlight_file(__FILE__);phpinfo(); } ?>看完代码后再来学习学习函数吧&#xff0c;毕竟菜啊&#xff01;&#xff01;&…

【图书推荐】《Vue.js 3.x+Element Plus从入门到精通(视频教学版)》

配套示例源码与PPT课件下载 百度网盘链接: https://pan.baidu.com/s/1nBQLd9UugetofFKE57BE5g?pwdqm9f 自学能力强的&#xff0c;估计不要书就能看代码学会吧。 内容简介 本书通过对Vue.js&#xff08;简称Vue&#xff09;的示例和综合案例的介绍与演练&#xff0c;使读者…

【独家揭秘!玩转ChatGPT?一文带你解锁秘籍!】

&#x1f680;【独家揭秘&#xff01;玩转ChatGPT&#xff1f;一文带你解锁秘籍&#xff01;】&#x1f680; &#x1f449; 【直达ChatGPT体验站】 ChatGPT&#xff0c;全称“Chat Generative Pre-trained Transformer”&#xff0c;是人工智能研究实验室OpenAI于2022年底推出…

夏日炎炎,手机如何避免变成热源?这些降温技巧分享给你

夏日炎炎&#xff0c;手机也容易“中暑”。 高温不仅会让手机性能大打折扣&#xff0c;还可能引发安全隐患。因此&#xff0c;如何让手机在高温下“冷静”下来&#xff0c;成为了许多手机用户关心的问题。 本文将为你提供一些实用的降温技巧&#xff0c;帮助你的手机安全度过…

Python数据可视化(四)

实现图形的动画效果 在 matplotlib 中&#xff0c;不仅可以绘制静态图形&#xff0c;也可以绘制动态图形。对于动态图形来说&#xff0c;我们称 之为动画或许会让读者更容易明白。绘制动画的方法主要有两种&#xff1a;一种是使用模块 animation 绘制动 画&#xff1b;另一种是…

【C++题解】1699 - 输出是2的倍数,但非3的倍数的数

问题&#xff1a;1699 - 输出是2的倍数&#xff0c;但非3的倍数的数 类型&#xff1a;循环 题目描述&#xff1a; 请从键盘读入一个整数 n&#xff0c;输出 1∼n 中所有是 2 的倍数&#xff0c;但非 3 的倍数的数&#xff0c;每行 1个。 比如&#xff0c;读入一个整数10 &…

[Algorithm][动态规划][简单多状态DP问题][按摩师][打家劫舍Ⅱ][删除并获得点数][粉刷房子]详细讲解

目录 1.按摩师1.题目链接2.算法思路详解3.代码实现 2.打家劫舍 II1.题目链接2.算法思路详解3.代码实现 3.删除并获得点数1.题目链接2.算法思路详解3.代码实现 4.粉刷房子1.题目链接2.算法思路详解3.代码实现 1.按摩师 1.题目链接 按摩师 2.算法思路详解 思路&#xff1a; 确…

2024 ISCC pwn wp

iscc 练武pwn 总结第一周chaosISCC_easyFlagshopping 第二周ISCC_easyISCC_Uheapheap 第三周miaoYour_programeazy_heap 总结 总体感觉iscc考察的题目都挺基础的&#xff0c;在目前这种比赛的大环境下&#xff0c;仍然出这种&#xff0c;比较基础的题目&#xff0c;实在是难得…

原生js实现拖拽改变元素顺序

代码展示如下&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title>…

NLP(19)--大模型发展(3)

前言 仅记录学习过程&#xff0c;有问题欢迎讨论 大模型训练相关知识&#xff1a; 问题&#xff1a; 数据集过大&#xff0c;快速训练模型过大&#xff0c;gpu跑不完 方案&#xff1a; 数据并行训练&#xff1a; 复制数据&#xff08;batch_size&#xff09;到多个gpu&…

毕设 大数据校园卡数据分析

文章目录 0 前言1 课题介绍2 数据预处理2.1 数据清洗2.2 数据规约 3 模型建立和分析3.1 不同专业、性别的学生与消费能力的关系3.2 消费时间的特征分析 4 Web系统效果展示5 最后 0 前言 &#x1f525; 这两年开始毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的毕设…