[code] Implantation des arbres binaires de recherche du lundi 7/04 2008

, par Pierre

  1. # include <stdlib.h>
  2. # include <stdio.h>
  3. # include <assert.h>
  4.  
  5. /* Les éléments : type et comparaison */
  6. typedef int element_t;
  7.  
  8. int comparer(element_t a, element_t b){
  9.   if (a < b) return 1;
  10.   if (a > b) return -1;
  11.   return 0;
  12. }
  13.  
  14. void affiche_element(element_t e) {
  15.   printf("%2d ", e);
  16. }
  17.  
  18. /* Les ABR : type */
  19. typedef struct abr_s {
  20.   struct abr_s *parent;
  21.   struct abr_s *droite;
  22.   struct abr_s *gauche;
  23.   element_t e;
  24. } *abr_t;
  25.  
  26. /* Parcours dans l'ordre pour affichage */
  27. void parcours_infixe(abr_t x) {
  28.   if (x) {
  29.     parcours_infixe(x->gauche);
  30.     affiche_element(x->e);
  31.     parcours_infixe(x->droite);
  32.   }
  33. }
  34.  
  35. /* minimum(x) renvoie le noeud contenant le minimum de l'arbre, ou
  36.    NULL si l'arbre est vide */
  37. abr_t minimum(abr_t x) {
  38.   if (x) {
  39.     while (x->gauche) {
  40.       x = x->gauche;
  41.     }
  42.   }
  43.   return x;
  44. }
  45.  
  46. abr_t maximum(abr_t x) {
  47.   if (x) {
  48.     while (x->droite) {
  49.       x = x->droite;
  50.     }
  51.   }
  52.   return x;
  53. }
  54.  
  55. /* Recherche d'un élément, renvoie le noeud contenant l'élément ou
  56.    bien NULL si absent */
  57. abr_t rechercher(abr_t x, element_t a) {
  58.   if (x) {
  59.     switch (comparer(a, x->e)) {
  60.     case 1:
  61.       return rechercher(x->gauche, a);
  62.       break;
  63.     case -1:
  64.       return rechercher(x->droite, a);
  65.       break;
  66.     case 0:
  67.       return x;
  68.     }
  69.   }
  70.   return NULL; /* élément introuvable */
  71. }
  72.  
  73. /* successeur(y): renvoie le successeur de y dans l'arbre ou NULL s'il
  74.    n'existe pas */
  75. abr_t successeur(abr_t y){
  76.   assert(y);
  77.   if (y->droite) {
  78.     return minimum(y->droite);
  79.   }
  80.   else {
  81.     while ( y-> parent && (y == (y->parent)->droite) ) {
  82.       y = y->parent;
  83.     }
  84.     return y->parent;
  85.   }
  86. }
  87.  
  88. abr_t predecesseur(abr_t y){
  89.   assert(y);
  90.   if (y->gauche) {
  91.     return maximum(y->gauche);
  92.   }
  93.   else {
  94.     while ( y-> parent && (y == (y->parent)->gauche) ) {
  95.       y = y->parent;
  96.     }
  97.     return y->parent;
  98.   }
  99. }
  100.  
  101. /* nouveau_noeud(a), crée (allocation mémoire) et renvoie un arbre à
  102.    un seul noeud contenant l'élément a. */
  103. abr_t nouveau_noeud(element_t a) {
  104.   abr_t x;
  105.   x = malloc(sizeof(abr_t));
  106.   if (!x) perror("malloc");
  107.   x->parent = NULL;
  108.   x->gauche = NULL;
  109.   x->droite = NULL;
  110.   x->e = a;
  111.   return x;
  112. }
  113.  
  114. void effacer_noeud(abr_t x) {
  115.   free(x);
  116. }
  117.  
  118. /* inserer(&x, a) insere un élément a dans un arbre binaire de
  119.    recherche x. S'il existe déjà un élément b égal à a dans l'arbre
  120.    aucun noeud n'est créé (pas de répétition).  La fonction inserer()
  121.    ne renvoie rien, l'arbre x est passé par adresse (px = adresse de
  122.    l'arbre) pour être directement modifié (argument-résultat). */
  123.  
  124. void inserer(abr_t *px, element_t e) {
  125.   abr_t x, parent;
  126.   int cote;
  127.   if ( !(*px) ) {
  128.     *px = nouveau_noeud(e);
  129.     return;
  130.   }
  131.   x = *px;
  132.   /* Recherche de la place de a (parent et côté où le mettre) */
  133.   while ( x ) {
  134.     parent = x;
  135.     switch ( cote = comparer(e, x->e) ) {
  136.     case 1:
  137.       x = x->gauche;
  138.       break;
  139.     case -1:
  140.       x = x->droite;
  141.       break;
  142.     case 0:
  143.       return; /* pas de répétition dans l'arbre */
  144.     }
  145.   }
  146.   /* parent sera le parent du nouveau noeud, la valeur de cote dit de
  147.        quel côté l'attacher à son parent.  */
  148.   x = nouveau_noeud(e);
  149.   x->parent = parent;
  150.   if (cote == 1) {
  151.     parent->gauche = x;
  152.   }
  153.   else {
  154.     parent->droite = x;
  155.   }  
  156. }
  157.  
  158. /* supprimer(px, y) supprime l'élément contenu dans le noeud d'adresse
  159.    y de l'arbre d'adresse px (argument-résultat).
  160.  
  161.    Remarque : pour supprimer un élément a il faut d'abord chercher
  162.    dans l'arbre l'adresse du noeud qui le contient.
  163.    Exemple:
  164.        supprimer(&x, rechercher(x, a));
  165.    Ou bien:
  166.        if (y = rechercher(x, a)) supprimer(&x, y);
  167. */
  168.  
  169. void supprimer(abr_t *px, abr_t y) {
  170.   assert(y);
  171.   if (y->gauche && y->droite) {
  172.     abr_t z;
  173.     z = successeur(y); /* en fait z = minimum(y->droite) */
  174.     y->e = z->e;
  175.     supprimer(px, z);
  176.   }
  177.   else {
  178.     abr_t fils;
  179.     if ( y->gauche ) {
  180.       fils = y->gauche;
  181.     } else {
  182.       fils = y->droite;
  183.     }
  184.    /* Si il y avait un parent alors fils remplace y auprès de ce parent */
  185.  
  186.     if ( y->parent ) {
  187.       if ( y == (y->parent)->gauche ) {
  188.         (y->parent)->gauche = fils;
  189.       } else {
  190.         (y->parent)->droite = fils;    
  191.       }
  192.     } else {
  193.       *px = fils;
  194.     }
  195.   /*  le parent de y devient le nouveau parent du fils */
  196.  
  197.     if (fils) {
  198.       fils->parent = y->parent;
  199.     }
  200.     effacer_noeud(y);
  201.   }
  202. }
  203.  
  204. /* Rotations :
  205.  
  206.  x -> b       ---rot. droite de centre x-->     a <- x
  207.      / \                                       / \
  208.     a   C     <--rot. gauche de centre x---   A   b
  209.    / \                                           / \
  210.   A   B                                         B   C
  211.  
  212. */
  213.  
  214. void rotation_droite(abr_t x) {
  215.   abr_t y, A, B, C;
  216.   element_t e;
  217.   assert(x && x->gauche);
  218.   y = x->gauche;
  219.   A = y->gauche;
  220.   B = y->droite;
  221.   C = x->droite;
  222.   /* échange des deux éléments */
  223.   e = x->e;
  224.   x->e = y->e;
  225.   y->e = e;
  226.  
  227.   /* remise en place des sous-arbres */
  228.   x->droite = y;
  229.   x->gauche = A;
  230.   A->parent = x;
  231.   y->gauche = B;
  232.   y->droite = C;
  233.   C->parent = y;
  234. }
  235.  
  236. /* Affichage "simple" en mode texte, exemple :
  237.  
  238. L'arbre       4
  239.              / \
  240.             1   7
  241.            / \   \
  242.           0   3   9
  243.                  /
  244.                 8
  245.  
  246. s'affichera comme ceci :
  247.  
  248.  
  249.  4 ----- 7 ----- 9
  250.  |               |      
  251.  |               8
  252.  |      
  253.  1 ----- 3
  254.  |      
  255.  0
  256.  
  257. */
  258.  
  259. /* fonction auxilliaire pour l'affichage d'une ligne de traits
  260.    verticaux représentant la descendance à gauche. */
  261. void afficher_arbre_aux1(abr_t x){
  262.   if (x->parent) {
  263.     afficher_arbre_aux1(x->parent);
  264.     if (x == (x->parent)->droite) {
  265.       if ((x->parent)->gauche) {
  266.         printf(" |      "); /* 8 caractères */
  267.       }
  268.       else {
  269.         printf("        "); /* 8 caractères */
  270.       }
  271.     }
  272.   }
  273. }
  274.  
  275. /* afficher_arbre(x) réalise l'affichage de x sur la sortie standard
  276.    comme décrit plus haut. */
  277. void afficher_arbre(abr_t x){
  278.   if (x) { /* Si l'arbre n'est pas vide, on réalise l'affichage par
  279.               appels récursifs sur les sous-arbres non vides. */
  280.     affiche_element(x->e);
  281.     if (x->droite) { /* noeuds de droite sur la même ligne */
  282.       printf("-----");
  283.       afficher_arbre(x->droite);
  284.     }
  285.     else { /* plus rien à droite : fin de ligne */
  286.     printf("\n");
  287.     }
  288.     if (x->gauche) {  
  289.       afficher_arbre_aux1(x->gauche);
  290.       printf(" |      \n"); /* 8 caractères */
  291.       afficher_arbre_aux1(x->gauche);
  292.       afficher_arbre(x->gauche);
  293.     }
  294.   }
  295.   else { /* Si l'arbre est vide on le signale */
  296.     printf("\n        (arbre vide)\n\n");
  297.   }
  298. }
  299.  
  300. int main() {
  301.     abr_t            x = NULL;
  302.     element_t       i;
  303.     element_t       tab[] = {5, 2, 4, 3, 7, 6, 1, 9, 8, 0};
  304.  
  305.     for (i = 0; i < 10; i++) {
  306.      inserer(&x, tab[i]);
  307.     }
  308.     parcours_infixe(x);
  309.     printf("fin du parcours \n");
  310.     printf("\nAffichage ***************************\n");
  311.     afficher_arbre(x);
  312.  
  313.     supprimer(&x, rechercher(x, 6));
  314.     printf("\nAffichage (supprimer 6)**************\n");
  315.     afficher_arbre(x);
  316.  
  317.     supprimer(&x, rechercher(x, 5));
  318.     printf("\nAffichage (supprimer 5)**************\n");
  319.     afficher_arbre(x);
  320.  
  321.     rotation_droite(rechercher(x, 2));
  322.     printf("\nAffichage (rotation_droite 2)********\n");
  323.     afficher_arbre(x);
  324.  
  325.     supprimer(&x, rechercher(x, 2));
  326.     printf("\nAffichage (supprimer 2)**************\n");
  327.     afficher_arbre(x);
  328.  
  329.     supprimer(&x, rechercher(x, 7));
  330.     printf("\nAffichage (supprimer 7)**************\n");
  331.     afficher_arbre(x);
  332.  
  333.     return EXIT_SUCCESS;
  334. }

Télécharger

Revenu et logement, Je livre ici quelques éléments de comparaison concernant mon niveau de vie, pour couper court à quelques idées reçues, et un condensé de nombreuses (...)
Revenu et travail d’un enseignant-chercheur, Cet article complète l'article Revenu et logement, en détaillant un peu le budget de mon ménage, mon parcours d'enseignant-chercheur en terme de (...)
Cybersyn (el systemo synco), Au café, mardi 5 avril 2011, j'ai bien vu que, mis à part Antoine Allombert, personne ne connaissait l'histoire de l'extraordinaire projet chilien (...) [jpg, jpg, png]