编写算法实现 对二叉树的层序遍历c++

在C++中，实现二叉树的层序遍历通常使用队列数据结构，因为层序遍历需要按照从上到下、从左到右的顺序逐层访问节点。下面是一个简单的层次遍历算法的步骤：

1. 定义一个辅助函数`void levelOrderUtil(Node* root, vector<int>& result, queue<Node*> &q)`：
- 用于实际的层次遍历操作
- 参数root指向根节点，result存储遍历结果，q是一个队列，用于存放待处理的节点

2. 主函数`vector<int> levelOrderTraversal(TreeNode* root)`：
- 初始化空的结果数组和一个空的队列
- 如果根节点存在，则将根节点入队并开始遍历
- 当队列非空时，循环执行以下步骤：
a. 弹出队首元素，将其值添加到结果数组中
b. 将该元素的左右子节点（如果存在）入队
- 遍历结束后返回结果数组

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 假设 TreeNode 是一个包含整数值和两个指针（分别指向左子节点和右子节点）的结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 辅助函数，层序遍历的核心实现
void levelOrderUtil(TreeNode* root, vector<int>& result, queue<TreeNode*>& q) {
    if (root == nullptr) return;
    q.push(root);
    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        result.push_back(curr->val);

        // 将当前节点的左右子节点加入队列
        if (curr->left != nullptr) q.push(curr->left);
        if (curr->right != nullptr) q.push(curr->right);
    }
}

// 主函数，返回二叉树的层序遍历结果
vector<int> levelOrderTraversal(TreeNode* root) {
    vector<int> result;
    queue<TreeNode*> q;
    levelOrderUtil(root, result, q);
    return result;
}

int main() {
    // 示例：创建一个二叉树并测试层序遍历
    TreeNode* tree = new TreeNode(1);
    tree->left = new TreeNode(2);
    tree->right = new TreeNode(3);
    tree->left->left = new TreeNode(4);
    tree->left->right = new TreeNode(5);

    vector<int> result = levelOrderTraversal(tree);
    for (int i : result) {
        cout << i << " ";
    }

    return 0;
}

当你运行这个程序时，它会按照层序打印出二叉树的所有节点值。