c - 在二叉树中查找节点时出现内存错误

Question

所以这个函数应该找到一个具有电话值的节点。问题在于内存管理。当输入值不在二叉树中时，我的函数不能很好地处理。

我的问题到底出在哪里？显然这里有一些我不明白的地方。

功能：

bst_node* find_node(bstree* bst, unsigned long phone) {

bst_node* x = bst->root;
    if(x == NULL)
        return NULL;
    if(x->phone == phone)
        return bst->root;

    while (x->phone != phone && (x->left != NULL && x->right != NULL) ){
        if(phone <= x->phone){
             x = x->left;}
        else{x = x->right;}
    }
    if (x->phone == phone){
        return x;}
    else{return NULL;} 

}

这是 Valgrind 吐出来的。找到节点时和未找到节点时。

Exiting...
==591== 
==591== HEAP SUMMARY:
==591==     in use at exit: 44 bytes in 7 blocks
==591==   total heap usage: 20 allocs, 13 frees, 7,260 bytes allocated
==591== 
==591== 44 bytes in 7 blocks are definitely lost in loss record 1 of 1
==591==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==591==    by 0x401427: bst_insert_node (introprog_telefonbuch.c:23)
==591==    by 0x400AAE: read_file (introprog_main_telefonbuch.c:54)
==591==    by 0x400D06: main (introprog_main_telefonbuch.c:119)
==591== 
==591== LEAK SUMMARY:
==591==    definitely lost: 44 bytes in 7 blocks
==591==    indirectly lost: 0 bytes in 0 blocks
==591==      possibly lost: 0 bytes in 0 blocks
==591==    still reachable: 0 bytes in 0 blocks
==591==         suppressed: 0 bytes in 0 blocks
==591== 
==591== For counts of detected and suppressed errors, rerun with: -v
==591== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

编辑：

好吧，我认为主要问题可能出在这个函数中，它应该从所选节点开始释放子树：

void bst_free_subtree(bst_node* node) {
    if(node == NULL){
        return;}
    else{
        bst_free_subtree(node->left);
        bst_free_subtree(node->right);
        free(node);
    }
}

这是在树中插入新节点的函数：

void bst_insert_node(bstree* bst, unsigned long phone, char *name) {
    if(find_node(bst, phone) != NULL){
        return;}
    // Use calloc, memset, or manually set all values to NULL
    bst_node* new_node = malloc(sizeof(bst_node));

    new_node->phone = phone;
    new_node->left = NULL;
    new_node->right = NULL;

    char *dup = malloc(strlen(name) + 1);

    if (dup != NULL)
       strcpy(dup, name);

    new_node->name = dup; 

    bst_node* y = NULL;
    bst_node* x = bst->root;

    while(x != NULL)
    {
        y = x;
        if(phone <= x->phone)
             x = x->left;
        else x = x->right;
    }
    if (y == NULL)
    {
        bst->root = new_node;
    }
    else
    {
        if (phone <= y->phone)
             y->left = new_node;
        else
            y->right = new_node;
    }
}

标签： cmemory-managementtreebinary-treebinary-search-tree