二叉树的层次遍历算法

article/2025/9/22 6:59:31

前面学的二叉树的遍历是把二叉树看作3个部分:根,左子树,右子树,然后我们以此来访问3个部分

而层次遍历是把树看成从上到下的若干层:根结点在第一层,根结点的孩子在第二层,根结点的孩子的孩子在第三层,然后依次类推,从上到下一层一层来访问,每一层从左到右依次访问,每个结点只访问一次

如何实现?

思路:用队列

先将根结点入队,接下来就不断从队伍中去出队一个结点,同时,如果他有左右孩子,就分别将他的左右孩子入队,这就是访问顺序:首先是根结点,然后是他的左右孩子,左右孩子后面是他的左孩子的左右孩子,右孩子的左右孩子......

例子:

将a出队的同时,将他的两个孩子b,f入队

b出队的同时将c,d入队.....

这就是层次遍历的思路:先从根节点开始,依次是他的左右孩子,到左右孩子时,再分别把左右孩子的孩子继续入队,然后再将下一层入队,一层一层入队,再按入队的顺序一个一个出队

算法:

 

用顺序循环队列。用数组data[MaxSize]来存放队中的元素,另外我们有两个指针分别表示队头和队尾

首先初始化这个队列,InitQueue(qu)

 

然后将根节点b入队qu

再从队列中出队元素,出队前判断队列是否为空!QueueEmpty

若为空,就将队头元素用出队deQueue(qu,p)

输出他的值p->data,

 

若存在左孩子,就将左孩子入队

 

若存在右孩子,就将右孩子入队

当队列中没有元素时,循环结束

用到了队列初始化,入队,判断队空,出队操作

 


http://chatgpt.dhexx.cn/article/lQgpJKU9.shtml

相关文章

二叉树各种遍历算法

二叉树是许多算法题的常用结构,其遍历算法的各种变种就是各种题目。具体的顺序如下: 先序遍历:先根、后左、再右中序遍历:先左、后根、再右后序遍历:先左、后右、再根 递归版先序、中序、后序遍历 最简单、最直接的…

带你图解二叉树的多种递归遍历(建议收藏!!)

文章目录 二叉树的构建结点类型的定义构建二叉树之间的关系 深度优先遍历前序遍历代码实现图解递归(由于图片大小问题,建议用手机客户端查看,以下图解也是) 中序遍历代码实现图解递归 后序遍历代码实现图解递归 广度优先遍历层序遍…

二叉树遍历之图解Mirror算法(莫里斯算法)

144. 二叉树的前序遍历 我们写二叉树的遍历时,一般有两种方式,迭代和递归。然而还有一种神奇的算法,也可以作我们的二叉树递归,且空间复杂度为O(1),要知道,我们迭代和递归都是需要额外栈空间的 递归和迭代网…

二叉树遍历方法——前、中、后序遍历(图解)

目录 一、前序遍历 (1)递归版本 (2)非递归版本 二、中序遍历 (1)递归版本 (2)非递归版本 三、后序遍历 (1)递归版本 (2)非递归版…

详细图解二叉树四种遍历(前序中序后序层次遍历)

文章目录 一.前序遍历常规操作简单方法 二.中序遍历常规操作简单方法 三.后序遍历常规操作 四.层次遍历常规操作 本文中以此二叉树为例 一.前序遍历 常规操作 先根,再左,再右 确定了遍历整体结构: 确定了左子树中的整体结构 继续操作&…

FPN细节剖析以及pytorch代码实现

目录 FPN(feature pyramid network) 网络结构 bottleneck pytorch代码实现 公式:卷积层输入输出大小的计算公式 细节一:代码中blocks参数的含义 细节二:c1 c2 c3 c4 c5层尺寸分别为原图的1/2 1/4 1/8 1/16 1/32…

目标检测之FPN、AugFPN、NAS-FPN

针对小目标的检测有提升的文章。 未完待续~ Feature Pyramid Networks for Object Detection FPN是一种多尺度的目标检测算法。大多数目标检测算法都是采用顶层特征来做预测的,但是我们知道:低层的特征语义信息较少,但是位置信息丰富&#x…

