在 Valgrind 和 BST 的 min 函数实现方面遇到问题

Question

我实现了一个包含四个函数的 bst，add、inorderPrint、min 和 max。最小值和最大值应该 return 树中的 smallest/greatest 值，并且还删除该节点。允许树不平衡。下面是我的节点结构的实现，add函数，min函数，还有valgrind报错。

Valgrind 错误如下：

==2768== Invalid read of size 8
==2768==    at 0x108C13: removeSmallest (bst.c:43)
==2768==    by 0x108BDC: removeSmallest (bst.c:39)
==2768==    by 0x108945: main (problem2.c:25)
==2768==  Address 0x522d8a8 is 8 bytes inside a block of size 24 free'd
==2768==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2768==    by 0x108C0B: removeSmallest (bst.c:42)
==2768==    by 0x108BDC: removeSmallest (bst.c:39)
==2768==    by 0x108945: main (problem2.c:25)
==2768==  Block was alloc'd at
==2768==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2768==    by 0x108A99: add (bst.c:9)
==2768==    by 0x108B08: add (bst.c:15)
==2768==    by 0x108918: main (problem2.c:21)
==2768==

第 43 行是 (*root) = (*root)->right;

第 39 行是 return removeSmallest((&(*root)->left));

第 42 行是 free(*root);

第 9 行是 (*root) = (bst_node *)malloc(sizeof(bst_node));

第 15 行是 add(&((*root)->left), word);

这是名为 bst.h

的单独文件中的节点结构

typedef struct  bst_node {
    char * data;
    struct bst_node * right;
    struct bst_node * left;
} bst_node ;

这是实现的功能的文件。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bst.h"


void add ( bst_node ** root, char * word ) {
if ((*root) == NULL) {
    (*root) = (bst_node *)malloc(sizeof(bst_node));
    (*root)->data = word;
    (*root)->left = NULL;
    (*root)->right = NULL;
} else {
    if (strcmp(word, (*root)->data) < 0) {
        add(&((*root)->left), word);
    } else if (strcmp(word, (*root)->data) > 0) {
        add(&((*root)->right), word);
    }
}
}

void inorder ( bst_node * root ) {

if(root == NULL) {
    return;
}
inorder(root->left);
printf("  %s", root->data);
inorder(root->right);
}

char * removeSmallest (  bst_node ** root ){
char * answer;

if (*root == NULL) {
    return NULL;
} else {
    if ((*root)->left != NULL) {
        return removeSmallest((&(*root)->left));
    } else if ((*root)->right != NULL) {
        answer = (*root)->data;
        free(*root);
        (*root) = (*root)->right;
        return answer;

    } else {
        answer = (*root)->data;
        free((*root));
        *root = NULL;
        return answer;
    }
}
}

Answer 1

您正在尝试使用释放的指针：

free(*root); (*root) = (*root)->right;

我觉得应该是

bst_node * new_root = (*root)->right; free(*root); (*root) = new_root;

在 Valgrind 和 BST 的 min 函数实现方面遇到问题

Having trouble with Valgrind and implementation of min function for BST

c

valgrind

min

binary-search-tree