当前位置: 首页 > news >正文

看完这篇我不信你不会二叉树的层序遍历【C语言】

目录

实现思路

代码实现


之前介绍了二叉树的前、中、后序三种遍历,采用的是递归的方式。今天我们来学习另外一种遍历方式——层序遍历。层序遍历不容小觑,虽然实现方法并不难,但是它所采取的思路是很值得学习的,与前三者不同,我们将采用非递归的方式实现。

层序遍历:从二叉树的根节点出发(设根节点所在为第一层),从上到下,从左到右的一次访问第一、第二、第三......层的节点。

实现思路

我们将采用一种数据结构——队列来实现层序遍历。以这样的二叉树为例:

我们知道队列有个重要的性质,只能从队尾进数据,在队头出数据

因此我们先将 1 入队。

接着让队头的元素 1 出队。在 1 出队的同时有个约定:将 1 所在节点的左、右孩子入队;

接着让队头的元素 2 出队。在 2 出队的同时,将 2 所在节点的左、右孩子入队(若为空节点则不入队);

队头元素 4 出队,左、右孩子入队;

队头元素 3 出队,左、右孩子入队;

队头元素 5 出队,左、右孩子入队;

......

最后,队列为空即表示所有节点都已访问完毕。

代码实现

因为此处用到了队列的知识,若有不明白队列的童鞋可以去看看<队列>的概念&结构&实现【C语言版】小补一下哦。

//队列的初始化
void QueueInit(Queue* pq);
//释放malloc出的内存
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头的数据
QDataType QueueFront(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);if(front->left)QueuePush(&q, front->left);if(front->right)QueuePush(&q, front->right);}printf("\n");QueueDestroy(&q);
}

相关文章:

看完这篇我不信你不会二叉树的层序遍历【C语言】

目录 实现思路 代码实现 之前介绍了二叉树的前、中、后序三种遍历,采用的是递归的方式。今天我们来学习另外一种遍历方式——层序遍历。层序遍历不容小觑,虽然实现方法并不难,但是它所采取的思路是很值得学习的,与前三者不同&am…...

案例17-环境混用带来的影响

目录一、背景介绍背景事故二、思路&方案三、过程四、总结nginx做转发fastdfs(文件上传下载)五、升华一、背景介绍 本篇博客主要介绍开发中项目使用依赖项环境闭一只带来的恶劣影响,在错误中成长进步。 背景 本公司另外一个产品开发God…...

知识蒸馏论文阅读:DKD算法笔记

标题:Decoupled Knowledge Distillation 会议:CVPR2022 论文地址:https://ieeexplore.ieee.org/document/9879819/ 官方代码:https://github.com/megvii-research/mdistiller 作者单位:旷视科技、早稻田大学、清华大学…...

Sentinel架构篇 - 熔断降级

熔断降级 概念 除了流量控制以外,对调用链路中不稳定的资源进行熔断降级也是保障高可用的重要措施之一。一个服务常常会调用其它模块,可能是一个远程服务、数据库、或者第三方 API 等。然而,被依赖的服务的稳定性是不能保证的。如果依赖的服…...

shell脚本的一些记录 与jenkins的介绍

shell 脚本的执行 sh ***.sh shell脚本里面的命令 其实就是终端执行一些命令 shell 连接服务器 可以直接ssh连接 但是这样最好是无密码的 不然后面的命令就不好写了 换而言之有密码得 不好写脚本 需要下载一些expect的插件之类的才可以 判断语句 的示例 需要注意的是…...

JVM的了解与学习

一:jvm是什么 jvm是java虚拟机java Virtual Machine的缩写 jdk包含jre和java DevelopmentTools 二:什么是java虚拟机 虚拟机是一种抽象化的计算机,通过在实际的计算机上仿真模拟各种计算机功能来实现的。java虚拟机有自己完善的硬体结构,如处理器、堆栈、寄存器等,还有…...

提升数字品牌的5个技巧

“品牌”或“品牌推广”的概念通常用于营销。因为建立您的企业品牌对于产品来说极其重要,品牌代表了您与客户互动的身份和声音。今天,让我们来看看在数字领域提升品牌的一些有用的技巧。如何在数字领域提升您的品牌?在了解这些技巧之前&#…...

java通过反射获取加了某个注解的所有的类

有时候我们会碰到这样的情况:有n个场景,每个场景都有自己的逻辑,即n个处理逻辑,这时候我们就需要通过某个参数的值代表这n个场景,然后去加载每个场景不同的bean对象,即不同的类,这些类中都有一个…...

