使用Valgrind遇到麻烦，并且实现了BST的min函数

Question

我实现了具有四个功能的bst，分别是add，inorderPrint，min和max。最小值和最大值应返回树中的最小/最大值，并删除该节点。允许树不平衡。下面是我的节点struct，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;