Accueil > Enseignement > Anciens cours (avant 2015-2016) > Algorithmique et arbres (L2 cours/TD 2005-2011) > [code] Implantation des arbres binaires de recherche du lundi 7/04 (...)
[code] Implantation des arbres binaires de recherche du lundi 7/04 2008

mardi 8 avril 2008, par Pierre
# include <stdlib.h>
# include <stdio.h>
# include <assert.h>
 
/* Les éléments : type et comparaison */
typedef int element_t;
 
int comparer(element_t a, element_t b){
  if (a < b) return 1;
  if (a > b) return -1;
  return 0;
}
 
void affiche_element(element_t e) {
  printf("%2d ", e);
}
 
/* Les ABR : type */
typedef struct abr_s {
  struct abr_s *parent;
  struct abr_s *droite;
  struct abr_s *gauche;
  element_t e;
} *abr_t;
 
/* Parcours dans l'ordre pour affichage */
void parcours_infixe(abr_t x) {
  if (x) {
    parcours_infixe(x->gauche);
    affiche_element(x->e);
    parcours_infixe(x->droite);
  }
}
 
/* minimum(x) renvoie le noeud contenant le minimum de l'arbre, ou
   NULL si l'arbre est vide */
abr_t minimum(abr_t x) {
  if (x) {
    while (x->gauche) {
      x = x->gauche;
    }
  }
  return x;
}
 
abr_t maximum(abr_t x) {
  if (x) {
    while (x->droite) {
      x = x->droite;
    }
  }
  return x;
}
 
/* Recherche d'un élément, renvoie le noeud contenant l'élément ou
   bien NULL si absent */
abr_t rechercher(abr_t x, element_t a) {
  if (x) {
    switch (comparer(a, x->e)) {
    case 1:
      return rechercher(x->gauche, a);
      break;
    case -1:
      return rechercher(x->droite, a);
      break;
    case 0:
      return x;
    }
  }
  return NULL; /* élément introuvable */
}
 
/* successeur(y): renvoie le successeur de y dans l'arbre ou NULL s'il
   n'existe pas */
abr_t successeur(abr_t y){
  assert(y);
  if (y->droite) {
    return minimum(y->droite);
  }
  else {
    while ( y-> parent && (y == (y->parent)->droite) ) {
      y = y->parent;
    }
    return y->parent;
  }
}
 
abr_t predecesseur(abr_t y){
  assert(y);
  if (y->gauche) {
    return maximum(y->gauche);
  }
  else {
    while ( y-> parent && (y == (y->parent)->gauche) ) {
      y = y->parent;
    }
    return y->parent;
  }
}
 
/* nouveau_noeud(a), crée (allocation mémoire) et renvoie un arbre à
   un seul noeud contenant l'élément a. */
abr_t nouveau_noeud(element_t a) {
  abr_t x;
  x = malloc(sizeof(abr_t));
  if (!x) perror("malloc");
  x->parent = NULL;
  x->gauche = NULL;
  x->droite = NULL;
  x->e = a;
  return x;
}
 
void effacer_noeud(abr_t x) {
  free(x);
}
 
/* inserer(&x, a) insere un élément a dans un arbre binaire de
   recherche x. S'il existe déjà un élément b égal à a dans l'arbre
   aucun noeud n'est créé (pas de répétition).  La fonction inserer()
   ne renvoie rien, l'arbre x est passé par adresse (px = adresse de
   l'arbre) pour être directement modifié (argument-résultat). */ 
 
void inserer(abr_t *px, element_t e) {
  abr_t x, parent;
  int cote;
  if ( !(*px) ) {
    *px = nouveau_noeud(e);
    return;
  }
  x = *px;
  /* Recherche de la place de a (parent et côté où le mettre) */
  while ( x ) {
    parent = x;
    switch ( cote = comparer(e, x->e) ) {
    case 1:
      x = x->gauche;
      break;
    case -1:
      x = x->droite;
      break;
    case 0:
      return; /* pas de répétition dans l'arbre */
    }
  }
  /* parent sera le parent du nouveau noeud, la valeur de cote dit de
       quel côté l'attacher à son parent.  */
  x = nouveau_noeud(e);
  x->parent = parent;
  if (cote == 1) {
    parent->gauche = x;
  }
  else {
    parent->droite = x;
  }  
}
 
/* supprimer(px, y) supprime l'élément contenu dans le noeud d'adresse
   y de l'arbre d'adresse px (argument-résultat).
 
   Remarque : pour supprimer un élément a il faut d'abord chercher
   dans l'arbre l'adresse du noeud qui le contient. 
   Exemple:
       supprimer(&x, rechercher(x, a));
   Ou bien:
       if (y = rechercher(x, a)) supprimer(&x, y); 
*/
 
