C++二叉树BFS广度优先搜索 |21xrx.com

C++二叉树BFS广度优先搜索

2023-07-13 18:43:28 深夜i -- --

C++ 二叉树 BFS 广度优先搜索

在C++中，广度优先搜索（BFS）是一种称为层序遍历的算法，它以距离根节点相等的节点为一层，逐层遍历直到所有节点都被遍历完。BFS算法可以使用于二叉树，通过遍历每个节点并检查它们的子节点，可以对每个节点的值进行处理。

二叉树BFS广度优先搜索算法的基本思想是，首先将根节点存入队列中，然后遍历队列中的所有节点，并将它们的左右子节点依次存入队列中，直到队列为空为止，此时就遍历完了整棵二叉树。由于BFS算法遍历的顺序是按照节点的层级进行的，因此可以保证每个节点都被遍历且只被遍历一次。

在C++中实现该算法，需要定义一个二叉树的节点结构体，包含节点的值、左右子节点的指针等信息。同时，需要定义一个队列，用于存储节点，实现遍历广度优先搜索。

以下是C++中二叉树BFS广度优先搜索算法的示例代码。


#include<iostream>
#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){
  if(!root) return;
  queue<TreeNode*> q;
  q.push(root);
  while(!q.empty()){
    int size = q.size();
    for(int i=0;i<size;i++){
      TreeNode *node = q.front();
      q.pop();
      cout<<node->val<<" ";
      if(node->left) q.push(node->left);
      if(node->right) q.push(node->right);
    }
    cout<<endl;
  }
}
int main(){
  TreeNode* root=new TreeNode(1);
  root->left=new TreeNode(2);
  root->right=new TreeNode(3);
  root->left->left=new TreeNode(4);
  root->left->right=new TreeNode(5);
  root->right->left=new TreeNode(6);
  root->right->right=new TreeNode(7);
  cout<<"Binary Tree BFS:"<<endl;
  BFS(root);
  return 0;
}

在上述代码中，我们定义了一个名为BFS的函数，该函数实现了二叉树BFS广度优先搜索算法。函数中使用了一个队列q，首先将根节点push入队，然后使用while循环依次遍历队列中的节点，同时将每个节点的左右子节点依次push入队，直到队列为空为止。

我们在主函数中构造了一个二叉树，以测试该算法是否正确。运行程序后，输出如下：

Binary Tree BFS: 1 2 3 4 5 6 7

可以看到，该算法按照层级遍历了整棵二叉树，并输出了节点的值。通过这种方式，我们可以快速有效地遍历并处理二叉树中的每个节点。

上一篇: idea打包java可执行jar包

下一篇: 使用C++编写三角形面积计算对话框

评论区

()

相似文章