基于队列的二叉树层序遍历陷入无限循环问题排查

嗨，我帮你找出了代码里导致无限循环和逻辑错误的几个关键点，咱们一步步来修正：

1. 队列实现完全搞反了（栈 vs 队列） #

你现在的enqueue和dequeue实现的是栈（后进先出），而层序遍历需要的是队列（先进先出）——这是导致无限循环的核心原因：

• enqueue里你把新节点插到队列头部（temp->next = back; back = temp;），这是栈的push操作，不是队列的尾插法
• dequeue里你从头部删除节点（操作back指针），这也是栈的pop逻辑，完全不符合队列“先进先出”的要求
• 这种错误的队列逻辑会让节点永远无法按层序顺序处理，要么重复入队要么无法出队，最终触发无限循环

正确的队列应该用尾插法：新节点加到队列尾部，从头部（front）删除节点。

2. level_order里的子节点入队逻辑完全写反 #

你这段代码的判断条件和入队节点完全不匹配：

if(current->right != NULL){
  enqueue(&(current->left));
}
if(current->left != NULL){
  enqueue(&(current->right));
}

应该是左子节点存在就入队左节点，右子节点存在就入队右节点，判断条件和入队对象要对应上。

3. first_element函数逻辑错误 #

因为队列的front和back指针逻辑搞反了，你现在的front实际上永远指向队列的最后一个节点，导致first_element返回的不是队首元素，每次处理的节点都不对，进一步加剧了循环问题。

4. 类型定义的小问题 #

标准C里使用自定义结构体时，部分函数里的BstNode前面没加struct（比如create_queue的参数），虽然部分编译器兼容，但会产生警告，最好规范写法。另外别忘了引入<stdbool.h>头文件，否则bool类型无法被识别。

修正后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // 引入bool类型的头文件

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

struct Queue{
    struct BstNode *address;
    struct Queue *next;
};

struct Queue *front = NULL;
struct Queue *back = NULL;

// 修正结构体类型声明
struct Queue* create_queue(struct BstNode **address){
    struct Queue *temp = (struct Queue*)malloc(sizeof(struct Queue));
    temp->next = NULL;
    temp->address = *address;
    return temp;
}

// 修正enqueue：尾插法实现队列入队
void enqueue(struct BstNode **address){
    struct Queue *temp = create_queue(address);
    if(front == NULL && back == NULL){
        front = back = temp;
    } else{
        back->next = temp; // 新节点加到队列尾部
        back = temp;       // 更新back指针到新节点
    }
}

// 修正dequeue：从队首（front）删除节点
void dequeue(){
    if(front == NULL){
        return;
    }
    struct Queue* temp = front; // 要删除的是队首节点
    if(front == back){
        front = back = NULL;
    } else{
        front = front->next; // front指针移动到下一个节点
    }
    free(temp);
}

// 简化empty函数写法
bool empty(){
    return front == NULL;
}

// 修正print_queue：从队首开始遍历
void print_queue(){
    struct Queue *temp = front;
    while(temp != NULL){
        printf("%d ", temp->address->data);
        temp = temp->next;
    }
    printf("\n");
}

struct BstNode *root;

// 修正结构体类型声明
struct BstNode *create_node(int data){
    struct BstNode *temp = (struct BstNode *)malloc(sizeof(struct BstNode));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

// 修正结构体类型声明
void insert_bst_cell(struct BstNode **node, int data){
    if((*node) == NULL){
        struct BstNode* temp = create_node(data);
        *node = temp;
    } else if(data > (*node)->data){
        insert_bst_cell(&(*node)->right, data);
    } else if(data < (*node)->data){
        insert_bst_cell(&(*node)->left, data);
    }
}

// 修正first_element：返回队首节点的地址
struct BstNode *first_element(){
    return front->address;
}

// 修正level_order的子节点入队逻辑
void level_order(){
    if(root == NULL) return;
    enqueue(&root);
    while(!empty()){
        struct BstNode *current = first_element();
        dequeue();
        printf("%d ", current->data);
        // 左子节点优先入队，符合层序遍历从左到右的顺序
        if(current->left != NULL){
            enqueue(&(current->left));
        }
        if(current->right != NULL){
            enqueue(&(current->right));
        }
    }
}

int main(int argc, char **argv) {
    front = NULL;
    back = NULL;
    root = NULL;
    insert_bst_cell(&root, 15);
    insert_bst_cell(&root, 10);
    insert_bst_cell(&root, 20);
    insert_bst_cell(&root, 5);
    insert_bst_cell(&root, 11);
    insert_bst_cell(&root, 17);
    insert_bst_cell(&root, 25);
    insert_bst_cell(&root, 4);
    insert_bst_cell(&root, 6);
    insert_bst_cell(&root, 9);
    insert_bst_cell(&root, 12);
    insert_bst_cell(&root, 16);
    insert_bst_cell(&root, 19);
    insert_bst_cell(&root, 21);
    insert_bst_cell(&root, 35);
    level_order();
    return 0;
}

修正后的运行结果 #

运行后会输出正确的层序遍历结果：
15 10 20 5 11 17 25 4 6 12 16 19 21 35 9

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