#include #include #include "arbre.h" typedef struct noeud *noeud; struct noeud { void *info; noeud g; noeud d; }; struct arbre { noeud racine; comparer cmp; detruire_element detruire; }; static noeud *position_element(void *elt, arbre a); static void *supprimer_noeud_a_fils_nul(noeud * n); static void detruire_noeud(noeud n, detruire_element detruire) ; /*****************************************************/ arbre arb_creer(comparer cmp, detruire_element detruire) { arbre a = (arbre) malloc(sizeof(struct arbre)); assert(a != NULL && cmp != NULL && detruire != NULL); *a = (struct arbre){NULL, cmp, detruire}; return a; } void arb_liberer(arbre *a) { assert(a != NULL && *a != NULL); detruire_noeud((*a)->racine,(*a)->detruire); free(*a) ; *a = NULL ; } static void detruire_noeud(noeud n, detruire_element detruire) { if ( n == NULL) return ; detruire_noeud(n->g,detruire); detruire_noeud(n->d,detruire); detruire(n->info); free(n); } static noeud * position_element(void *elt, arbre a) { int comp; noeud *n = &a->racine; for (n = &a->racine; *n != NULL && (comp = a->cmp(elt, (*n)->info) != 0); n = (comp > 0) ? &(*n)->d : &(*n)->g) ; return n; } void * arb_chercher(void *elt, arbre a) { noeud *n; assert(elt != NULL && a != NULL); n = position_element(elt, a); return (*n == NULL) ? NULL : (*n)->info; } void arb_inserer(void *elt, arbre a) { noeud *position; noeud n = (noeud) malloc(sizeof(struct noeud)); assert(elt != NULL && a != NULL && n != NULL); *n = (struct noeud) { elt, NULL, NULL }; position = position_element(elt, a); assert(*position == NULL); *position = n; } void * arb_supprimer(void *elt, arbre a) { noeud *n; assert(elt != NULL && a != NULL); n = position_element(elt, a); assert(*n != NULL); if ((*n)->g == NULL || (*n)->d == NULL) return supprimer_noeud_a_fils_nul(n); { noeud *max_sous_arbre_g; void *valeur_elt = (*n)->info; for (max_sous_arbre_g = &(*n)->g; *max_sous_arbre_g != NULL; max_sous_arbre_g = &(*n)->d) ; (*n)->info = supprimer_noeud_a_fils_nul(max_sous_arbre_g); return valeur_elt; } } static void * supprimer_noeud_a_fils_nul(noeud * n) { void *element = (*n)->info; if ((*n)->g == NULL && (*n)->d == NULL) { free(*n); *n = NULL; } else { noeud noeud_a_detruire = *n; *n = ((*n)->g == NULL) ? (*n)->d : (*n)->g; free(noeud_a_detruire); } return element; } void arb_detruire(void *elt, arbre a) { assert(a != NULL); a->detruire(arb_supprimer(elt,a)) ; }