#include "arbre.h" #include "objet_definitions.h" #include "memoire.h" #include /* C'est l'exercice de style par excellence */ typedef struct noeud *noeud; struct noeud { objet info; noeud g; noeud d; }; struct arbre { noeud racine; comparer cmp; }; static noeud *emplacement_element (objet elt, arbre a); static void supprimer_noeud_incomplet (noeud * n); static void detruire_branche (noeud n, appliquer f, objet parametre_1); static void parcourir_branche (noeud n, appliquer f, objet parametre_1); arbre abr_creer (comparer cmp) { arbre a = (arbre) mem_malloc (sizeof (struct arbre)); assert (cmp != NULL); a->racine = NULL; a->cmp = cmp; return a; } /* quelques fonctions récursives classiques... */ void abr_detruire (arbre a, appliquer f, objet parametre_1) { detruire_branche (a->racine, f, parametre_1); mem_free (a); } static void detruire_branche (noeud n, appliquer f, objet parametre_1) { if (n == NULL) return; detruire_branche (n->d, f, parametre_1); detruire_branche (n->g, f, parametre_1); f (parametre_1, n->info); mem_free (n); } static void parcourir_branche (noeud n, appliquer f, objet parametre_1) { if (n == NULL) return; parcourir_branche (n->g, f, parametre_1); f (parametre_1, n->info); parcourir_branche (n->d, f, parametre_1); } void abr_appliquer (arbre a, appliquer f, objet parametre_1) { parcourir_branche (a->racine, f, parametre_1); } /* Bienvenue au royaume du pointeur de pointeur ! */ static noeud * emplacement_element (objet elt, arbre a) { int comp; noeud *n; for (n = &a->racine; *n != NULL && (comp = a->cmp (elt, (*n)->info)); n = (comp > 0) ? &(*n)->d : &(*n)->g) ; return n; } objet abr_chercher (arbre a, objet elt) { noeud *n = emplacement_element (elt, a); return (*n == NULL) ? NULL : (*n)->info; } void abr_inserer (arbre a, objet elt) { noeud *position = emplacement_element (elt, a); assert (*position == NULL); *position = mem_malloc (sizeof (struct noeud)); (*position)->info = elt; (*position)->d = (*position)->g = NULL; } /* abr_supprimer 3 cas sont à considérer suivant que le noeud à supprimer soit : - une feuille : on supprime la feuille et on met NULL "dans son pere" - un noeud incomplet : on supprime le noeud et on lui substitue son (unique) fils "dans son pere" - un noeud complet : on remplace la valeur supprimée par la valeur maximale du ss-arbre gauche (ou le min du ss-arbre droit) pour ensuite supprimer le noeud (forcément incomplet) où résidait cette valeur. Les deux premiers cas sont traités par supprimer_noeud_incomplet prodécure intervenant aussi dans le troisième cas. */ objet abr_supprimer (arbre a, objet elt) { noeud *n = emplacement_element (elt, a); objet info; assert (*n != NULL); info = (*n)->info; if ((*n)->g == NULL || (*n)->d == NULL) supprimer_noeud_incomplet (n); else { noeud *max; for (max = &(*n)->g; (*max)->d != NULL; max = &(*max)->d) ; (*n)->info = (*max)->info; supprimer_noeud_incomplet (max); } return info; } static void supprimer_noeud_incomplet (noeud * n) { noeud a_detruire = *n; *n = ((*n)->g == NULL) ? (*n)->d : (*n)->g; mem_free (a_detruire); } /* pour le plaisir version non récursive : la version récursive est */ /* tellement plus simple et toute aussi performante */ #include "pile.h" void abr_parcours_infixe (arbre a, appliquer f, objet argument) { if (a->racine != NULL) { pile p = pil_creer (); noeud n = a->racine; do { for (; n != NULL; n = n->g) pil_empiler (p, n); n = pil_depiler (p); f (n->info, argument); n = n->d; } while (!pil_est_vide (p) || n != NULL); pil_detruire (p); } }