c++层次遍历二叉树

在C++中，层次遍历（也称广度优先搜索，Breadth-First Search, BFS）是一种访问二叉树节点的方法，它按照从上到下、从左到右的顺序逐层遍历。对于二叉树的层次遍历，通常会用队列数据结构来辅助操作，因为队列的特点就是先进先出（FIFO），非常适合当前层节点全部处理完再处理下一层。

以下是C++中层次遍历二叉树的基本步骤：

1. 创建一个队列，并将根节点入队。
2. 当队列非空时，循环执行以下操作：
a. 弹出队首元素。
b. 访问该节点。
c. 如果该节点有左孩子，将其入队。
d. 如果该节点有右孩子，将其入队。
3. 完成上述步骤后，所有节点都被访问过了。

下面是一个简单的C++示例，展示了如何使用递归方法来实现层次遍历：

#include <iostream>
#include <queue>

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

void levelOrder(TreeNode* root) {
    if (root == nullptr) return;

    std::queue<TreeNode*> q { root };
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            std::cout << node->val << " ";
            
            // 将左右子节点加入队列，如果存在的话
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        std::cout << "\n";
    }
}

int main() {
    // 测试代码，假设有一个已经构建好的二叉树...
    TreeNode* tree = ...;
    levelOrder(tree);
    return 0;
}