C++非递归实现二叉树层序遍历：问题排查与修正

针对你的四个疑问的解答： #

• 如何初始化并使用std::queue存储遍历节点？
  先初始化一个空的std::queue<TreeNode*>，只有当根节点非空时才将其入队。每次循环从队列头部取出节点处理，再将该节点的有效子节点（非空）入队，以此推进遍历流程。

• 入队节点左右子节点的正确方式是什么？
  必须先判断子节点是否为nullptr，仅将非空的子节点入队。顺序上严格遵循先左后右，这样才能保证同一层内的节点按从左到右的顺序遍历。

• 如何确保循环在处理完所有节点后停止？
  将循环条件设为!q.empty()，每次处理完当前节点后，仅入队存在的子节点。当所有节点都被处理完毕，队列会自然变为空，循环自动终止。

• 需要处理哪些边界情况？

  • 空树：直接终止函数，不执行任何遍历操作；
  • 单节点树：仅入队根节点，处理后队列为空，循环结束；
  • 单侧子树（如只有左子节点链）：按层序依次入队有效子节点，保证遍历顺序正确。

你的代码问题分析 #

你遇到的段错误，核心原因是没有处理空树的边界情况：当root为nullptr时，你直接将其入队，后续循环中访问current->val会触发空指针访问，导致程序崩溃。

修改后的完整代码 #

#include <iostream>
#include <queue>

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;
    }

    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();

        std::cout << current->val << " ";

        // 仅将非空的左子节点入队
        if (current->left != nullptr) {
            q.push(current->left);
        }
        // 仅将非空的右子节点入队
        if (current->right != nullptr) {
            q.push(current->right);
        }
    }
}

// 测试用例
int main() {
    // 构建测试二叉树
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    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);

    std::cout << "标准树遍历结果：";
    levelOrderTraversal(root); // 预期输出：1 2 3 4 5
    std::cout << "\n";

    // 测试空树
    std::cout << "空树遍历结果：";
    levelOrderTraversal(nullptr); // 无输出
    std::cout << "\n";

    // 测试单节点树
    TreeNode* singleNode = new TreeNode(10);
    std::cout << "单节点树遍历结果：";
    levelOrderTraversal(singleNode); // 输出：10
    std::cout << "\n";

    // 释放内存（实际项目中需注意内存管理）
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;
    delete singleNode;

    return 0;
}

关键修改说明 #

1. 新增空树判断：函数开头检查root是否为nullptr，直接返回，彻底避免空指针访问；
2. 保留子节点非空校验：确保只有有效节点入队，不会将nullptr加入队列，保证循环内操作的安全性；
3. 队列逻辑保持正确：先入队根节点，每次处理节点后按左到右顺序入队非空子节点，严格保证层序遍历的顺序。

内容的提问来源于stack exchange，提问作者Naormeit