C语言基于队列实现二叉树层序遍历的代码问题排查

根因定位 #

• enqueue函数打印逻辑错误：你在enqueue中打印的是入队前的旧节点值，而非本次新插入的节点值。第一次入队时打印新节点值正常，后续入队时先打印旧tail节点值再更新tail指针，就会出现旧值重复打印、最后一个入队节点漏打的问题。
• 层序遍历逻辑不符合算法要求：你没有按照题目给出的「出队→打印→子节点入队」流程实现，而是直接遍历队列链表插入子节点，遍历完成后head指针已经移动到NULL，后续调用dequeue自然无法取出任何节点。
• dequeue函数缺少边界判断：队列为空时调用dequeue会直接访问空指针触发段错误，且弹出队列节点后没有释放对应的内存，存在内存泄漏问题。

修复代码 #

1. 修复enqueue函数 #

void enqueue(struct queueNode** head, struct queueNode** tail, struct treeNode* tree){
    struct queueNode* newNode = (struct queueNode*)malloc(sizeof(struct queueNode));
    if( newNode ){
        newNode -> tree = tree;
        newNode -> next = NULL;
        if(!(*head)){
            *head = newNode;
        } else {
            (*tail) -> next = newNode;
        }
        (*tail) = newNode;
    } else {
        printf("%s\n", "[ERROR] 内存不足，分配失败！");
    }
}

2. 修复dequeue函数 #

struct treeNode* dequeue(struct queueNode** head, struct queueNode** tail){
    if(*head == NULL) return NULL; // 新增空队列判空逻辑
    struct treeNode* val = (*head)->tree;
    struct queueNode* temp = *head;
    *head = (*head) -> next;
    if(!(*head))
        *tail = NULL;
    free(temp); // 释放弹出的队列节点内存，避免泄漏
    return val;
}

3. 修复levelOrder遍历逻辑 #

void levelOrder(struct treeNode** root){
    struct treeNode* output = NULL;
    struct queueNode* head = NULL, *tail = NULL;
    size_t i;
    srand(time(NULL));
    for(i = 0; i < 9; ++i){
        insert(root, 1 + rand()%16);
    }
    puts("中序遍历结果");
    inOrder(*root);
    puts("NULL");
    puts("中序遍历结束");
    
    // 严格按照题目给的层序遍历步骤实现
    puts("层序遍历结果");
    enqueue(&head, &tail, *root);
    while(head != NULL){
        // 1. 取出队列下一个节点
        output = dequeue(&head, &tail);
        // 2. 打印节点值
        printf("%d --> ", output->data);
        // 3. 左右子节点非空则入队
        if(output->left != NULL)
            enqueue(&head, &tail, output->left);
        if(output->right != NULL)
            enqueue(&head, &tail, output->right);
    }
    puts("NULL");
}

验证方法 #

运行修改后的代码，对比中序遍历和层序遍历的结果：二叉搜索树的中序遍历会输出升序序列，层序遍历会按层级从左到右输出所有节点，两者节点总数完全一致即可确认逻辑正确。

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