void supprimer(abr_t *px, abr_t y) {
  assert(y);
  if (y->gauche && y->droite) {
    abr_t z;
    z = successeur(y); /* en fait z = minimum(y->droite) */
    y->e = z->e;
    supprimer(px, z);
  }
  else {
    abr_t fils;
    if ( y->gauche ) {
      fils = y->gauche;
    } else {
      fils = y->droite;
    }
   /* Si il y avait un parent alors fils remplace y auprès de ce parent */
 
    if ( y->parent ) {
      if ( y == (y->parent)->gauche ) {
	(y->parent)->gauche = fils;
      } else {
	(y->parent)->droite = fils;	
      }
    } else {
      *px = fils;
    }
  /*  le parent de y devient le nouveau parent du fils */
 
    if (fils) {
      fils->parent = y->parent;
    }
    effacer_noeud(y);
  }
}
 
/* Rotations :
 
 x -> b       ---rot. droite de centre x-->     a <- x
     / \                                       / \
    a   C     <--rot. gauche de centre x---   A   b 
   / \                                           / \
  A   B                                         B   C
 
*/
 
void rotation_droite(abr_t x) {
  abr_t y, A, B, C;
  element_t e;
  assert(x && x->gauche);
  y = x->gauche;
  A = y->gauche;
  B = y->droite;
  C = x->droite;
  /* échange des deux éléments */
  e = x->e;
  x->e = y->e;
  y->e = e;
 
  /* remise en place des sous-arbres */
  x->droite = y;
  x->gauche = A;
  A->parent = x;
  y->gauche = B;
  y->droite = C;
  C->parent = y;
}
 
/* Affichage "simple" en mode texte, exemple :
 
L'arbre       4
             / \
            1   7
           / \   \
          0   3   9
                 /
                8
 
s'affichera comme ceci :
 
 
 4 ----- 7 ----- 9 
 |               |      
 |               8 
 |      
 1 ----- 3 
 |      
 0 
 
*/
 
/* fonction auxilliaire pour l'affichage d'une ligne de traits
   verticaux représentant la descendance à gauche. */
void afficher_arbre_aux1(abr_t x){
  if (x->parent) {
    afficher_arbre_aux1(x->parent);
    if (x == (x->parent)->droite) {
      if ((x->parent)->gauche) {
	printf(" |      "); /* 8 caractères */
      }
      else {
	printf("        "); /* 8 caractères */
      }
    }
  }
}
 
/* afficher_arbre(x) réalise l'affichage de x sur la sortie standard
   comme décrit plus haut. */
void afficher_arbre(abr_t x){
  if (x) { /* Si l'arbre n'est pas vide, on réalise l'affichage par
	      appels récursifs sur les sous-arbres non vides. */
    affiche_element(x->e);
    if (x->droite) { /* noeuds de droite sur la même ligne */
      printf("-----");
      afficher_arbre(x->droite);
    }
    else { /* plus rien à droite : fin de ligne */
    printf("\n");
    }
    if (x->gauche) {   
      afficher_arbre_aux1(x->gauche);
      printf(" |      \n"); /* 8 caractères */
      afficher_arbre_aux1(x->gauche);
      afficher_arbre(x->gauche);
    }
  }
  else { /* Si l'arbre est vide on le signale */
    printf("\n        (arbre vide)\n\n");
  }
}
 
int main() {
    abr_t            x = NULL;
    element_t       i;
    element_t       tab[] = {5, 2, 4, 3, 7, 6, 1, 9, 8, 0};
  
    for (i = 0; i < 10; i++) {
     inserer(&x, tab[i]);
    }
    parcours_infixe(x);
    printf("fin du parcours \n");
    printf("\nAffichage ***************************\n");
    afficher_arbre(x);
 
    supprimer(&x, rechercher(x, 6));
    printf("\nAffichage (supprimer 6)**************\n");
    afficher_arbre(x);
 
    supprimer(&x, rechercher(x, 5));
    printf("\nAffichage (supprimer 5)**************\n");
    afficher_arbre(x);
 
    rotation_droite(rechercher(x, 2));
    printf("\nAffichage (rotation_droite 2)********\n");
    afficher_arbre(x);
 
    supprimer(&x, rechercher(x, 2));
    printf("\nAffichage (supprimer 2)**************\n");
    afficher_arbre(x);
 
    supprimer(&x, rechercher(x, 7));
    printf("\nAffichage (supprimer 7)**************\n");
    afficher_arbre(x);
 
    return EXIT_SUCCESS;
}