我很确定我在递归函数中有内存泄漏，但我不知道如何修复它

Question

我是运行二叉树上的搜索函数，它将 return 以 returned 树的根为搜索查询的二叉树，例如，如果我有：

100为根,

50 和 150 作为其 children,

20 和 70 和 50 的 children ----&---- 120 和 170 为 150 的 children

如果我将 50 作为我的搜索函数的键，它将 return 一个二叉树，其中 50 作为根，20 和 70 作为其 children。这都是用指针完成的。我的问题是我正在 malloc'ing 一个新的 BST（二进制搜索树）结构每个递归调用而不是释放它，所以我几乎肯定我有内存泄漏，但我不知道如何在没有 free 的情况下修复它'在使用内存之前。下面是我的函数。

typedef struct node { 
    int key; 
    struct node *left, *right; 
} Node; 

typedef struct binarySearchTree {
    Node* top;
} BST;

BST *search(BST* bst, int key) {
    // Base Cases: root is null or key is present at root 
    if (bst->top == NULL || bst->top->key == key) {
        return bst;
    }

    // Key is greater than root's key 
    if (bst->top->key < key) {
        BST *temp = malloc(sizeof(BST));
        temp->top = bst->top->right;
        return search(temp, key); 
    }

    // Key is smaller than root's key 
    BST *temp = malloc(sizeof(BST));
    temp->top = bst->top->left;
    return search(temp, key); 
}

如有任何想法，我们将不胜感激。谢谢！

Answer 1

无需为搜索功能分配内存。似乎问题是当你应该传递一个 Node 对象时，你传递了一个 BST 对象。

Node* search(Node* node, int key){ 
    if (node== NULL) return NULL;

    if (node->key < key) {
        return search(node->left, key); 
    } else if (node->key > key){
        return search(node->right, key); 
    } else {
        return node;
    }
}

现在该函数将 return 包含密钥的节点，或者 NULL 如果未找到。

我很确定我在递归函数中有内存泄漏，但我不知道如何修复它

I am pretty sure I have a memory leak in a recursive function but I don't know how to fix it

c

malloc

recursion

memory-leaks