完全二叉树的基本操作(顺序存储)
#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 …...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
