广度优先搜索怎么遍历（广度优先搜索遍历算法）



目录

广度优先遍历（层序遍历）

一、什么是广度优先遍历（BFS）

二、为什么要广度优先遍历

三、什么时候用BFS

四、简单的BFS演示 二叉树的层序遍历

五、通过队列 和 记录层数 来进行层序遍历

广度优先搜索：

广度优先遍历（Breadth-First Search，BFS）是一种图形搜索算法，从图的某一特定顶点出发，首先访问其所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，如此一层一层地向外扩展，直到访问完所有顶点。在二叉树等数据结构中，BFS 通常按照从根节点开始，一层一层地横向遍历节点。

1. 探索图或树的结构：可以全面地了解图或树的整体结构，对于需要对整个结构进行分析的问题非常有用。
2. 寻找最短路径：在某些情况下，BFS 可以有效地找到从一个起始点到目标点的最短路径。因为 BFS 在访问每个节点时，都是先访问距离起始点最近的节点，再逐渐扩展到更远的节点。
3. 分层处理问题：对于具有层次结构的数据，如二叉树的层序遍历，可以清晰地按照层次进行处理，便于理解和分析问题。

1. 当需要找到从一个起始点到目标点的最短路径时。
2. 对图或树进行分层处理，例如二叉树的层序遍历、图的按层遍历等。
3. 当问题可以通过逐层探索来解决时，比如在迷宫问题中，找到从起点到终点的最短路径。

这个题目真的很有意义，一定要耐心看完，我觉得肯定会对你有所提升。

对于普通的层序遍历，二叉树只是队列入节点，在增加节点，但是这里又要考虑层数的控制，每层数值的比较，是思维更加跳跃灵活的体现。

一定要自己先了解题目，尝试怎么根据层序遍历，来控制层数和每一层的数的奇偶比较。

解析真的写的很详细了：

广度优先搜索：

由于判断一棵二叉树是否为奇偶树的条件是针对同一层的节点，因此可以使用广度优先搜索，每一轮搜索访问同一层的全部节点，且只会访问这一层的节点。

使用队列存储节点。初始时，将根节点加入队列。每一轮搜索之前，队列中的节点是同一层的全部节点，记队列的大小为 size，该轮搜索只访问 size 个节点，即可保证该轮搜索访问的恰好是同一层的全部节点。搜索过程中，将当前层的节点的非空子节点依次加入队列，用于下一层的搜索。

判断一棵二叉树是否为奇偶树，需要考虑两个条件，一是节点值的奇偶性，二是节点值的单调性，这两个条件都由层下标的奇偶性决定。因此，需要维护搜索到的层下标，以及对于每一层搜索都需要维护上一个节点值。

如果当前层下标是偶数，则要求当前层的所有节点的值都是奇数，且节点值从左到右严格递增。如果遇到节点值是偶数，或者当前节点值小于等于上一个节点值，则二叉树一定不是奇偶树。

如果当前层下标是奇数，则要求当前层的所有节点的值都是偶数，且节点值从左到右严格递减。如果遇到节点值是奇数，或者当前节点值大于等于上一个节点值，则二叉树一定不是奇偶树。

如果二叉树的所有节点都满足奇偶树的条件，则二叉树是奇偶树。

如果一行行读代码真的能发现 这个代码写的真的很完美，思维很跳跃，能够将控制层数 ，每一层的数字的大小比较都做得完美，当然如果多加熟练的练习，能够想上去也不是问题！

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/26794.html