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

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

下次还敢

发布： 2025-09-30 20:40:04

原创

853人浏览过

层序遍历通过队列实现，按从上到下、从左到右顺序访问节点。首先定义TreeNode结构，包含val、left和right指针。遍历时将根节点入队，循环取出队首节点，访问其值后将其左右子节点依次入队，直至队列为空。基础版本输出节点值，进阶版本按层分组返回vector<vector<int>>，每轮记录当前层大小，用for循环处理该层所有节点，再将子节点入队。时间复杂度O(n)，空间复杂度O(w)，w为树的最大宽度。

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

二叉树的层序遍历，也叫广度优先遍历，是按照从上到下、从左到右的顺序访问树中每一层的节点。在C++中，通常借助队列（queue）来实现这一过程。

定义二叉树节点结构

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

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

登录后复制

使用队列实现层序遍历

核心思想是：将根节点入队，然后不断取出队首节点，访问其值，并将其左右子节点（如果存在）依次入队，直到队列为空。

步骤说明：

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

创建一个队列，初始时将根节点加入队列
当队列不为空时，取出队首节点
输出或处理该节点的值
将其左子节点（如存在）入队
将其右子节点（如存在）入队
重复上述过程，直到队列为空

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

#include <iostream>
#include <queue>
using namespace std;
<p>void levelOrder(TreeNode* root) {
if (!root) return;</p><pre class='brush:php;toolbar:false;'>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);
}

登录后复制

}

返回每层节点值的列表（进阶用法）

有时需要将每一层的节点值分组返回，比如返回 vector<vector<int>>。这时可以在每轮循环中记录当前层的节点数量。

vector<vector<int>> levelOrderGroup(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
<pre class='brush:php;toolbar:false;'>queue<TreeNode*> q;
q.push(root);

while (!q.empty()) {
    int levelSize = q.size();  // 当前层的节点数
    vector<int> currentLevel;

    for (int i = 0; i < levelSize; ++i) {
        TreeNode* node = q.front();
        q.pop();
        currentLevel.push_back(node->val);

        if (node->left)  q.push(node->left);
        if (node->right) q.push(node->right);
    }
    result.push_back(currentLevel);
}
return result;

登录后复制

}

基本上就这些。利用队列的先进先出特性，可以自然地实现从上到下、从左到右的访问顺序。这种方法时间复杂度为 O(n)，空间复杂度最坏为 O(w)，其中 w 是树的最大宽度。

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