Refine .gitignore some more.
[Algorithmic_C.git] / 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 ******************************************************************************/