mémoire allouée pour Libérant un arbre - C

Question

J'ai un arbre défini comme,

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

Maintenant, je dois libérer la mémoire allouée par cet arbre. J'ai écrit le code suivant.

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

Cette méthode renvoie le nombre d'éléments qu'elle a libérés afin que je puisse le vérifier par rapport au nombre d'allocations effectuées. Ce code fonctionne. Mais je ne suis pas sûr que ce soit la bonne façon de faire les choses.

Ceci est une implémentation d'arborescence de suffixes. Pour les articles de, pile, plus, trop-plein, Stackoverflow l'arbre ressemblera

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

Toutes les suggestions pour améliorer le code sont les bienvenus.

Answer 1

Si vous avez besoin de libérer un arbre, vous devez marcher, donc je pense que le code est correct. Je l'aurais fait de la même manière (marcher récursivement dans l'arbre, libérant les objets le long du chemin). La seule chose que je ferais différemment est d'exécuter xfree après la récursivité (c'est-à-dire échanger xfree(current); et freecnt += tree_free(child) + 1;). Parce que maintenant vous supprimez un nœud avant de supprimer son enfant, mais je pense qu'il serait préférable de supprimer l'enfant avant de supprimer le parent.

Aussi, vous pouvez vous débarrasser de la variable child que vous l'utilisez une seule fois, avec un réel besoin. Vous économiserait sizeof(pointer) de l'espace de pile par récursivité ;-)

Answer 2

C'est une assez bonne solution. Vous utilisez la récursivité pour les enfants (qui ne sera pas trop profonde) mais l'itération pour les frères et sœurs (serait aller plus loin si vous avez utilisé la récursivité). Votre code pourrait certainement être plus élégant comme une solution de récursivité seulement (appelant tree_free pour child et next) mais le risque de débordement de la pile serait grandement augmenté donc je pense que vous avez fait le bon choix.

Cela dit, il n'y a pas besoin de child du tout si vous réarranger l'ordre de vos opérations:

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

Si vous pensez que la longueur de votre liste de frères et soeurs ne sera pas si grande, vous pourrait essayer la solution élégante:

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

il est non testé Je fais donc aucune déclaration de garantie ou adéquation à un usage, d'autant qu'il est probablement dangereux pour votre cas spécifique d'un grand nombre de SIBL liens. Je l'inclue plus comme une indication de ce qui est possible avec la récursivité. Mon conseil est d'utiliser le premier.