C++实现二叉树层序遍历（小白也能学会的广度优先搜索BFS算法详解）

什么是层序遍历？

层序遍历（Level Order Traversal）是指从二叉树的根节点开始，逐层从左到右访问所有节点。例如，对于如下二叉树：

        1       / \      2   3     / \   \    4   5   6

其层序遍历结果为：[1, 2, 3, 4, 5, 6]。

为什么使用队列？

层序遍历的核心思想是先进先出（FIFO），这正好符合队列（queue）的数据结构特性。我们从根节点开始，将其入队；然后每次从队首取出一个节点，访问它，并将其左右子节点（如果存在）依次入队。如此循环，直到队列为空。

C++实现步骤详解

下面我们将用C++标准库中的queue容器来实现层序遍历。

1. 定义二叉树节点结构

struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};

2. 实现层序遍历函数

我们将编写一个函数 levelOrder，它接收根节点指针，返回一个二维向量（每层一个子向量），也可以简化为一维向量。这里我们展示二维版本，便于理解层级结构。

#include <iostream>#include <vector>#include <queue>using namespace std;vector<vector<int>> levelOrder(TreeNode* root) {    vector<vector<int>> result;    if (!root) return result; // 空树直接返回    queue<TreeNode*> q;    q.push(root);    while (!q.empty()) {        int levelSize = q.size(); // 当前层的节点数量        vector<int> currentLevel;        for (int i = 0; i < levelSize; ++i) {            TreeNode* node = q.front();            q.pop();            currentLevel.push_back(node->val);            if (node->left) q.push(node->left);            if (node->right) q.push(node->right);        }        result.push_back(currentLevel);    }    return result;}

3. 完整可运行示例

#include <iostream>#include <vector>#include <queue>using namespace std;struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};vector<vector<int>> levelOrder(TreeNode* root) {    vector<vector<int>> result;    if (!root) return result;    queue<TreeNode*> q;    q.push(root);    while (!q.empty()) {        int levelSize = q.size();        vector<int> currentLevel;        for (int i = 0; i < levelSize; ++i) {            TreeNode* node = q.front();            q.pop();            currentLevel.push_back(node->val);            if (node->left) q.push(node->left);            if (node->right) q.push(node->right);        }        result.push_back(currentLevel);    }    return result;}// 测试函数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->right = new TreeNode(6);    vector<vector<int>> res = levelOrder(root);    cout << "层序遍历结果：\n";    for (const auto& level : res) {        for (int val : level) {            cout << val << " ";        }        cout << endl;    }    // 输出：    // 1     // 2 3     // 4 5 6    return 0;}

常见问题与优化

• Q：能否只输出一维数组？
  A：当然可以！只需将 currentLevel 中的元素直接 push 到一维 result 向量即可。
• Q：空间复杂度高吗？
  A：最坏情况下（完全二叉树最后一层），队列会存储 O(n/2) 个节点，空间复杂度为 O(n)。
• Q：时间复杂度是多少？
  A：每个节点入队出队一次，时间复杂度为 O(n)，n 为节点总数。

总结

通过本教程，你已经掌握了如何用C++实现二叉树的层序遍历。这项技术广泛应用于树形结构处理、图的BFS、序列化/反序列化等场景。记住，队列是实现BFS的关键，而层序遍历正是BFS在树结构中的典型应用。

无论你是准备面试，还是学习算法，掌握C++层序遍历、二叉树层序遍历、C++ BFS算法和广度优先搜索C++实现都至关重要。多加练习，你一定能熟练运用！