【数据结构初阶】二叉树与堆(一)

文章目录

  • 一、树的基础概念
    • 1、节点与度数
    • 2、树的度与高度
    • 3、引入:数组下标为何从0开始
    • 4、祖先节点
    • 5、树是递归定义的
    • 6、树与非树的区别
    • 7、代码表示
  • 二、二叉树
    • 2.1、满二叉树
    • 2.2、完全二叉树
    • 2.3、完全二叉树的存储
  • 三、堆

一、树的基础概念

1、节点与度数

节点分为叶节点与分支节点

  • 度数:其子节点的个数
  • 叶节点:无子节点,即节点度数为0
  • 分支节点:度数不为0的节点

2、树的度与高度

  • 树的度:节点中度数最大的度数为树的度
  • 树的高度(深度):树的最大层次
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bg1ltLM8-1722609222670)(https://i-blog.csdnimg.cn/direct/1e7c57da3e6c473e9ee335e7e7056995.png)]

3、引入:数组下标为何从0开始

答:迫于无奈,方便计算。
已知:数组名=数组首元素的地址
且 a[i] = *( a+i )
若下标从1开始,那么首元素 = *( a+1 )该式显然不成立。

4、祖先节点

从我这个节点往上这条路径的节点均为我的祖先节点。

在这里插入图片描述

5、树是递归定义的

一个树可分为根和子树(度>=0)。
在这里插入图片描述

在这里插入图片描述

6、树与非树的区别

树:

  1. 子树间不相交
  2. 除根节点外,每个节点有且仅有一个母(父)节点

非树:子树间相交。

7、代码表示

存储方法:左孩子右兄弟模型(链表)

struct TreeNode
{int val;struct TreeNode* LeftChild;struct TreeNode* RightSister;
};

在这里插入图片描述

二、二叉树

1、定义:树的每个节点的度数最大为2
2、代码模型:左孩子右孩子(可参考左孩子右兄弟模型)

2.1、满二叉树

1、定义:每一层都是满的(2个节点),叶子只在最后一层。
2、第 k 层有 2^(k-1)个节点
总节点个数:2^k - 1
在这里插入图片描述

2.2、完全二叉树

1、定义:设二叉树的高度为k,其前k-1层都是满的,最后一层不满且从左到右必须是连续的。
2、满二叉树是特殊的完全二叉树。
在这里插入图片描述

2.3、完全二叉树的存储

物理结构:在内存中以数组的形式存储。
在这里插入图片描述

原理:在内存中存储以数组的形式,已知一个父节点,则它的后两个数据一定是它的子节点。

  • 1、局限
    只适用于完全/满二叉树,对非完全也可以,但存在很大的空间浪费。

  • 2、优点
    便于访问母(父)子关系
    已知父节点下标为 i
    则 左孩子下标为 2 * i+1, 右孩子下标为 2*i+2

    已知一个子节点的下标为 j
    1、j 为奇数时,为左孩子,父下标为 (j -1)/2
    2、j 为偶数时,为右孩子,父下标为 (j -2)/2
    但在C语言中,除后取整
    故可直接写为 (j -1)/2

三、堆

注:
1、堆是一个完全二叉树(可用数组存储)
2、C语言中的堆、栈是内存的划分,与数据结构中的堆(二叉树)、栈(后进先出)不一样

大堆:任何一个父节点都大于等于其子节点
小堆:任何一个父节点都小于等于其子节点
在这里插入图片描述

3、特点
可以直接得到极值。大堆:根是极大值,小堆:根是极小值。

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

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

相关文章

多语言海外AEON抢单可连单加额外单源码,java版多语言抢单系统

多语言海外AEON抢单可连单加额外单源码,java版多语言抢单系统。此套是全新开发的java版多语言抢单系统。 后端java,用的若依框架,这套代码前后端是编译后的,测试可以正常使用,语言繁体,英文,日…

Charles怎么修改参数

Charles怎么修改参数 1、再【Structure】下,找到需要抓取的包,鼠标右键,点中断点。 2、在【Proxy】-点击【Breakpoint Settings…】 3、双击设置断点的接口 4、勾选后,点击【OK】。 5、再次刷新,重新发请求&#…

Nginx解析漏洞

一、nginx_parsing 这个解析漏洞其实是PHP CGI的漏洞,在PHP的配置文件中有一个关键的选项cgi.fix_pathinfo默认是开启的,当URL中有不存在的文件,PHP就会向前递归解析。在一个文件/xx.jpg后面加上/php会将/xx.jpg/xx.php解析为php文件。 1、…

第三方库认识- Mysql 数据库 API 认识

文章目录 一、msyql数据库API接口1.初始化mysql_init()——mysql_init2.链接数据库mysql_real_connect——mysql_real_connect3.设置当前客户端的字符集——mysql_set_character_set4.选择操作的数据库——mysql_select_db5.执行sql语句——mysql_query6.保存查询结果到本地——…

修改mac的音量能像windows系统那样给出音量反馈吗?

一、背景 windows有一些非常好的设计,比如拖动音量条的时候会有对应的音量大小的反馈。有时还能用来确定是视频没声音还是电脑坏了 在mac里怎么设置? 二、方法 首先点击菜单栏音量按钮->声音偏好设置…->勾选 “当更改音量时播放反馈”。 mac…

运放失调电流,偏置电流产生原因 ,对运放电路有什么影响,减小偏置电流带来的影响,TINA仿真。

偏置电流,失调电流定义 运放除了输入失调电压外,正常工作的时候,始终存在不为零的静态流进电流,如图所示: 对于BJT组成输入级的运放,这个电流就是差动输入级晶体管的基极电流IBQ,没有它&#xf…

Spring Boot+MyBatis+MySQL如何实现读写分离

​ 博客主页: 南来_北往 系列专栏:Spring Boot实战 背景 读写分离是数据库架构中的一种优化策略,它将读操作(查询)和写操作(更新、插入、删除)分开处理,通常通过将读请求和写请求分别发送…

正点原子imx6ull-mini-Linux驱动之异步通知实验(13)

在前面使用阻塞或者非阻塞的方式来读取驱动中按键值都是应用程序主动读取的,对于非 阻塞方式来说还需要应用程序通过 poll 函数不断的轮询。最好的方式就是驱动程序能主动向应 用程序发出通知,报告自己可以访问,然后应用程序在从驱动程序中读…

传统CS网络的新生——基于2G网络的远程灌溉实现

概述:iphone 实现远程电话触发,实现灌溉绿植的一般方法 方法一: 远程电话触发,音频线左右声道会产生一个信号,可以在后端利用SR锁存器暂存信号,后级可以接相应的控制电路实现灌溉。 方法二: 同…

【JavaScript】详解默认导出和命名导出的区别

文章目录 一、默认导出二、命名导出三、默认导出和命名导出的区别四、实际应用案例五、总结 在JavaScript模块化开发中,导入和导出模块是核心操作。ES6引入的模块化语法提供了两种主要的导出方式:默认导出(default export)和命名导…

【数学建模】——【A题 信用风险识别问题】全面解析

目录 1.题目 2.解答分析 问题1:指标筛选 1.1 问题背景 1.2 数据预处理 1.3 特征选择方法 1.4 多重共线性检测 1.5 实现步骤 问题2:信用评分模型 2.1 问题背景 2.2 数据分割 2.3 处理不平衡数据 2.4 模型选择与理由 问题3:模型对…

notes for datawhale summer camp chemistry task3

Transformer transformer的诞生 循环神经网络:由于所有的前文信息都蕴含在一个隐向量里面,这会导致随着序列长度的增加,编码在隐藏状态中的序列早期的上下文信息被逐渐遗忘。 卷积神经网络:受限的上下文窗口在建模长文本方面天…

Taming Lookup Tables for Efficient Image Retouching

Abstract 高清屏幕在终端用户相机、智能手机和电视等边缘设备中的广泛使用,刺激了对图像增强的巨大需求。现有的增强模型通常针对高性能进行优化,但不能减少硬件推断时间和功耗,尤其是在计算和存储资源受限的边缘设备上。为此,我…

信息学奥赛初赛天天练-53-CSP-J2019阅读程序2-模拟算法在数组中典型应用

PDF文档公众号回复关键字:20240802 2019 CSP-J 阅读程序2 1阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填 √,错误填 。除特殊说明外,判断题 1.5 分,选择题 3 分,共计 40 分) 假设输入的n和m都是正整…

