二叉搜索树 - 插入时内存泄漏

Question

我正在尝试创建一个二叉搜索树并以迭代方式插入一个新节点。除了我在这个函数中遇到内存泄漏外，一切都运行良好。

Valgrind 说缺少 7 个块（我正在添加 7 个节点）。我看不到我的泄漏在哪里。如果再看一下我的代码，我将不胜感激。

void bst_insert_node(bstree* bst, unsigned long phone, char *name) {
    bst_node* current = bst->root;

    bst_node* parent = NULL;

    bst_node* new = (bst_node *)malloc(sizeof(bst_node));
    new->phone  = phone;
    new->left   =   new->right  =   new->parent =   NULL;
    new->name = malloc(sizeof(char) * (strlen(name)+1));
    strncpy(new->name,name,(strlen(name)+1));

    while(current != NULL) {

        parent = current;

        if(phone < current->phone) {
            current = current -> left;
        }
        else if(phone > current->phone) {
            current = current -> right;
        } else {
            free(new);
            printf("Diese Nummer ist schon bekannt \n");
            return;
        }
    }

    new->parent = parent;

    if(parent == NULL) {
        bst->root = new;
    }
    else if(new->phone < parent->phone) {
        parent->left = new;
    }
    else {
        parent->right = new;
    }
}

免费方法：

void bst_free_subtree(bst_node* node) {
if (node == NULL) return;

bst_free_subtree(node->left);
bst_free_subtree(node->right);
printf("\n Deleting node: %lu \t %s", node->phone,node->name);
free(node);}

void bst_free_tree(bstree* bst) {
    if(bst != NULL && bst->root != NULL) {
        bst_free_subtree(bst->root);
        bst->root = NULL;
    }
}

Answer 1

正如我们在评论中讨论的那样，您的内存泄漏是因为您没有释放已分配的 node->name 字符串。您需要在代码中再添加两个 free：

在bst_insert_node中，如果不能插入节点，free(new->name)在free(new)
在bst_free_subtree，free(node->name)在你free(node)

还有一个为复制的字符串分配 space 的差一错误，如您的回答所示。只用 new->name = strdup(name) 可能是最简单的，它会一次性完成分配和复制。

顺便说一句，如果这些是 phone 数字，那么 I'd probably store them as strings, not integers (or libphonenumber 如果你想全力以赴，但 C++ 而不是 C)，如果插入一个有问题，那么它可能会更好return 调用代码的错误（例如 return 如果插入则为 true，否则为 false）并让它引发错误而不是从此代码打印。

二叉搜索树 - 插入时内存泄漏

Binary Search Tree - Memory Leak at insertion

c

binary-tree

binary-search-tree