| 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 | ******************************************************************************/ |