当前位置: 首页> 教育> 大学 > 彻底学懂BFS广度优先遍历(最全解)

彻底学懂BFS广度优先遍历(最全解)

时间:2025/7/10 21:50:35来源:https://blog.csdn.net/2301_80636070/article/details/141875295 浏览次数:0次

目录

广度优先遍历(层序遍历)

一、什么是广度优先遍历(BFS)

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

三、什么时候用BFS

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

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

广度优先搜索:


广度优先遍历(层序遍历)

一、什么是广度优先遍历(BFS)

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

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

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

三、什么时候用BFS

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

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

#include <iostream>
#include <queue>
using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};void levelOrderTraversal(TreeNode* root) {if (root == nullptr) return;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();cout << node->val << " ";if (node->left) q.push(node->left);if (node->right) q.push(node->right);}
}

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

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

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

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

解析真的写的很详细了:

广度优先搜索:

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

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

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

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

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

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

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:queue<TreeNode*> q;bool isEvenOddTree(TreeNode* root) {q.push(root);int level=0;//根 0层while(!q.empty()){int size=q.size();int prev=level%2==0?INT_MIN:INT_MAX;//偶数层递增 奇数层递减  (同一层的上一个节点值进行比较)for(int i=0;i<size;i++){TreeNode* node=q.front();int value=q.front()->val;q.pop();if(level%2==value%2) return false; //层数跟数的奇偶相反if((level%2==0&&value<=prev)||(level%2==1&&value>=prev)) return false;prev=value;if(node->left) q.push(node->left);if(node->right) q.push(node->right);}level++;}return true;}
};

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

关键字:彻底学懂BFS广度优先遍历(最全解)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: