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