[code] Implantation des arbres binaires de recherche

< !—>

# include <stdlib.h>
# include <stdio.h>

/* 
   On définit un type pour les éléments et une fonction de comparaison
   entre éléments 
*/
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 a) {
  printf("%2d ", a);
}


/*
  On définit le type des arbres binaires, qui est utilisé ici pour
  les arbres binaires de recherche (voir cours).

  L'arbre vide est représenté par NULL (l'adresse mémoire 0).
*/

typedef struct noeud_s {
  element_t        e;
  struct noeud_s * gauche;
  struct noeud_s * droite;
  struct noeud_s * parent;
} * ab_t;



/* parcours_infixe(x) affiche les éléments de x dans l'ordre */

void parcours_infixe(ab_t x){
  if (x) {
    parcours_infixe(x->gauche);
    affiche_element(x->e); 
    parcours_infixe(x->droite);
  }
}

/* cardinal(x) renvoie le nombre de noeuds de l'arbre x */

int cardinal(ab_t x){
  if (x) {
    return cardinal(x->gauche) + cardinal(x->droite) + 1;
  }
  else return 0;
}

/* Utile: max(p, q) renvoie le maximum entre ces deux entiers */

int max(int p, int q) {
  return (p > q) ? p : q;
}

/* hauteur(x) renvoie la hauteur de l'arbre x */

int hauteur(ab_t x){
  if (x) {
    return 1 + max(hauteur(x->gauche), hauteur(x->droite));
  }
  else return 0;
}

/* maximum(x) renvoie NULL si x est vide et l'élément maximum sinon */

ab_t maximum(ab_t x){
  if (!x) {
    return NULL;
  }
  if (!(x->droite)) {
    return x;
  }
  return maximum(x->droite);
}

/* 
--- Alternative (fonction non récursive) ---
ab_ t maximum(ab_t x){
  if (x) {
    while (x->droite) {
      x = x->droite;
    }
  }
  return x;
}
*/

/* minimum(x): de même que maximum(x), pour le minimum */

ab_t minimum(ab_t x){
  if (!x) {
    return NULL;
  }
  if (!(x->gauche)) {
    return x;
  }
  return minimum(x->gauche);
}


/* predecesseur(x) prend l'adresse d'un noeud d'un abr et renvoie le
   predecesseur de ce noeud dans l'arbre. */

ab_t predecesseur(ab_t x){
  if (x->gauche) {
    return maximum(x->gauche);
  }
  while (x->parent && (x == (x->parent)->gauche)){
    x = x->parent;
  }
  return x->parent;
}

/* rechercher(x, a) cherche un element b dans l'arbre x tel que a = b
   au sens de la fonction de comparaison des éléments, et renvoie le
   noeud contenant b ou NULL si un tel element n'existe pas . */

ab_t rechercher(ab_t x, element_t a){
  if (x) {
    switch ( comparer(a, x->e) ){
    case 1: 
      return rechercher(x->gauche, a);
    case 0:
      return x;
    case -1:
      return rechercher(x->droite, a);    
    }
  }
  return NULL; /* élément introuvable */
}

/* nouveau_noeud(a), crée (allocation mémoire) et renvoie un arbre à
   un seul noeud contenant l'élément a. */

ab_t nouveau_noeud(element_t a){
  ab_t x;
  x = malloc(sizeof(ab_t*));
  if (!x) {
    perror("Echec malloc");
  }
  x->parent = NULL;
  x->gauche = NULL;
  x->droite = NULL;
  x->e = a;
  return 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(ab_t *px, element_t a){
  if (!(*px)) {
    *px = nouveau_noeud(a);
  }  
  else {
    ab_t y, parent;
    int cote;
    y = *px;
    /* Recherche de la place de a (parent et côté où le mettre) */
    while (y) {
      parent = y;
      cote = comparer(a, y->e);
      switch(cote){
      case 1: /* côté gauche */
        y = y->gauche;
        break;
      case -1: /* côté droit */ 
        y = y->droite;
        break;
      case 0: /* on a déjà cet élément, pas d'insertion */
        return;       
      }    
    }
    /* parent sera le parent du nouveau noeud, la valeur de cote dit
       de quel côté l'attacher à son parent.  */
    y = nouveau_noeud(a);
    y->parent = parent;
    if (1 == cote) {
      parent->gauche = y;
    }
    else {
      parent->droite = y;
    }
  }    
}

/* 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(ab_t * px, ab_t y){
  if (y->gauche && y->droite) {
    ab_t z; /* z = le predecesseur de y */
    z = predecesseur(y);
    y->e = z->e;
    supprimer(px, z); /* On pourrait aussi continuer avec y = z */
  }
  else {
    ab_t z; /* z = l'unique fils de y ou NULL s'il n'y en a pas */
    if (y->gauche) {
      z = y->gauche;
    }
    else {
      z = y->droite;
    }

    /*  le parent de y devient le nouveau parent de z */
    if (z) {
      z->parent = y->parent;
    }

    /* Si y avait un parent alors z remplace y auprès de ce parent */
    if (y->parent) {
      if (y == (y->parent)->gauche ){
        (y->parent)->gauche = z;        
      }
      else {
        (y->parent)->droite = z;
      }
      if (z) {
        z->parent = y->parent;
      }
    }
    /* Sinon y était la racine, il faut mettre l'arbre à jour */
    else { 
      *px = z;
    }
    free(y);
  }
}

/* vider(&x) : libère l'espace mémoire utilisé par l'arbre x, et met x
   à NULL (arbre vide) */

void vider(ab_t *px){
  ab_t x;
  x = *px;
  if (x) {
    vider(&(x->gauche));
    vider(&(x->droite));
    free(x);
    *px = NULL;
  }
}

/* Rotations :

 y -> b       ---rot. droite de centre y-->     a <- y
     / \                                       / \
    a   C     <--rot. gauche de centre y---   A   b 
   / \                                           / \
  A   B                                         B   C

*/

void rotation_droite(ab_t y){
  element_t tmp;
  ab_t x;
  
  x = y->gauche;

  /* échange des éléments */
  tmp = y->e;
  y->e = x->e;
  x->e = tmp;

  /* déplacement des sous-arbres */
  y->gauche = x->gauche;
  x->gauche = x->droite;
  x->droite = y->droite;
  y->droite = x;
  
  /* mise à jour des parents */ 
  (y->gauche)->parent = y;
  (x->droite)->parent = x;  
}


void rotation_gauche(ab_t y){
  element_t tmp;
  ab_t x;
  
  x = y->droite;

  /* échange des éléments */
  tmp = y->e;
  y->e = x->e;
  x->e = tmp;

  /* déplacement des sous-arbres */
  y->droite = x->droite;
  x->droite = x->gauche;
  x->gauche = y->gauche;
  y->gauche = x;
  
  /* mise à jour des parents */ 
  (y->droite)->parent = y;
  (x->gauche)->parent = x;  
}

/* 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(ab_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(ab_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() {
    ab_t            x = NULL;
    element_t       i;
    element_t       tab[] = {5, 2, 4, 3, 7, 6, 1, 9, 8, 0};
    element_t       tab2[] = {1, 4, 5, 3, 2};
 
    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);

    vider(&x);
    printf("\nAffichage (vider)********************\n");
    afficher_arbre(x);

    for (i = 0; i < 5; i++) {
     inserer(&x, tab2[i]);
    }

    printf("\nAffichage ***************************\n");
    afficher_arbre(x);

    vider(&x);
    printf("\nAffichage (vider)********************\n");
    afficher_arbre(x);

    return EXIT_SUCCESS;
}