C 中的二叉树创建

Question

我创建了一个程序来使用双链表和队列生成树，这也是在单链表的帮助下实现的。但是，我遇到了一个问题。例如，当我输入

7

时，程序只提示左右一次，然后就终止了。跟踪程序时，它应该正确获取所有输入，而不是仅在两个数字后终止。我曾多次尝试调试该程序，但此时我感到非常沮丧。您能否检查入队、出队或创建函数或全局声明中是否存在任何问题？我很感谢你的帮助。谢谢你

这是代码：

#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();
}

Answer 1

您的出列函数似乎缺乏对队列变空的情况的正确处理。

据我所知，两个全局（！）变量

f

和

r

代表链表的front和rear。

当对前面的元素进行出列时，“通常”只需要更新

f

的值。但是，有一种特殊情况，即链表仅包含单个元素。在这种情况下，您需要同时更新

f

和

r

。

因此更改

f

后检查

r

是否需要更新。也许像：

f = f->next;               // existing line
if (f == NULL) r = NULL;   // add this line