C++非递归队列实现二叉树的广度优先遍历

算法原理与逻辑

广度优先遍历（Breadth-First Search, BFS）的核心思想是“一层一层地访问”。在二叉树中，这意味着我们需要先访问根节点，然后依次访问第二层的所有节点，接着是第三层，依此类推。

为了实现这一过程，我们通常需要一个辅助的数据结构来保存待访问节点的顺序。由于BFS具有先进先出（FIFO）的特征，因此队列（Queue）是最理想的选择。其基本逻辑如下：

1. 将根节点加入队列。
2. 当队列不为空时，取出队首元素并访问（打印数据等）。
3.
3. 将该元素的左子节点和右子节点（如果存在）依次加入队列尾部。
4.
4. 重复上述步骤，直到队列为空。

C++完整实现代码

为了演示清晰，以下代码使用了C++ STL库的标准容器。在实际工程中，建议包含头文件 #include , #include , #include 和 #include (使用智能指针)。

// 定义二叉树节点结构
template<typename T>
struct TreeNode {
    T val;
    TreeNode* left;
    TreeNode* right;
    
    // 构造函数方便初始化
    TreeNode(T value) : val(value), left(nullptr), right(nullptr) {}
};

// 广度优先遍历函数
// 参数: root - 二叉树的根节点
template<typename T>
void breadthFirstSearch(TreeNode<T>* root) {
    if (root == nullptr) {
        return; // 空树直接返回
    }
    
    // 创建队列存储节点指针
    std::queue<TreeNode<T>> q;
    q.push(root); // 根节点入队
    
    while (!q.empty()) { // 只要队列不为空，就继续循环
        // 1. 获取队首元素（当前层的下一个要访问的节点）
        TreeNode<T>* current = q.front();
        q.pop(); // 弹出队首，准备处理下一轮
        
        // 2. 访问该节点（此处仅打印值作为示例）
        std::cout << current->val << " ";
        
        // 3. 将其左右子节点依次入队
        // 注意：必须先判断子节点是否为空
        if (current->left != nullptr) {
            q.push(current->left);
        }
        if (current->right != nullptr) {
            q.push(current->right);
        }
    }
    std::cout << std::endl;
}

测试用例与验证

为了验证算法的正确性，我们可以构建一个标准的完全二叉树进行测试。假设我们要构建如下结构的二叉树：

        1
       / \
      2   3
     / \
    4   5

对于这棵树的广度优先遍历，预期的输出序列应当是：1 2 3 4 5。因为它是按层从左到右输出的。

// 简单的测试主函数示例
template<typename T>
void testBFSTraversal() {
    // 构建上述示例二叉树
    TreeNode<int>* root = new TreeNode<int>(1);
    root->left = new TreeNode<int>(2);
    root->right = new TreeNode<int>(3);
    root->left->left = new TreeNode<int>(4);
    root->left->right = new TreeNode<int>(5);
    
    std::cout << "BFS Result: ";
    breadthFirstSearch(root);
    
    // 释放内存（实际项目中建议使用智能指针自动管理）
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;
}

注意事项与常见误区

• 空指针检查：在处理父节点的子节点前，务必确认父节点本身以及子节点是否存在，否则会导致段错误（Segmentation Fault）。
• 节点销毁时机：在上面的纯指针实现中，最后记得手动销毁所有动态分配的内存，避免内存泄漏。在实际开发中，推荐使用 std::unique_ptr<TreeNode> 来替代原始指针。
• 时间复杂度：每个节点进队和出队各一次，时间复杂度为 $O(N)$，其中 $N$ 为节点总数。空间复杂度取决于队列的最大宽度，最坏情况下（满二叉树的最后一层）为 $O(N/2)$，即 $O(N)$。

以上就是C++非递归队列实现二叉树的广度优先遍历的详细内容，更多关于C++二叉树遍历算法的资料请关注本站其它相关文章！