Я почти уверен, что у меня есть утечка памяти в рекурсивной функции, но я не знаю, как это исправить - PullRequest
Новая
       37

Я почти уверен, что у меня есть утечка памяти в рекурсивной функции, но я не знаю, как это исправить

0 голосов
/ 06 мая 2020

Я запускаю функцию поиска в двоичном дереве, которая возвращает двоичное дерево с root возвращенного дерева, которое является поисковым запросом, например, если бы у меня было:

100 как root,

50 и 150 как его дочерние элементы,

20 и 70 и 50-е годы ---- & ---- 120 и 170 как дочерние элементы 150

, если I поставив 50 в качестве ключа к моей функции поиска, он вернет двоичное дерево с 50 в качестве root и 20 и 70 в качестве его дочерних элементов. Все это делается с помощью указателей. Моя проблема в том, что я mallo c создаю новую структуру BST (двоичное дерево поиска) каждый рекурсивный вызов и не освобождаю его, поэтому я почти уверен, что у меня утечка памяти, но я не знаю, как исправить это без освобождения памяти перед использованием. Ниже моя функция. 

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); 
}

Любые мысли были бы очень признательны. Спасибо!

1 Ответ

2 голосов
/ 06 мая 2020

Нет необходимости выделять память для функции поиска. Кажется, проблема в том, что вы передаете объект BST, тогда как вы должны передавать объект Node. 

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;
    }
}

Теперь функция вернет узел, содержащий ключ, или NULL, если не найден.

...