二叉树层次遍历C++

二叉树的层次遍历，也称为广度优先搜索（Breadth-First Search, BFS），是一种按照从上到下、从左到右的顺序逐层遍历树节点的方法。在C++中，我们可以使用队列数据结构来实现这一过程，因为队列的特点是先进先出（FIFO），非常适合处理二叉树的层次遍历。

以下是一个简单的C++代码示例，展示了如何使用层次遍历方法遍历二叉树：

#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 levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) 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(); // 弹出队首元素
            cout << node->val << " "; // 访问节点值
            // 将子节点入队，继续下一层
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << endl; // 每层结束后换行
        q.pop(); // 出队已访问的节点
    }
}

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);

    levelOrderTraversal(root); // 输出：1 2 3 4 5

    return 0;
}