完全二叉树的基本操作(顺序存储)
#include<iostream>
#include<math.h>
using namespace std;#define MaxSize 100
struct TreeNode {int value;bool isEmpty;//判断该节点是否为空
}t[MaxSize];/**
*定义一个长度位MaxSize的数组,按照从上到下,
*从左到右的方式依次存储完全二叉树的各个节点
*/
//TreeNode t[MaxSize];//初始化二叉树:注意从数组下标来进行存储
void InitTreeNode(TreeNode * t) {for (int i = 0; i < MaxSize; i++) {t[i].isEmpty = true;}
} /*
i的左孩子——2i
i的右孩子——2i+1
i的父节点——【i/2】
i所在的层次——log2的(n+1)向上取整 或者 log2的n(向下取整)
*///寻找i的左节点的数据
bool FindLeft(TreeNode* t, int size, int &value) {if (size * 2 > 100 - 1||t[size*2].isEmpty==true) {return false;}value = t[size*2].value;return true;
}//寻找i的右节点的数据
bool FindRight(TreeNode* t, int size, int& value) {if (size * 2 +1> 100 - 1 || t[size*2+1].isEmpty == true) {return false;}value = t[size*2+1].value;return true;
}//寻找i的父节点的数据
bool FindFather(TreeNode* t, int size, int& value) {if ( t[size /2].isEmpty == true) {return false;}value = t[size/2].value;return true;
}//寻找i的层次
double FindHigh(TreeNode* t, int size) {//i所在的层次——log2的(n+1)向上取整double a = 2;double b = size + 1;double result = log(b) / log(a);//进行向上取整result = ceil(result);return result;
}int main() {return 0;
}
一、整体功能概述
这段 C++ 代码主要实现了与完全二叉树相关的一些基本操作,包括二叉树节点结构体的定义、二叉树的初始化以及对完全二叉树中节点的左孩子、右孩子、父节点数据的查找,还有对节点所在层次的计算等功能。
二、代码结构分析
1. 头文件和命名空间
#include<iostream>
#include<math.h>
using namespace std;
- 包含了
<iostream>头文件用于输入输出操作,<math.h>头文件用于数学运算(如对数运算用于计算节点层次)。使用了using namespace std;,这种方式虽然方便但在大型项目中可能会导致命名冲突,更推荐按需使用std::限定符。
2. 二叉树节点结构体定义
#define MaxSize 100
struct TreeNode {int value;bool isEmpty;
}t[MaxSize];
- 通过宏定义
MaxSize确定了二叉树节点数组的最大容量为 100。定义了TreeNode结构体,包含一个整型的value字段用于存储节点的值,以及一个布尔型的isEmpty字段用于判断该节点是否为空。同时声明了一个名为t的TreeNode类型数组,用于存储完全二叉树的各个节点。
3. 二叉树初始化函数
//初始化二叉树:注意从数组下标来进行存储
void InitTreeNode(TreeNode * t) {for (int i = 0; i < MaxSize; i++) {t[i].isEmpty = true;}
}
- 该函数接受一个指向
TreeNode数组的指针t,通过循环将数组中每个节点的isEmpty字段设置为true,表示初始时所有节点都为空,为后续插入节点等操作做好准备。
4. 查找节点相关函数
查找左节点数据函数
//寻找i的左节点的数据
bool FindLeft(TreeNode* t, int size, int &value) {if (size * 2 > 100 - 1 || t[size * 2].isEmpty == true) {return false;}value = t[size * 2].value;return true;
}
- 此函数用于查找完全二叉树中指定节点(由
size索引确定)的左孩子节点的数据。首先判断左孩子节点的索引是否超出范围(通过size * 2 > 100 - 1判断)或者左孩子节点是否为空(通过t[size * 2].isEmpty == true判断),如果满足其中一个条件则返回false。否则,将左孩子节点的值赋给传入的引用参数value,并返回true。
查找右节点数据函数
//寻找i的右节点的数据
bool FindRight(TreeNode* t, int size, int &value) {if (size * 2 + 1 > 100 - 1 || t[size * 2 + 1].isEmpty == true) {return false;}value = t[size * 2 + 1].value;return true;
}
- 与查找左节点数据函数类似,用于查找指定节点的右孩子节点的数据。先进行索引范围和节点是否为空的判断,满足条件则返回
false,否则赋值并返回true。
查找父节点数据函数
//寻找i的父节点的数据
bool FindFather(TreeNode* t, intsize, int &value) {if (t[size / 2].isEmpty == true) {return false;}value = t[size / 2].value;return true;
}
- 该函数用于查找指定节点的父节点的数据。判断父节点是否为空(通过
t[size / 2].isEmpty == true判断),为空则返回false,否则赋值并返回true。
5. 计算节点层次函数
//寻找i的层次
double FindHigh(TreeNode* t, int size) {//i所在的层次——log2的(n+1)向上取整double a = 2;double b = size + 1;double result = log(b) / log(a);//进行向上取整result = ceil(result);return result;
}
- 此函数用于计算完全二叉树中指定节点(由
size索引确定)所在的层次。根据公式先通过对数运算计算出一个初步结果(以 2 为底的对数,通过换底公式log(b) / log(a)实现),然后使用ceil()函数对结果进行向上取整,最后返回该节点所在的层次值。
相关文章:
完全二叉树的基本操作(顺序存储)
#include<iostream> #include<math.h> using namespace std;#define MaxSize 100 struct TreeNode {int value;bool isEmpty;//判断该节点是否为空 }t[MaxSize];/** *定义一个长度位MaxSize的数组,按照从上到下, *从左到右的方式依次存储完全…...
【HTTP】http与https
http与https的关系 应用层协议: http(HyperText Transfer Protocol)超文本传输协议; https(Hypertext Transfer Protocol Secure)超文本传输安全协议; 传输层协议:TCP(Tr…...
【Git多人开发与协作之团队的环境搭建】
Git多人开发与协作之团队的环境搭建 新的改变1. Git 的用途2. 分支的概念与类型3. HEAD 和分支指针如何查看 HEAD 指向的位置: 4. 常见的 Git 操作5. 常见问题与解决方法总结GitHub 项目获取实操在新电脑上运行 Git1. 安装 Git2. 配置用户名和邮箱3.配置 Git 和 SSH…...
java基础概念36:正则表达式1
一、正则表达式的作用 作用一:校验字符串是否满足规则;作用二:在一段文本中查找满足要求的内容。——爬虫 二、正则表达式 2-1、字符类 示例: public static void main(String[] args) {System.out.println("a".matc…...
java实现小程序接口返回Base64图片
文章目录 引言I java 接口返回Base64图片接口设计获取验证码图片-base64字符串获取验证码图片-二进制流arraybufferII 小程序端代码过期代码: 显示文件流图片(arraybuffer)知识扩展:微信小程序下载后端返回的文件流引言 场景: 图形验证码 背景: 接口返回arraybuffer的格式…...
网络编程并发服务器的应用
作业2:完成局域网CS模型,局域网内一个服务器,多个客户端连接一个服务器,完成局域网聊天(select函数,poll函数,完成TCP并发服务器)。 poll函数应用: 服务器部分代码&…...
数据结构——停车场管理问题
目录 1、问题描述2、逐步分析1)涉及操作2)代码实现 3、代码整合 1、问题描述 1、题目 设停车场内只有一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列&#x…...
道品智能科技移动式水肥一体机:农业灌溉施肥的革新之选
在现代农业的发展进程中,科技的力量正日益凸显。其中,移动式水肥一体机以其独特的可移动性、智能化以及实现水肥一体化的卓越性能,成为了农业领域的一颗璀璨新星。它不仅改变了传统的农业灌溉施肥方式,更为农业生产带来了高效、精…...
AI实习--常用的Linux命令
一、基础命令 1. 切换到根目录。 cd ~ 2. 返回上一级目录。 cd .. 3. 查看当前目录下包括哪些文件和文件夹。 ls 4. 查看当前路径。 pwd 5. 将文件或文件夹剪切到目标目录下。 mv 文件所在路径 目标路径 6. 查看文本文件内容。 cat 文本文件名 7. 创建文件或文件夹…...
Python学习指南 + 谷歌浏览器如何安装插件
找往期文章包括但不限于本期文章中不懂的知识点: 个人主页:我要学编程(ಥ_ಥ)-CSDN博客 所属专栏: Python 目录 前言 Python 官方文档的使用 谷歌浏览器中如何安装插件 前言 在学习Python时,我们可能会出现这样的困惑&#x…...
研0找实习【学nlp】15---我的后续,总结(暂时性完结)
当下进展成果: nlptransformerpytorchhuggingfacebert简历环境配置表情识别文本分类 断更了快1个月,2个礼拜找实习,1个礼拜伤心,1个礼拜想我要干什么…… 承认自己的才疏学浅,了解了leetcode,和老师商量了…...
kylin麒麟银河桌面版操作系统安装部署
本文主要描述kylin麒麟银河桌面版操作系统的安装,该操作系统的安装源文件可以从kylin麒麟银河官方网站上下载,商业版本需要申请试用,开源版本可以直接下载使用。 如上所示,x86芯片处理器架构的请下载INTEL版本,华为海思…...
MyBatis插件原理及应用
🎮 作者主页:点击 🎁 完整专栏和代码:点击 🏡 博客主页:点击 文章目录 介绍<plugins>标签解析拦截器链的工作原理插件的应用场景MyBatis插件应用的四个组件InterceptorChain和Interceptor MyBatis框架…...
[M最短路] lc743. 网络延迟时间(spfa最短路+单源最短路)
文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接:743. 网络延迟时间 相关链接: [图最短路模板] 五大最短路常用模板) 2. 题目解析 怎么讲呢,挺抽象的…很久没写最短路算法了。反正也是写出来了,但脱离了模板,把…...
MySQL 中的锁
MySQL 中的锁:全面解析与应用指南 在 MySQL 数据库的复杂世界里,锁是确保数据一致性、完整性以及并发控制的关键机制。无论是简单的小型应用还是复杂的企业级系统,深入理解 MySQL 中的锁对于优化数据库性能、避免数据冲突和错误都具有至关重要…...
【动手学电机驱动】STM32-FOC(8)MCSDK Profiler 电机参数辨识
STM32-FOC(1)STM32 电机控制的软件开发环境 STM32-FOC(2)STM32 导入和创建项目 STM32-FOC(3)STM32 三路互补 PWM 输出 STM32-FOC(4)IHM03 电机控制套件介绍 STM32-FOC(5&…...
【C++11】尽显锋芒
(续) 一、可变参数模板 C11支持可变参数模板,也就是说支持可变数量参数的函数模板和类模板,可变数目的参数被称 为参数包,存在两种参数包:模板参数包,表示零或多个模板参数;函数参数包:表示零…...
掌握控制流的艺术:Go语言中的if、for和switch语句
标题:掌握控制流的艺术:Go语言中的if、for和switch语句 在Go语言的编程世界中,控制流语句是构建程序逻辑的基石。if语句、for循环和switch语句是我们最常用的控制流工具,它们让我们能够根据不同的条件执行不同的代码块。本文将深入探讨这些语句的使用方法、技术细节和实际…...
飞书会话消息左右排列
飞书会话消息左右排列 1. 飞书登录后,点击头像,弹出菜单有个按钮设置 2. 3....
.net 支持跨平台(桌面)系列技术汇总
1. 首先微软老大哥的.net core 。 .NET Core 是微软开发的一个跨平台、高性能的开源框架,用于构建云和互联网连接的新型应用。 它允许开发者在 Windows、macOS 和 Linux 上使用喜爱的开发工具进行开发,并支持部署到云或本地环境。 .NET Core 是对 .NET …...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