Warshall算法

🚀write in front🚀 📜所属专栏:> 算法 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我…...

vector中迭代器失效的问题及解决办法

目录 vector常用接口 vector 迭代器失效问题 vector中深浅拷贝问题 vector的数据安排以及操作方式,与array非常相似。两者的唯一差别在于空间的运用的灵活性。array 是静态空间,一旦配置了就不能改变;要换个大(或小) 一点的房子&#x…...

【蓝桥杯刷题训练营】day05

1 数的分解 拆分成3个数相加得到该数 然后采用了一种巨愚蠢的办法&#xff1a; int main() {int count 0;int a 2;int b 0;int c 1;int d 9;int a1, a2, a3;int c1, c2, c3;int d1, d2, d3;for (a1 0; a1 < 2; a1){for (a2 0; a2 < 2; a2){for (a3 0; a3 <…...

线程中断interrupt导致sleep产生的InterruptedException异常

强制当前正在执行的线程休眠&#xff08;暂停执行&#xff09;&#xff0c;以“减慢线程”。 Thread.sleep(long millis)和Thread.sleep(long millis, int nanos)静态方法当线程睡眠时&#xff0c;它睡在某个地方&#xff0c;在苏醒之前不会返回到可运行状态。 当睡眠时间到期…...

ubuntu的快速安装与配置

文章目录前言一、快速安装二 、基础配置1 Sudo免密码2 ubuntu20.04 pip更新源3 安装和配置oneapi(infort/mpi/mkl) apt下载第一次下载的要建立apt源apt下载&#xff08;infort/mpi/mkl)4 安装一些依赖库等5 卸载WSLpython总结前言 win11系统 ubuntu20.04 提示&#xff1a;以下…...

人工智能AI工具汇总(AIGC ChatGPT时代个体崛起)

NameCategoryWebsiteDescription描述《AIGC时代&#xff1a;超级个体的崛起》小报童https://xiaobot.net/p/SuperIndividual 介绍AIGC&#xff0c;ChatGPT&#xff0c;使用技巧与搞钱方式。Masterpiece Studio3Dhttps://masterpiecestudio.comSimplifying 3D Creation with AI…...

【rust-grpc-proxy】在k8s中,自动注入代理到pod中,再不必为grpc调试而烦恼

目录前言原理sidecarwebhook实现安装k8s设置webhook使用尾语前言 rust-grpc-proxy 目前功能基本完善。是时候上环境开始应用了。 之前考虑是gateway模式或者sidecar模式。 思考良久之后&#xff0c;觉得两种模式都有使用场景&#xff0c;那就都支持。本次就带来sidecar模式的食…...

VisualStudio2022制作多项目模板及Vsix插件

一、安装工作负载 在vs2022上安装“visual studio扩展开发 ”工作负载 二、制作多项目模板 导出项目模板这个我就不再多说了&#xff08;项目→导出模板→选择项目模板&#xff0c;选择要导出的项目→填写模板信息→完成&#xff09;。 1.准备模板文件 将解决方案中的多个…...

仿写简单IOC

目录 TestController类: UserService类: 核心代码SpringIOC&#xff1a; Autowired和Component注解 SpringIOCTest 类 ​编辑 总结&#xff1a; TestController类: Component public class TestController {Autowiredprivate UserService userService;public void test…...

liunx下安装node exporter

1 建立文件夹 cd /opt mkdir software 下载最新的包&#xff0c;并解压 https://prometheus.io/download/ 下载 curl -LO https://github.com/prometheus/node_exporter/releases/download/v0.18.1/node_exporter-0.18.1.linux-amd64.tar.gz 3.解压 tar -xvf node_exporter-0.…...

lambda函数

Lambda(函数指针)lambda 是c11非常重要也是最常用的特性之一&#xff0c;他有以下优点&#xff1a;可以就地匿名定义目标函数或函数对象&#xff0c;不需要额外写一个函数lambda表达式是一个匿名的内联函数lambda表达式定义了一个匿名函数&#xff0c;语法如下&#xff1a;[cap…...

【Python入门第二十七天】Python 日期

Python 日期 Python 中的日期不是其自身的数据类型&#xff0c;但是我们可以导入名为 datetime 的模块&#xff0c;把日期视作日期对象进行处理。 实例 导入 datetime 模块并显示当前日期&#xff1a; import datetimex datetime.datetime.now() print(x)运行实例 2023-0…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...