前端Web-JavaScript(上)

要想让网页具备一定的交互效果,具有一定的动作行为,还得通过JavaScript来实现, 这门语言会让我们的页面能够和用户进行交互。 什么是JavaScript JavaScript(简称:JS) 是一门跨平台、面向对象的脚本语言,是…

【C++11】:右值引用移动语义完美转发

目录 前言一,左值引用和右值引用二,左值引用与右值引用比较三,探索引用的底层四,右值引用使用场景和意义4.1 解决返回值问题4.2 STL容器插入接口的改变 五,移动语义六,完美转发6.1 模板中的&& 万能…

产品经理如何快速掌握大模型技术,享受AI红利?

前言 随着人工智能(AI)技术的快速发展,AI产品经理的角色变得越来越重要。尽管AI产品经理并不是一个新鲜的概念,但随着AI技术的迭代升级,这一角色的重要性得到了显著提升。 AI产品经理的演变 早期的AI产品可能并不会…

网络原理的TCP/IP

TCP/IP协议 1)应用层 应用层和应用程序直接相关,与程序员息息相关的一层协议,应用层协议,里面描述的内容,就是写的程序,通过网络具体按照啥样的方式来进行传输,不同的应用程序,就可以用不同的应用层协议,在实际开发的过程中,需要程序员自制应用层协议 应用层协议本质上就是对…

python: 多进程实例

1. 实例一 主进程跟子进程的通过两个队列实现全双工通信;如有需要主进程会提示窗口输入信息传输给子进程;如果子进程收到主进程的消息,会弹窗提示收到的消息;子进程弹窗提示进程即将结束; 详细代码如下 # -*- coding…