信息学奥赛 二叉树 c++ 层序遍历

在信息学奥赛中，二叉树是一个常见的数据结构。层序遍历是一种遍历二叉树的方式，它按照从上到下、从左到右的顺序逐层遍历二叉树的节点。

下面是一个使用 C++ 实现二叉树层序遍历的示例代码：

#include <iostream>
#include <queue>

using namespace std;

// 定义二叉树的节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 层序遍历函数
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    
    // 使用队列来辅助层序遍历
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        
        // 输出当前节点的值
        cout << node->val << " ";
        
        // 将当前节点的左右子节点加入队列
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
}

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->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    
    // 层序遍历二叉树
    levelOrderTraversal(root);
    
    return 0;
}

上述代码中，首先定义了二叉树的节点结构 TreeNode，其中包含一个值 val，以及左右子节点的指针 left 和 right。然后，实现了层序遍历函数 levelOrderTraversal，使用队列 q 来辅助层序遍历。

在 levelOrderTraversal 函数中，首先判断根节点是否为空，若为空则直接返回。然后，将根节点加入队列 q。之后，进入循环，每次从队列中取出一个节点，输出该节点的值，并将该节点的左右子节点加入队列。继续循环，直到队列为空，完成层序遍历。

在 main 函数中，创建了一个示例二叉树，并调用 levelOrderTraversal 函数对二叉树进行层序遍历。输出结果为按层序遍历顺序输出的节点值。