Освобождение связанных структур в C

Question

Хорошо, у меня есть Бинарное дерево поиска, построенное с использованием только структур и указателей C, потому что я безумен и не хочу использовать C ++. В любом случае, у меня есть некоторые серьезные утечки памяти, так как я , предполагая free(tree), дерево, являющееся экземпляром структуры ниже, не освобождает всех потомков этого дерева. .

Вот мой узел:

struct node{
    struct node* parent;
    struct node* left;
    struct node* right;
    int key; //the value of the node
};

и вот мой bst:

struct bst{
    struct node* root;
    int elements; //number of nodes in the bst
};

Так что мой вопрос, есть ли лучший способ сделать это, чем рекурсивный вызов функции удаления? например (написать это на месте):

void delete_tree(struct node* n){
    if(n == NULL) return;
    struct node* left = n->left;
    struct node* right = n->right;
    free(n);
    delete_tree(left);
    delete_tree(right);
}

Answer 1

Я не вижу абсолютно ничего плохого в рекурсивном удалении. Вы можете использовать итеративный подход, но он не будет иметь каких-либо заметных преимуществ и будет труднее написать.

Кстати, вы можете немного упростить код и удалить две локальные переменные так:

void delete_tree(struct node* n){
    if(n == NULL) return;
    delete_tree(n->left);
    delete_tree(n->right);
    free(n);
}

Answer 2

Вы делаете рекурсивные вызовы, но на самом деле никогда не звоните free.Вам, вероятно, нужно проверить, является ли узел листовым узлом (возможно, спрашивая, являются ли оба дочерних элемента нулевыми) и вызвать free на этом узле.