数据结构c++二叉树的层序遍历算法

在C++中，实现二叉树的层序遍历可以通过队列来辅助完成。以下是简单的层序遍历算法示例[^1]：

#include <iostream>
#include <queue>

// 定义二叉树节点
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; // 如果根节点为空，直接返回

    std::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(); // 出队
            std::cout << node->val << " "; // 访问节点值
            if (node->left != nullptr) q.push(node->left); // 左孩子入队
            if (node->right != nullptr) q.push(node->right); // 右孩子入队
        }
        std::cout << '\n'; // 每层结束后换行
    }
}

int main() {
    // 假设我们有一个已构建好的二叉树实例
    TreeNode* tree = ...; // 实际代码里应填充实际的树构造
    levelOrderTraversal(tree);
    return 0;
}

这个算法的工作原理是从根节点开始，依次放入队列。每次取出队首节点并访问其值，然后将左右子节点加入队列。这样就能保证始终按层次顺序遍历。