二叉树实现的相关函数
1.二叉树的创建
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{ if (n==0||a[*pi] == '#'){ (*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->_data = a[(*pi)++];root->_left = BinaryTreeCreate(a, --n, pi);root->_right = BinaryTreeCreate(a, --n, pi);return root;}
形参中BTDataType* a是自定义类型的数组,用与给二叉树的结点赋值,int n是数组元素的个数,int*pi是当前将要放入二叉树的元素的下标。本方法适用于用前序遍历的结果来创建二叉树。若采用别的遍历方式需修改代码中调用函数和数组赋值的位置。
2.二叉树的销毁
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (root == NULL){return;}if ((*root)->_left){free((*root)->_left);(*root)->_left = NULL;}if ((*root)->_right){free((*root)->_right);(*root)->_right = NULL;}free(*root);*root = NULL;return;
}
销毁采用后序遍历的方式,先销毁结点的左右子树,再销毁当前结点。若先销毁当前结点,无法找到该结点的左右子树的位置。
3.求二叉树结点的个数
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;}
采用后续遍历的方式,求出当前结点的左右子树的结点个数,相加后再加上当前结点(+1的由来)。
4.求叶子结点的个数
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->_left==NULL && root->_right==NULL){return 1;}return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);}
叶子结点是左右子树都为空且自己本身不为空的结点,由于此处需要通过访问左右子树来判断,所以在这之前必须判断当前结点是否为空。在当前结点有子结点的时候,则访问子树,返回子树的叶子结点个数。
5.求第k层结点的个数
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);}
对当前结点的第k层,就是对当前结点的子节点的第k-1层。对于结点为空的判断和对层的判断先后顺序不能修改,因为可能会有k==1的时候是空结点的情况,此时不应该加1.(即k=2的时候恰好是叶子结点的情况)
6.查找值为x的结点
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->_data == x){return root;}BTNode* left = BinaryTreeFind(root->_left, x);if (left != NULL){return left;}return BinaryTreeFind(root->_right, x);}
通过先序遍历的方式遍历所有结点,找到值符合的就返回,都不符合的时候返回NULL。
此处判断左子树是否为空不判断右子树的原因是此时左子树已经为空,若右子树有则返回右子树,若右子树为空则返回右子树(也是空结点)。
7.层序遍历
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{queue<BTNode*> q;if (root == NULL){ return;}q.push(root); while (!q.empty()){BTNode* tmp = q.front();printf("%c ", tmp->_data);q.pop();if (tmp->_left){q.push(tmp->_left);}if (tmp->_right){q.push(tmp->_right);}}printf("\n");return;}
思路:通过队列先进先出的特性,使得当前队列中恒保持只有相邻两层或只有一层的结点的情况。
8.判断是否是满二叉树
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{queue<BTNode*> q;if (root == NULL){return 1;}int count = 0;q.push(root);while (!q.empty()){BTNode* tmp = q.front();q.pop();if (tmp->_left&&count==0){q.push(tmp->_left);}else if (tmp->_left && count == 1){return 0;}else if(tmp->_left==NULL&&count==0){count = 1;}if (tmp->_right&&count==0){q.push(tmp->_right);}else if (tmp->_right && count == 1){return 0;}else if (tmp->_right == NULL && count == 0){count = 1;}}return 1;}
满二叉树的特性就是层序遍历的情况下,出现一次结点为空以后,就不会再有结点不为空的情况,此处用count=1表示第一次遇到结点为空,此后存在两种情况,一种是后面的结点全是空,最后队列为空退出,此时是满二叉树。一种情况是后面又遇到非空结点,由于此时count已经等于1了,则不是满二叉树。
相关文章:
二叉树实现的相关函数
1.二叉树的创建 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (n0||a[*pi] #){ (*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root->_data a[(*pi)];root->_left BinaryTreeCreate(a, --n, pi);root->_right Binary…...
Redis面试题(二)
文章目录 前言一、Redis 支持的 Java 客户端都有哪些?官方推荐用哪个?二、Redis 和 Redisson 有什么关系?三、Jedis 与 Redisson 对比有什么优缺点?四、说说 Redis 哈希槽的概念?五、Redis 集群的主从复制模型是怎样的…...
STP介绍
目录 STP概述 二层环路带来的问题 1.广播风暴 2.MAC地址漂移问题 3.多帧复制---这个好理解,同一个数据帧被重复收到多次,被称为多帧复制。 802.1D生成树 STP的BPDU BPDU主要分为两大类 配置BPDU RPC COST 配置BPDU的工作过程 TCN BPDU TCN…...
numpy 和 tensorflow 中的各种乘法(点乘和矩阵乘)
嗨喽,大家好呀~这里是爱看美女的茜茜呐 👇 👇 👇 更多精彩机密、教程,尽在下方,赶紧点击了解吧~ python源码、视频教程、插件安装教程、资料我都准备好了,直接在文末名片自取就可 点乘和矩阵乘…...
(图论) 1020. 飞地的数量 ——【Leetcode每日一题】
❓ 1020. 飞地的数量 难度:中等 给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个 海洋单元格、1 表示一个 陆地单元格。 一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边…...
c++ 重载、重写、覆盖
重载:指在同一作用域内,有多个同名但参数不同的函数的现象,叫重载;可以是任何用户定义的函数,例如 类成员函数、类静态函数、普通函数重写:子类重写父类的同名函数,只要子类出现有父类的同名函数…...
Python异步编程高并发执行爬虫采集,用回调函数解析响应
一、问题:当发送API请求,读写数据库任务较重时,程序运行效率急剧下降。 异步技术是Python编程中对提升性能非常重要的一项技术。在实际应用,经常面临对外发送网络请求,调用外部接口,或者不断更新数据库或文…...
SpriteKit与Swift配合:打造您的第一个简易RPG游戏的步骤指南
1. 简介: RPG(Role-Playing Game)游戏是一种角色扮演游戏,它允许玩家在一个虚拟的游戏世界中扮演一个或多个角色。在本教程中,我们将使用Apple的2D游戏框架SpriteKit和Swift编程语言来创建一个简单的RPG游戏。我们将从…...
服务网格的面临挑战:探讨服务网格实施中可能遇到的问题和解决方案
🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...
leetcode61 旋转链表
题目 给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。 示例 输入:head [1,2,3,4,5], k 2 输出:[4,5,1,2,3] 解析 这道题属实不好想:需要计算出链表的长度,然后在k > n的…...
【学习笔记】各类基于决策单调性的dp优化
文章目录 对于决策单调性的一般解释关于决策单调性的证明四边形不等式一维dp区间dp一种二维dp一些满足四边形不等式的函数类 与图形相结合 决策单调性的常见优化手段二分队列二分栈分治类莫队做法 SMAWKWQS二分WQS多解情况满足四边形不等式的序列划分问题的答案凸性以及WQS二分…...
【C++】构造函数初始化列表 ⑤ ( 匿名对象 生命周期 | 构造函数 中 不能调用 构造函数 )
文章目录 一、匿名对象 生命周期1、匿名对象 生命周期 说明2、代码示例 - 匿名对象 生命周期 二、构造函数 中调用 构造函数1、构造函数 中 不能调用 构造函数2、代码示例 - 构造函数中调用构造函数 构造函数初始化列表 总结 : 初始化列表 可以 为 类的 成员变量 提供初始值 ;…...
Knife4j系列--使用方法
原文网址:Knife4j系列--使用/教程/实例/配置_IT利刃出鞘的博客-CSDN博客...
pmp项目管理考试是什么?适合哪些人学?
PMP,简单点说,就是美国PMI为考察项目管理人士的专业能力而设立的考试。 该流程以知识和任务驱动型指南评估从业者的能力,同时确定项目经理能力行业标准,包括各项知识、任务和技能的特点、重要性与运用频率。(考纲原文…...
CSDN博客可以添加联系方式了
csdn博客一直不允许留一些联系方式,结果是官方有联系方式路径 在首页,往下拉,左侧就有 点击这个即可添加好友了~ 美滋滋,一起交流, 学习技术 ~...
小程序隐私弹窗的实现
小程序的开发者对于微信官方来说是有爱有恨,三天二头整事是鹅厂的一贯风格。 隐私弹窗的几个要点 回归正题,小程序隐私弹窗的几个要点: 1、何时弹出用户隐私协议的弹窗? 2、是每次进小程序都弹出来吗? 这两个想明…...
【JavaEE】多线程案例-单例模式
文章目录 1. 前言2. 什么是单例模式3. 如何实现单例模式3.1 饿汉模式3.2 懒汉模式4. 解决单例模式中遇到的线程安全问题4.1 加锁4.2 加上一个判断解决频繁加锁问题4.2 解决因指令重排序造成的线程不安全问题 1. 前言 单例模式是我们面试中最常考到的设计模式。什么是设计模式呢…...
社区分享|MeterSphere变身“啄木鸟”,助力云帐房落地接口自动化测试
云帐房网络科技有限公司(以下简称为“云帐房”)成立于2015年3月,以“成为最值得信赖的税务智能公司”为愿景,运用人工智能、大数据等互联网技术,结合深厚的财税行业服务经验,为代账公司和中大型企业提供智能…...
fpga内嵌逻辑分析仪使用方法
文章目录 前言一、方法1 — 使用 IP 核创建 ILA 调试环境1、创建 ILA ip 核2、进行例化3、生成比特流文件4、下载程序5、进行在线调试 二、方法2 — 使用 Debug 标记创建 ILA1、Debug 标记相关信号2、综合操作3、设置 Set Up Debug4、生成比特文件5、下载程序6、进行在线调试 前…...
第14章 结构和其他数据形式
本章介绍以下内容: 关键字:struct、union、typedef 运算符:.、-> 什么是C结构,如何创建结构模板和结构变量 如何访问结构的成员,如何编写处理结构的函数 联合和指向函数的指针 设计程序时,最重要的步骤之…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