FPN网络和RPN网络介绍

原文链接 神经网络特征提取过程中,一般底层特征具有良好的空间信息,高层的具有良好的语义信息。原来多数的object detection算法都是只采用顶层特征做预测,但我们知道低层的特征语义信息比较少,但是目标位置准确;高层…

Neck网络 FPN + PAN 改进解读

呃 这篇文章的目的在于补充一些知识以便于理解Neck部分的网络 特征提取网络 与 目标检测之间的关系 一个特征提取网络,假设有1000层,开始的特征图包含的细节信息就很多,而随着网络的加深,特征提取网络经过多次被卷积和池化操作&…

FPN论文笔记

FPN论文笔记 现在看FPN和Inception并行结构融合有点像,FPN上采样同时横向连接相加,Inception是堆叠几个感受野不同的feature,融合的思想有点相似。 FPN是什么? Feature Pyramid Networks,用于特征抽取(feature extr…

FPN算法一览

FPN应该是2017年CV顶会的优秀论文,基于目标检测做的研究,在小物体检测方面较为具有吸引力。 1.FPN 源论文:feature pyramid networks for object detection 参考代码:FPN 同时利用低层特征高分辨率和高层特征的高语义信息&…

目标检测中的各种FPN

早期的目标检测算法,无论是一步式的,还是两步式的,通常都是在Backbone的最后一个stage(特征图分辨率相同的所有卷积层归类为一个stage)最后一层的特征图,直接外接检测头做目标检测。此种目标检测算法&#…

FPN(在FasterRCNN里面是如何运用的)

FPN(Feature Pyramid Networks) FPN解决了什么问题? 答:FPN的提出是为了实现更好的feature maps融合,一般的网络都是直接使用最后一层的feature maps,虽然最后一层的feature maps 语义强,但是位置和分辨率都比较低&…

深度学习之FPN+PAN

一、FPN 检测不同尺度的物体具有挑战性,尤其是对于小物体,我们可以使用不同尺度的同一图像的金字塔来检测物体(下左图)但是,处理多尺度图像非常耗时并且内存需求太高而无法同时进行端到端训练,因此创建了一…

FPN全解-最全最详细

这篇论文是CVPR2017年的文章,采用特征金字塔做目标检测,有许多亮点,特来分享。 论文:feature pyramid networks for object detection 论文链接:https://arxiv.org/abs/1612.03144 论文概述: 作者提出的…

FPN和PAN的内容及区别

FPN和PAN都是用于解决在目标检测中特征金字塔网络(FPN)在多尺度检测任务上的不足的方法。下面分别详细介绍一下它们的原理和区别。 FPN FPN全称Feature Pyramid Network,是由FAIR在2017年提出的一种处理多尺度问题的方法。FPN的主要思路是通过构建金字塔式的特征图…

深度学习之FPN和PAN

注:借鉴整理,仅供自学,侵删 FPN是自顶向下,将高层的强语义特征传递下来,对整个金字塔进行增强,不过只增强了语义信息,对定位信息没有传递。PAN就是针对这一点,在FPN的后面添加一个自…

FPN网络介绍

目录 前言一.FPN网络二.网络创新点 前言 上一篇博文我们介绍了FCN结构,这篇博文我们来简答的介绍下FPN网络,FPN (Feature Pyramid Network) 是一种用于图像语义分割、物体检测等任务的神经网络结构。是针对目标检测提出的结构。 一.FPN网络 先来看下FP…

FPN+PAN结构,SPP结构

一、FPNPAN FPN 高维度向低维度传递语义信息(大目标更明确) PAN 低维度向高维度再传递一次语义信息(小目标也更明确) 二、SPP 深层的feature map携带有更强的语义特征,较弱的定位信息。而浅层的feature map携带有…

FPN+PAN结构学习

yolo4的neck结构采用该模式,我们将Neck部分用立体图画出来,更直观的看下两部分之间是如何通过FPN结构融合的。 如图所示,FPN是自顶向下的,将高层特征通过上采样和低层特征做融合得到进行预测的特征图。Neck部分的立体图像&#xf…