c - C 中的 BST 链表 : Breadth First Search

Question

我正在编写一个程序，它是二叉搜索树的链接列表。我们应该在树中搜索一个数字并打印找到的树和行号。因此，我们应该使用广度优先搜索函数。我的出队函数中出现段错误，但我不确定原因。

这些是我的结构:

typedef struct BST {
    int value;
    int treeNum;
    struct BST* left;
    struct BST* right;
}BST;

typedef struct rootList{
    struct BST* root;
    struct rootList* next;
}rootList;

typedef struct bfsQ{
    struct BST* treeNode;
    struct bfsQ* next;
}bfsQ;

这是我的 BFS 函数:

void BFS(rootList* listHead, int searchValue)
{
    if(listHead->root == NULL)
    {
        printf("%d/tNO/tN/A/tN/A\n", searchValue);
    }
    else
    {
        bfsQ* newQueue = NULL;
        BST* temp = NULL;

        newQueue = malloc(sizeof(bfsQ));
        newQueue->next = NULL;
        enqueue(&newQueue, listHead->root);
        while(newQueue != NULL)
        {
            temp = dequeue(&newQueue);
            printf("Did this work?");
            if(temp->value == searchValue)
                printf("HI I WAS FOUND");
            else
            {
                if(temp->left != NULL)
                    enqueue(&newQueue, temp->left);
                if(temp->right != NULL)
                    enqueue(&newQueue, temp->right);
            }
        }
        BFS(listHead->next, searchValue);
    }
}

这是我的队列:

void enqueue(bfsQ** qHead, BST* new_tree_node)
{
    bfsQ *temp = malloc(sizeof(bfsQ));
    BST *node;
    temp->treeNode = new_tree_node;
    temp->next = *qHead;
    *qHead = temp;
    node = temp->treeNode;
    printf("%d\n", node->value);
}

这是我的出队:

BST* dequeue(bfsQ** qHead)
{
    bfsQ *temp, *first;
    BST *newBST;
    temp = (*qHead);
    while(temp->next != NULL)
    {
        printf("THIS IS NOT NULL YET\n");
        temp = temp->next;
    }
    first = temp;
    newBST = first->treeNode;
    free(temp);
    return first->treeNode;
}

我做错了什么？入队工作正常，但是我的出队存储不正确。

编辑:显然我需要:

“该函数实现了逐级搜索的变体，或者正式地 称为广度优先搜索。 -> 该函数在二叉树中搜索给定值并执行此操作 通过在每个二叉树中搜索级别 1，然后移动到级别 2，如果 它无法在级别 1 中找到该值，依此类推。 -> 基本上，你必须在所有二叉树中搜索给定值，其中一个 一次一层，同时在链表中。”

所以我不确定是否需要搜索整棵树，然后继续，或者逐行查看每棵树。

Answer 1

从我对代码的表面观察来看，它看起来总体不错(尽管我会以不同的方式实现某些部分)，但是 dequeue() 中的最后几行肯定是错误的:

first = temp;
newBST = first->treeNode;
free(temp);
return first->treeNode;

访问最后一行中的 first->treeNode 是灾难性的:first 持有一个已经被释放的地址(temp 和 >first 指的是相同的内存位置)。我认为您想返回 newBST 相反:

return newBST; 

你不妨扔掉first，因为它看起来没什么用，然后把它变成:

newBST = temp->treeNode;
free(temp);
return newBST;