la libération de la mémoire d'un arbre binaire C

Je voudrais pour libérer de la mémoire de mon alloué arbre binaire de ce que la traversée est le meilleur pour le faire?

typedef struct Node{
struct Node * right;
struct Node * left;
void * data;
}Node;


typedef int (*cmp) (void*,void *);


Node* init(void * element){
    Node * newNode=(Node*)malloc(sizeof(Node));
    newNode->data=element;
    newNode->left=NULL;
    newNode->right=NULL;
    return newNode; 
}

void  insert(void * element, Node** root,cmp compareTo){
    if(*root==NULL){
        *root=init(element);
        return;
    }
    if(compareTo(element,(*root)->data)==1)
        insert(element,&((*root)->left),compareTo);
    else
        insert(element,&((*root)->right),compareTo);
}

OriginalL'auteur mary | 2012-02-07

  1. 8

    Puisque c'est un arbre, vous devriez aller avec une approche récursive.

    deallocate (node):
    //do nothing if passed a non-existent node
    if node is null
        return

    //now onto the recursion
    deallocate(left node)
    deallocate(right node)

    free node
    Si votre arbre est super grand des appels récursifs pourrait provoquer un débordement de pile (ahhhhhhh) dans laquelle vous voulez aller un itinéraire différent (itératif), mais vous serez l'augmentation de la complexité du temps.

    OriginalL'auteur Pochi

  2. 9

    Penser à ce que la traversée de différents types, et de garder à l'esprit, après vous libérer de la mémoire, vous n'êtes pas autorisé à y accéder plus:

    • Précommande: opération effectuée avant la visite de tous les enfants
    • Dans l'ordre: opération effectuée après la visite des sous-arbre gauche, avant droit de la sous-arborescence
    • Postorder: opération effectuée après la visite de toutes les sous-arborescences

    Donné les déclarations ci-dessus, la réponse doit être claire.

    OriginalL'auteur FatalError

  3. 3
    void free_tree(Node * node){
   //post-order like FatalError hinted at
       if (node != NULL) {
        free_tree(node->right);
        free(node->data); //if data was heap allocated, need to free it
        free_tree(node->left);
        free(node);
     }}

    Une façon cool pour vérifier seg défauts et fuites de mémoire est d'utiliser

    valgrind --leak-check=full ./yourProgram

    OriginalL'auteur MrPickles7

  4. 2

    Parcours en profondeur d'abord de recherche est le meilleur pour ce

    OriginalL'auteur Dan F

  5. 1

    Quand vous dites "le meilleur", vous voulez dire "correct" (c'est à dire, ne pas provoquer le chaos en accédant à la mémoire libérée) ou "les plus efficaces" ou quoi?

    Autant que la justesse va: Tout ce que vous voulez, à condition de prendre soin de ne pas accéder à des données après la libération. L'évidente de l'approche la plus simple (qui ne sont pas de l'état explicitement, car cela ressemble un peu comme des devoirs 🙂 mais c'est ce que vous feriez si vous vouliez écrire que peu de code que possible [ÉDITÉ à ajouter: c'est quoi "cnicutar" posté; j'espère que ce n'était pas de devoirs après tout!]) fonctionne très bien.

    Vous pourriez obtenir des résultats plus efficaces (dans l'espace ou dans le temps) par les correspondants de l'ordre de la libération avec la commande de répartition, mais les détails dépendent de votre allocateur de mémoire et vous ne devriez probablement pas de soins.

    OriginalL'auteur Gareth McCaughan