Как освободить память, занятую деревом, C?

Question

я в настоящее время имеет дело с родовым Деревом с этой структурой:

typedef struct NODE { 

    //node's keys 
    unsigned short *transboard; 
    int depth; 
    unsigned int i; 
    unsigned int j; 
    int player; 
    int value; 


    struct NODE *leftchild; //points to the first child from the left 
    struct NODE *rightbrothers; //linked list of brothers from the current node 

}NODE; 

static NODE *GameTree = NULL; 

В то время как функция, которая выделяет различные узлы есть (не беспокойтесь слишком много значений клавиши, в основном выделяют ребенок-узлы . Если нет какой-либо новый ребенок идет в LeftChild, в противном случае он идет в конце списка «node-> leftchild-> rightbrothers»):

static int AllocateChildren(NODE **T, int depth, unsigned int i, unsigned int j, int player, unsigned short *transboard) { 
NODE *tmp = NULL; 

if ((*T)->leftchild == NULL) { 
    if( (tmp = (NODE*)malloc(sizeof(NODE)) )== NULL) return 0; 
    else { 
     tmp->i = i; 
     tmp->j = j; 
     tmp->depth = depth; 
     (player == MAX) ? (tmp->value = 2): (tmp->value = -2); 
     tmp->player = player; 
     tmp->transboard = transboard; 

     tmp->leftchild = NULL; 
     tmp->rightbrothers = NULL; 

     (*T)->leftchild = tmp; 
    } 
} 

else { 
    NODE *scorri = (*T)->leftchild; 
    while (scorri->rightbrothers != NULL) 
     scorri = scorri->rightbrothers; 

    if((tmp = (NODE*)malloc(sizeof(NODE)))== NULL) return 0; 
    else { 
     tmp->i = i; 
     tmp->j = j; 
     tmp->depth = depth; 
     (player == MAX) ? (tmp->value = 2) : (tmp->value = -2); 
     tmp->player = player; 
     tmp->transboard = transboard; 

     tmp->leftchild = NULL; 
     tmp->rightbrothers = NULL; 
    } 
    scorri->rightbrothers = tmp; 


} 

return 1; 

} 

мне нужно придумать функцию, возможно рекурсивный, который отменяет все дерево, до сих пор я придумал это:

void DeleteTree(NODE **T) { 

if((*T) != NULL) { 
    NODE *tmp; 
    for(tmp = (*T)->children; tmp->brother != NULL; tmp = tmp->brother) { 
     DeleteTree(&tmp); 
    } 

    free(*T); 

} 
} 

Но он не работает, он даже не освобождает один узел памяти. Любые идеи о том, где я ошибаюсь или как это можно реализовать? P.s. Я получил идею рекурсивной функции от этого псевдокода от моего учителя. Однако я не уверен, что правильно перевел его на C с помощью своего дерева. псевдокод:

1: function DeleteTree(T) 
2: if T != NULL then 
3:  for c ∈ Children(T) do 
4:   DeleteTree(c) 
5:  end for 
6:  Delete(T) 
7: end if 
8: end function 

Answer 1

Я только что осознал свою БОЛЬШУЮ ошибку в коде, и я просто отвечу на вопрос, так как никто не нашел ответа.

Ошибка заключается в этой части кода:

for(tmp = (*T)->children; tmp->brother != NULL; tmp = tmp->brother) { 
    DeleteTree(&tmp); 
} 

Прежде всего Ами Tavory был прав насчет для условия, я должен продолжаться до тех пор, пока TMP = NULL В принципе это будет не просто потому что после DeleteTree (& tmp) я больше не могу получить доступ к памяти в tmp, потому что явно удален, поэтому после первого цикла для концов я не могу сделать tmp = tmp-> rightbrother, чтобы перейти к следующему удалять узел, потому что tmp-> rightbrother больше не существует, поскольку я просто удалил его. Для того, чтобы исправить это, мне просто нужно, чтобы сохранить tmp-> брат где-то еще:

void DeleteTree(NODE **T) { 

    if((*T) != NULL) { 
     NODE *tmp, *deletenode, *nextbrother; 

     for(tmp = (*T)->children; tmp != NULL; tmp = nextbrother) { 
      nextbrother = tmp->rightbrother; 
      DeleteTree(&tmp); 

     } 

    canc = (*T); 
    free(*T); 
    (*T) = NULL; 
    } 

} 

Answer 2

Одна вещь, которую я люблю делать, если я выделить множество узлов дерева, которые собираются уходить в то же время, чтобы выделить их в «партиях». I malloc, затем в виде массива узлов и выводит их из специальной функции nodealloc после сохранения указателя на массив (в функции, как показано ниже). Чтобы отбросить дерево, я просто удостоверяюсь, что не поддерживаю никаких ссылок, а затем вызываю бесплатную процедуру (также как показано ниже).

Это также может уменьшить объем ОЗУ, который вы выделите, если вам повезет (или очень умный) с вашим начальным malloc или вы можете доверять realloc, чтобы не перемещать блок при его сжатии.

struct freecell { struct freecell * next; void * memp; } * saved_pointers = 0; 

static void 
save_ptr_for_free(void * memp) 
{ 
    struct freecell * n = malloc(sizeof*n); 
    if (!n) {perror("malloc"); return; } 
    n->next = saved_pointers; 
    n->memp = memp; 
    saved_pointers = n; 
} 

static void 
free_saved_memory(void) 
{ 
    while(saved_pointers) { 
     struct freecell * n = saved_pointers; 
     saved_pointers = saved_pointers->next; 
     free(n->memp); 
     free(n); 
    } 
} 

Answer 3

Просто для полноты картины я хочу добавить свою версию DeleteTree

void DeleteTree(NODE *T) { 
    if(T != NULL) { 
    DeleteTree(T->rightbrothers); 
    DeleteTree(T->leftchild); 
    free(T); 
    } 
} 

Я думаю, что это гораздо менее неясен и гораздо легче читать. В основном это решает проблему в DeleteTree, но устраняет цикл.

Поскольку мы освобождаем узлы рекурсивно, мы можем также рекурсивно выполнять весь процесс.