樹(shù)的廣度優(yōu)先搜索BFS就是樹(shù)的層次遍歷。

思路

使用隊(duì)列queue對(duì)遍歷的節(jié)點(diǎn)進(jìn)行存儲(chǔ)，對(duì)于入隊(duì)的節(jié)點(diǎn)，優(yōu)先遍歷其左孩子和右孩子。然后一層一層地深入下去。

1/ \2 5/ \ \ 3 4 6

BFS函數(shù)

struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(NULL),right(NULL){} };void BFS(TreeNode* root){queue<TreeNode*> Q;//隊(duì)列Q.push(root);//根節(jié)點(diǎn)入隊(duì)while(!Q.empty())//隊(duì)不空{TreeNode* node=Q.front();//隊(duì)首元素cout<<node->val<<" ";Q.pop();//處理完出隊(duì)if(node->left)//左兒子存在Q.push(node->left);if(node->right)//右兒子存在Q.push(node->right);}}

測(cè)試代碼

#include<iostream>#include<vector>#include<queue>using namespace std;struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(NULL),right(NULL){} };void BFS(TreeNode* root){queue<TreeNode*> Q;Q.push(root);while(!Q.empty()){TreeNode* node=Q.front();cout<<node->val<<" ";Q.pop();if(node->left)Q.push(node->left);if(node->right)Q.push(node->right);}}int main(){TreeNode a(1);TreeNode b(2);TreeNode c(5);TreeNode d(3);TreeNode e(4);TreeNode f(6);a.left=&b;a.right=&c;c.right=&f;b.left=&d;b.right=&e;BFS(&a);}

測(cè)試結(jié)果

希望對(duì)你有幫助。

總結(jié)

以上是生活随笔為你收集整理的二叉树的BFS代码的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。