C语言二叉树创建程序异常终止问题排查求助

问题描述 #

使用单链表实现的队列构建二叉树时，输入根节点数据（如7）后，程序仅提示一次左右子节点输入就终止，无法继续接收后续节点输入。需排查入队（enQueue）、出队（deQueue）、创建（create）函数及全局声明中的问题。

原代码 #

#include <stdio.h>
#include <stdlib.h>

typedef struct tree {
    struct tree *lchild;
    int data;
    struct tree *rchild;
} tree;//create

typedef struct Queue {
    tree *data;
    struct Queue *next;
} Queue;//isEmptyQ,isFullQ,enQueue,deQueue

Queue *f = NULL;
Queue *r = NULL;
tree *root;

int isEmptyQ()
{
    return r == NULL || f == NULL;
}

int isFullQ()
{
    Queue *t = malloc(sizeof(Queue));
    return t == NULL;
}

void enQueue(tree *data)
{
    if (!isFullQ())
    {
        Queue *t = malloc(sizeof(Queue));
        t->data = data;
        t->next = NULL;  // Initialize next pointer to NULL

        if (r == NULL && f == NULL)
        {
            r = f = t;
        }
        else
        {
            r->next = t;
            r = t;
        }
    }
}

tree *deQueue()
{
    if (!isEmptyQ())
    {
        Queue *temp = f;
        tree *t = f->data;
        f = f->next;
        free(temp);
        return t;
    }
    return NULL;
}

void create()
{
    root = malloc(sizeof(tree));
    int data;
    printf("Enter the data to be entered:");
    scanf("%d", &data);
    root->data = data;
    root->lchild = root->rchild = NULL;
    enQueue(root);

    tree *p = NULL;
    while (!isEmptyQ())
    {
        p = deQueue();
        printf("Left? of %d (-1 for no left child):", p->data);
        scanf("%d", &data);
        if (data != -1)
        {
            tree *t = malloc(sizeof(tree));
            t->data = data;
            t->lchild = t->rchild = NULL;
            p->lchild = t;
            enQueue(t);
        }

        printf("Right? of %d (-1 for no right child):", p->data);
        scanf("%d", &data);
        if (data != -1)
        {
            tree *t = malloc(sizeof(tree));
            t->data = data;
            t->lchild = t->rchild = NULL;
            p->rchild = t;
            enQueue(t);
        }
    }
}

int main()
{
    create();
}

问题根源及修复方案 #

1. isEmptyQ 函数判断逻辑错误 #

原函数使用 return r == NULL || f == NULL;，当出队最后一个元素时，f 会被设为 NULL，但 r 仍指向已被释放的节点（野指针），此时函数会错误地返回 true（认为队列空），导致循环提前终止。

修复后代码：

int isEmptyQ()
{
    // 队列空的标志是头指针f为NULL（或头尾指针均为NULL）
    return f == NULL;
}

2. deQueue 函数未处理队列空的边界情况 #

当出队最后一个元素时，未将尾指针 r 置为 NULL，导致 r 成为野指针，后续判断队列状态时出错。

修复后代码：

tree *deQueue()
{
    if (!isEmptyQ())
    {
        Queue *temp = f;
        tree *t = f->data;
        f = f->next;
        // 若队列已空，同步更新尾指针r为NULL
        if (f == NULL) {
            r = NULL;
        }
        free(temp);
        return t;
    }
    return NULL;
}

3. isFullQ 函数内存泄漏 #

原函数每次调用都会malloc一个临时节点但不释放，导致内存泄漏。需在判断后释放临时节点。

修复后代码：

int isFullQ()
{
    Queue *t = malloc(sizeof(Queue));
    if (t == NULL) {
        return 1; // 内存不足，队列满
    }
    free(t); // 释放临时分配的节点
    return 0; // 内存充足，队列未满
}

修复后程序流程 #

修复后，根节点入队后，第一次出队处理左右子节点并将有效子节点入队，此时队列不为空，循环会继续执行，直到所有节点的左右子节点都处理完毕，队列彻底为空时才终止。

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