我为使用队列的二叉搜索树的级别顺序遍历编写的 C 代码出错

Question

我已经使用队列广度优先遍历了 BST。

代码编译运行。我也得到正确答案。但是，对于最后一个节点，字符会重复 4 次，然后会出现一条错误消息。错误消息意味着我使用无效指针调用了 free()。我无法调试此问题，如有任何帮助，我们将不胜感激。

输出： F D J B E G K A C I H H H H double free or corruption (fasttop) 中止

//bfs - level order traversal - USING QUEUE

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

struct bstnode {
    char data;
    struct bstnode *left;
    struct bstnode *right;
};

struct bstnode *front = NULL;
struct bstnode *rear = NULL;

struct bstnode *newnode (char d);
struct bstnode *insert (struct bstnode *root, char d);
void bfs (struct bstnode *root);
void enqueue (struct bstnode *root);
struct bstnode *dequeue();

int main (void) {
    struct bstnode *root = NULL;

    root = insert (root, 'F');
    root = insert (root, 'D');
    root = insert (root, 'B');
    root = insert (root, 'A');
    root = insert (root, 'E');
    root = insert (root, 'C');
    root = insert (root, 'J');
    root = insert (root, 'K');
    root = insert (root, 'G');
    root = insert (root, 'I');
    root = insert (root, 'H');

    bfs(root);
}

//create node
struct bstnode *newnode (char d) {
    struct bstnode *newnode = (struct bstnode *)malloc(sizeof(struct bstnode));
    newnode->data = d;
    newnode->left = newnode->right = NULL;
    return newnode;
}

//insert in bst
struct bstnode *insert (struct bstnode *root, char d) {
    if (root == NULL) {
        root = newnode(d);
    }
    else if (d <= root->data) {
        root->left = insert (root->left, d);
    }
    else {
        root->right = insert (root->right, d);
    }
    return root;
}

//level order traversal using queue
void bfs (struct bstnode *root) {
    struct bstnode *current = root;

    while (current != NULL) {
        printf("%c ", current->data);

        if (current->left != NULL) {
            enqueue(current->left);
        }
        if (current->right != NULL) {
            enqueue(current->right);
        }
        current = dequeue();  //remove char at front
    }
}

//enqueue children
void enqueue (struct bstnode *root) {
    struct bstnode *current = (struct bstnode *)malloc(sizeof(struct bstnode));
    current->data = root->data;
    current->left = root;
    current->right = NULL;

    if (front == NULL && rear == NULL) {
        front = rear = current;
        return;
    }
    rear->right = current;
    rear = current;
}

//pop element at front
struct bstnode *dequeue() {
    struct bstnode *ptr = front;

    if (front == NULL) {
        printf("there is no queue\n");
    }
    if (front == rear) {
        front = rear = ptr;
    } else {
        front = front->right;
    }

    struct bstnode *next = ptr->left;
    free(ptr);
    return next;
}

Answer 1

我不确定我是否 100% 理解您的代码 — 我刚刚盯着它看了大约 20 分钟，而且我还没有尝试运行它 — 但我认为我在 dequeue() 中看到了问题。当您在队列中只剩下一个节点时调用它（即 front == rear），确实如此

    front = rear = ptr;

其中 ptr 等于 front。所以这一行设置 front 和 rear 他们已经持有的价值观，而不是从队列中删除节点。所以下次你打电话给 dequeue() 时，队列仍然包含 H 节点 — 并且您永远不会取消它与队列的链接，即使您这样做了free。

我怀疑你是故意的

    front = rear = NULL;

我为使用队列的二叉搜索树的级别顺序遍历编写的 C 代码出错

Error in C code I wrote for level order traversal of a Binary Search Tree using queue

c

queue

breadth-first-search

binary-search-tree