TP6/arbres/ABR/ABR.c

   1 /*****************************************************************************/
   2 /*                      ABR : arbres binaires de recherche                   */
   3 /*****************************************************************************/
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 typedef int element;
   9
  10 typedef struct noeud {
  11     element valeur;
  12     struct noeud *gauche;
  13     struct noeud *droit;
  14 } NOEUD, *ABR;
  15
  16
  17 /* Creation d'un ABR vide */
  18 NOEUD *arbre_vide()
  19 {
  20     return NULL;
  21 }
  22
  23
  24 /* Insertion/Ajout d'un nouvel element dans l'ABR */
  25 NOEUD *insere(NOEUD * p, element x)
  26 {
  27     if (p == NULL) {
  28         p = (NOEUD *) malloc(sizeof(NOEUD));
  29         p->valeur = x;
  30         p->gauche = NULL;
  31         p->droit = NULL;
  32     } else if (x == p->valeur)
  33         printf("%d est deja dans l'arbre\n", x);
  34     else if (x < p->valeur)
  35         p->gauche = insere(p->gauche, x);
  36     else
  37         p->droit = insere(p->droit, x);
  38     return p;
  39 }
  40
  41
  42 /* Recherche d'un element dans l'ABR */
  43 int recherche(NOEUD * p, element x)
  44 {
  45     if (p == NULL)
  46         return 0;
  47     if (x == p->valeur)
  48         return 1;
  49     if (x < p->valeur)
  50         return recherche(p->gauche, x);
  51     else
  52         return recherche(p->droit, x);
  53 }
  54
  55
  56 /* Affichage du contenu de l'ABR en ordre croissant (par parcours profondeur infixe) */
  57 void affiche(NOEUD * p)
  58 {
  59     if (p) {
  60         affiche(p->gauche);
  61         printf("%d ", p->valeur);
  62         affiche(p->droit);
  63     }
  64 }
  65
  66
  67 /* Affichage de l'arbre (sous forme arborescente) */
  68 void affiche_arbre(NOEUD * p, int col)
  69 {
  70     int i;
  71
  72     if (p) {
  73         affiche_arbre(p->droit, col + 1);
  74         for (i = 0; i < col; i++)
  75             printf("   ");
  76         printf("%d\n", p->valeur);
  77         affiche_arbre(p->gauche, col + 1);
  78     }
  79 }
  80
  81
  82 /* Copie d'arbre (on cree physiquement le double de l'arbre de racine p) */
  83 NOEUD *copie_arbre(NOEUD * p)
  84 {
  85     NOEUD *q;
  86
  87     if (p == NULL)
  88         return NULL;
  89     else {
  90         q = (NOEUD *) malloc(sizeof(NOEUD));
  91         q->valeur = p->valeur;
  92         q->gauche = copie_arbre(p->gauche);
  93         q->droit = copie_arbre(p->droit);
  94         return q;
  95     }
  96 }
  97
  98
  99 /* Destruction de l'arbre de racine p en recuperant la place occupee (free) par chacun des noeuds  */
 100 NOEUD *detruis_arbre(NOEUD * p)
 101 {
 102     if (p == NULL)
 103         return p;
 104     else {
 105         p->gauche = detruis_arbre(p->gauche);
 106         p->droit = detruis_arbre(p->droit);
 107         free(p);
 108         p = NULL;
 109         return p;
 110     }
 111 }
 112
 113
 114 /* Maximum d'un sous-arbre de racine p (i.e., le noeud le plus a droite) */
 115 NOEUD *max(NOEUD * p, NOEUD * r)
 116 {
 117     NOEUD *q;
 118
 119     if (r->droit == NULL) {
 120         p->valeur = r->valeur;
 121         q = r;                  /* q : l'element a supprimer par free */
 122         r = r->gauche;
 123         free(q);
 124     } else
 125         r->droit = max(p, r->droit);
 126     return r;
 127 }
 128
 129
 130 /* Suppression du noeud de valeur x dans l'arbre de racine p.
 131  Suppression d'un noeud interne : la valeur du noeud a supprimer est
 132  remplacee par celle du noeud le plus a droite de son sous-arbre gauche */
 133 NOEUD *supprime(NOEUD * p, element x)
 134 {
 135     NOEUD *q;
 136
 137     if (p == NULL)
 138         printf("%d  n'est pas dans l'arbre\n", x);
 139     else if (x == p->valeur) {  /* suppression de p */
 140         if (p->droit == NULL) {
 141             q = p;
 142             p = p->gauche;
 143             free(q);
 144         } else if (p->gauche == NULL) {
 145             q = p;
 146             p = p->droit;
 147             free(q);
 148         } else
 149             p->gauche = max(p, p->gauche);
 150     } else if (x < p->valeur)
 151         p->gauche = supprime(p->gauche, x);
 152     else
 153         p->droit = supprime(p->droit, x);
 154     return p;
 155 }
 156
 157
 158 /* Chargement d'un arbre depuis un fichier */
 159 NOEUD *charge(NOEUD * p, FILE * fich)
 160 {
 161     if (p) {
 162         p = (NOEUD *) malloc(sizeof(NOEUD));
 163         fread(p, sizeof(NOEUD), 1, fich);
 164         p->gauche = charge(p->gauche, fich);
 165         p->droit = charge(p->droit, fich);
 166     }
 167     return p;
 168 }
 169
 170
 171 /* Sauvegarde d'un arbre dans un fichier */
 172 NOEUD *sauve(NOEUD * p, FILE * fich)
 173 {
 174     if (p) {
 175         fwrite(p, sizeof(NOEUD), 1, fich);
 176         p->gauche = sauve(p->gauche, fich);
 177         p->droit = sauve(p->droit, fich);
 178     }
 179     return p;
 180 }
 181
 182
 183
 184
 185 /*****************************************************************************/
 186 main()
 187 {
 188     NOEUD *abr;                 /* on peut travailler sur 3 arbres */
 189     NOEUD *abr2 = NULL;
 190     char c;
 191     int i, j;
 192     element x;
 193     char nom_fich[20];
 194     FILE *fich;
 195
 196     printf
 197         ("Commandes (une lettre) possibles : v arbre_vide ; r rechercher ; i inserer ; c copier ; d detruire ; a afficher contenu ; A affiche arborescence ; s supprimer ; C charger ; S sauvegarder)\n");
 198
 199     do {
 200         printf("Commande ? ");
 201         c = getchar();
 202         switch (c) {
 203         case 'v':
 204             abr = arbre_vide();
 205             break;
 206
 207         case 'r':
 208             printf("indiquer l'element a rechercher : ");
 209             scanf("%d", &x);
 210             if (recherche(abr, x) == 0)
 211                 printf("pas trouve\n");
 212             else
 213                 printf("trouve\n");
 214             break;
 215
 216         case 'i':
 217             printf("indiquer l'element a inserer : ");
 218             scanf("%d", &x);
 219             abr = insere(abr, x);
 220             break;
 221
 222         case 'c':
 223             abr2 = copie_arbre(abr);
 224             break;
 225
 226         case 'd':
 227             abr = detruis_arbre(abr);
 228             if (abr2)
 229                 abr2 = detruis_arbre(abr2);
 230             break;
 231
 232         case 'a':
 233             affiche(abr);
 234             if (abr2) {
 235                 printf("\nLa copie : \n");
 236                 affiche(abr2);
 237             };
 238             break;
 239
 240         case 'A':
 241             affiche_arbre(abr, 1);
 242             if (abr2) {
 243                 printf("\nLa copie : \n");
 244                 affiche_arbre(abr2, 1);
 245             };
 246             break;
 247
 248         case 's':
 249             printf("indiquer l'element a supprimer : ");
 250             scanf("%d", &x);
 251             abr = supprime(abr, x);
 252             break;
 253
 254         case 'C':
 255             printf("indiquer le nom de fichier pour le chargement : ");
 256             scanf("%s", nom_fich);
 257             if ((fich = fopen(nom_fich, "rb")) != NULL) {
 258                 abr = (NOEUD *) malloc(sizeof(NOEUD));
 259                 abr = charge(abr, fich);
 260                 fclose(fich);
 261             };
 262             break;
 263
 264         case 'S':
 265             printf("indiquer le nom de fichier pour la sauvegarde : ");
 266             scanf("%s", nom_fich);
 267             if ((fich = fopen(nom_fich, "wb")) != NULL) {
 268                 abr = sauve(abr, fich);
 269                 abr = NULL;
 270                 fclose(fich);
 271             };
 272             break;
 273
 274         case 'q':
 275             exit(0);
 276         }
 277         printf("\n");
 278         c = getchar();
 279     }
 280     while (1);
 281 }
 282
 283
 284 /* Trace d'execution **************************************
 285 Commandes (une lettre) possibles : v arbre_vide ; r rechercher ; i inserer ; c copier ; d detruire ; a afficher contenu ; A affiche arborescence ; s supprimer ; C charger ; S sauvegarder)
 286 Commande ? v
 287
 288 Commande ? i
 289 indiquer l'element a inserer : 2
 290
 291 Commande ? i
 292 indiquer l'element a inserer : 6
 293
 294 Commande ? i
 295 indiquer l'element a inserer : 4
 296
 297 Commande ? i
 298 indiquer l'element a inserer : 5
 299
 300 Commande ? i
 301 indiquer l'element a inserer : 1
 302
 303 Commande ? i
 304 indiquer l'element a inserer : 0
 305
 306 Commande ? a
 307 0 1 2 4 5 6
 308 Commande ? A
 309       6
 310             5
 311          4
 312    2
 313       1
 314          0
 315
 316 Commande ? r
 317 indiquer l'element a rechercher : 4
 318 trouve
 319
 320 Commande ? r
 321 indiquer l'element a rechercher : 3
 322 pas trouve
 323
 324 Commande ? s
 325 indiquer l'element a supprimer : 4
 326
 327 Commande ? a
 328 0 1 2 5 6
 329 Commande ? A
 330       6
 331          5
 332    2
 333       1
 334          0
 335
 336 Commande ? S
 337 indiquer le nom de fichier pour la sauvegarde : sauv.txt
 338
 339 Commande ? C
 340 indiquer le nom de fichier pour le chargement : sauv.txt
 341
 342 Commande ? a
 343 0 1 2 5 6
 344 Commande ? A
 345       6
 346          5
 347    2
 348       1
 349          0
 350
 351 Commande ? q
 352
 353 ******************************************************************************/