#include "abr.h" #include "memoire.h" #include typedef struct noeud *noeud; struct noeud { void *info; noeud g; noeud d; }; struct abr { noeud racine; comparer cmp; }; static noeud *emplacement_element (void *elt, abr a); static void supprimer_noeud_incomplet (noeud * n); static void detruire_branche (noeud n, appliquer f, void *parametre_1); static void parcourir_branche (noeud n, appliquer f, void *parametre_1); abr abr_creer (comparer cmp) { assert (cmp != NULL); abr a = (abr) memoire_allouer (sizeof (struct abr)); *a = (struct abr) { .racine = NULL,.cmp = cmp}; return a; } /* quelques fonctions récursives classiques... */ void abr_detruire (abr a, appliquer f, void *parametre_1) { detruire_branche (a->racine, f, parametre_1); memoire_liberer (a); } static void detruire_branche (noeud n, appliquer f, void *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); memoire_liberer (n); } static void parcourir_branche (noeud n, appliquer f, void *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 (abr a, appliquer f, void *parametre_1) { parcourir_branche (a->racine, f, parametre_1); } /* emplacement_element retourne l'emplacement "logique" de l'élément ie. l'adresse du pointeur qui désigne ou pourrait designer le noeud contenant elt */ static noeud * emplacement_element (void *elt, abr 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; } void * abr_chercher (abr a, void *elt) { noeud *n = emplacement_element (elt, a); return (*n == NULL) ? NULL : (*n)->info; } void abr_inserer (abr a, void *elt) { noeud *position = emplacement_element (elt, a); assert (*position == NULL); *position = memoire_allouer (sizeof (struct noeud)); **position = (struct noeud) {.info = elt, .d= NULL, .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-abr gauche (ou le min du ss-abr 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. */ void * abr_supprimer (abr a, void *elt) { noeud *n = emplacement_element (elt, a); void *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; memoire_liberer (a_detruire); }