这段广度优先搜索（BFS）代码能否正常处理所有二叉树？

存在的核心问题 #

这段代码在测试的完全二叉树上能输出正确结果，但无法兼容所有二叉树场景，存在多个严重问题：

• 空树、单节点树会崩溃：如果传入空树（root=NULL），main函数中会把NULL推入队列，后续调用print虽直接返回，但队列中的NULL未处理；如果是单节点树，打印完根节点后队列变为空，此时调用print(q.front())会访问空队列的首元素，触发未定义行为（通常是程序崩溃）。
• 递归实现BFS的设计错误：BFS本质是迭代算法，依赖队列循环处理。用递归实现会导致递归深度等于树的节点数，当树的节点数量较多（比如上万级）时，会触发栈溢出，直接崩溃。
• 全局队列的不可重入问题：队列q是全局变量，若多次调用print函数，前一次的队列残留数据会干扰后续执行，函数无法独立复用。
• 内存泄漏：代码中用calloc创建了大量节点，但没有任何释放逻辑，长期运行会耗尽系统内存。

改进建议：标准迭代式BFS实现 #

以下是修复所有问题后的代码，采用BFS标准的迭代实现：

#include <stdlib.h>
#include <stdio.h>
#include <queue>
using namespace std;

struct Node{
    int data;
    struct Node *left;
    struct Node *right;
};

Node* newNode(int data){
    Node* new_node = (Node*)calloc(1, sizeof(Node));
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return new_node;
}

// 迭代实现BFS，队列作为局部变量，支持所有二叉树场景
void bfsPrint(Node *root){
    if(root == NULL){
        printf("空树\n");
        return;
    }
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
        Node* current = q.front();
        q.pop();
        printf("%d ", current->data);
        // 先入队左孩子，再入队右孩子，保证层序遍历顺序
        if(current->left != NULL){
            q.push(current->left);
        }
        if(current->right != NULL){
            q.push(current->right);
        }
    }
}

// 递归释放二叉树所有节点，避免内存泄漏
void freeTree(Node* root){
    if(root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main(){
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(11);
    root->right->left->left = newNode(12);
    root->right->left->right = newNode(13);
    root->right->right->left = newNode(14);
    root->right->right->right = newNode(15);

    bfsPrint(root);
    printf("\n");

    // 释放所有节点内存
    freeTree(root);
    return 0;
}

改进点说明 #

1. 迭代逻辑：用while循环处理队列，完全符合BFS的层序遍历逻辑，避免递归栈溢出问题，支持任意规模的二叉树。
2. 局部队列：每次调用bfsPrint都创建独立的局部队列，函数可重复调用，无数据干扰。
3. 边界场景兼容：直接处理空树，单节点树也能正常输出，不会触发崩溃。
4. 内存管理：新增freeTree函数，递归释放所有节点内存，解决内存泄漏问题。

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