Освободить память, выделенная для дерева - C

Question

У меня есть дерево, определенное как,

struct tree { 
    char label[MAX_LENGTH]; 
    char value[MAX_LENGTH]; 
    struct tree *child; 
    struct tree *next; 
}; 

Теперь мне нужно, чтобы освободить память, выделенную этим деревом. Я написал следующий код.

unsigned int tree_free(struct tree *root) 
{ 
    struct tree *current = NULL, *next = NULL, *child = NULL; 
    unsigned int freecnt = 0; 

    current = root; 
    while(current != NULL) 
    { 
     next = current->next; 
     child = current->child;  
     xfree(current); 
     freecnt += tree_free(child) + 1; 
     current = next; 
    } 
    return freecnt; 
} 

Этот метод возвращает количество элементов, которые он освободил, так что я могу проверить его от числа ассигнованиями. Этот код работает. Но я не уверен, что это правильный способ делать что-то.

Это реализация дерева суффикса. Для элементов с, стек, более, переполнение, StackOverflow дерево будет выглядеть

root 
-s 
--stack 
---stackoverflow 
-over 
--overflow 

Любые предложения по улучшению кода приветствуются.

Answer 1

Если вам нужно освободить дерево, вам нужно его пройти, поэтому я думаю, что код правильный. Я бы сделал это таким же образом (рекурсивно ходить по дереву, освобождая объекты на этом пути). Единственное, что я сделал бы по-другому, это запустить xfree после рекурсии (т. Е. Обмен xfree(current); и freecnt += tree_free(child) + 1;). Поскольку теперь вы удаляете узел перед удалением его дочернего элемента, но я чувствую, что лучше удалить дочерний элемент перед удалением родителя.

Кроме того, вы можете избавиться от переменной child, поскольку вы используете ее только один раз, с реальной потребностью. Сэкономит вам sizeof(pointer) пространства стека за рекурсию ;-)

Answer 2

Это довольно хорошее решение. Вы используете рекурсию для детей (которая не будет слишком глубокой), но итерация для братьев и сестер (которая будет уйти вглубь, если вы использовали рекурсию). Ваш код мог бы быть более изящным как решение для рекурсии (вызов tree_free для обоих child и next), но риск переполнения стека будет значительно увеличен, поэтому я думаю, что вы сделали правильный выбор там.

Сказав, что нет никакой необходимости в child вообще, если вы переставить порядок ваших действий:

unsigned int tree_free (struct tree *root) { 
    struct tree *current = NULL, *next = NULL; 
    unsigned int freecnt = 0; 

    current = root; 
    while(current != NULL) 
    { 
     freecnt += tree_free (current->child) + 1; 
     next = current->next; 
     xfree (current); 
     current = next; 
    } 
    return freecnt; 
} 

Если вы считаете, что длина вашего списка родственного не будет, что большой, вы может попробовать элегантное решение:

unsigned int tree_free (struct tree *root) { 
    unsigned int freecnt; 

    if (root == NULL) return 0; 
    freecnt = tree_free (root->child) + tree_free (root->next); 
    xfree (root); 
    return freecnt + 1; 
} 

это тестировался, так что я не делать никаких заявлений об отсутствии гарантий или пригодности для конкретной цели, тем более, что это, наверное, опасно для вашего конкретного случая большого числа SIBL ссылки. Я включаю его больше как указание на то, что возможно с рекурсией. Мой совет - использовать первый.