c++中如何实现层序遍历_c++二叉树层序遍历实现-C++-PHP中文网

c++中如何实现层序遍历_c++二叉树层序遍历实现

冰火之心

发布： 2025-09-29 17:03:02

原创

693人浏览过

层序遍历通过队列实现，按从上到下、从左到右顺序访问节点。首先定义二叉树节点结构体TreeNode，包含值和左右子节点指针；然后在levelOrder函数中，利用queue存储待访问节点，根节点入队后循环出队并访问，同时将其非空左右子节点依次入队，直至队列为空。最终输出为1 2 3 4 5，完整展示了遍历过程。

c++中如何实现层序遍历_c++二叉树层序遍历实现

在C++中实现二叉树的层序遍历（也称广度优先遍历），通常使用队列（queue）来辅助完成。层序遍历按照从上到下、从左到右的顺序访问二叉树的每一个节点。

定义二叉树节点结构

首先需要定义一个二叉树节点的结构体，包含数据域和左右子树指针：

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

使用队列实现层序遍历

层序遍历的核心思想是借助队列先进先出的特性，先将根节点入队，然后循环处理队列中的节点：出队一个节点，访问它，并将其左右非空子节点依次入队。

以下是完整的C++实现代码：

立即学习“C++免费学习笔记（深入）”；

UP简历

基于AI技术的免费在线简历制作工具

128

查看详情

#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 levelOrder(TreeNode root) {
    if (!root) 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);

    cout << "层序遍历结果: ";
    levelOrder(root);
    return 0;
}

输出结果为：1 2 3 4 5

基本上就这些。使用队列可以轻松实现二叉树的层序遍历，逻辑清晰且效率高。

以上就是c++++中如何实现层序遍历_c++二叉树层序遍历实现的详细内容，更多请关注php中文网其它相关文章！