时间戳

首页 > 解决方案 > 我为使用队列的二叉搜索树的级别顺序遍历编写的 C 代码中的错误

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

问题描述

我使用队列来遍历 BST 广度优先。

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

输出： FDJBEGKACIHHHH 双重释放或损坏（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;
}

标签： cqueuebinary-search-treebreadth-first-search

解决方案

我不确定我是否 100% 理解你的代码——我已经观察了大约 20 分钟，我还没有尝试运行它——但我相信我在 dequeue(). 当您在队列中只剩下一个节点（即 front == rear）的情况下调用它时，它确实

    front = rear = ptr;

哪里ptr等于front。所以这条线正在设置 它们已经持有的值，而不是从队列中删除节点front。rear所以下次你调用dequeue()时，队列仍然包含该H 节点——即使你这样做了，你也永远不会从队列中取消它的链接 free 。

我怀疑你的意思是

    front = rear = NULL;

推荐阅读