Commit | Line | Data |
---|---|---|
5f72f302 JB |
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 { | |
760a8310 JB |
11 | element valeur; |
12 | struct noeud *gauche; | |
13 | struct noeud *droit; | |
5f72f302 JB |
14 | } NOEUD, *ABR; |
15 | ||
16 | ||
17 | /* Creation d'un ABR vide */ | |
760a8310 | 18 | NOEUD *arbre_vide() |
5f72f302 | 19 | { |
760a8310 | 20 | return NULL; |
5f72f302 JB |
21 | } |
22 | ||
23 | ||
24 | /* Insertion/Ajout d'un nouvel element dans l'ABR */ | |
760a8310 | 25 | NOEUD *insere(NOEUD * p, element x) |
5f72f302 | 26 | { |
760a8310 JB |
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; | |
5f72f302 JB |
39 | } |
40 | ||
41 | ||
42 | /* Recherche d'un element dans l'ABR */ | |
760a8310 | 43 | int recherche(NOEUD * p, element x) |
5f72f302 | 44 | { |
760a8310 JB |
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); | |
5f72f302 JB |
53 | } |
54 | ||
55 | ||
56 | /* Affichage du contenu de l'ABR en ordre croissant (par parcours profondeur infixe) */ | |
760a8310 | 57 | void affiche(NOEUD * p) |
5f72f302 | 58 | { |
760a8310 JB |
59 | if (p) { |
60 | affiche(p->gauche); | |
61 | printf("%d ", p->valeur); | |
62 | affiche(p->droit); | |
63 | } | |
5f72f302 JB |
64 | } |
65 | ||
66 | ||
67 | /* Affichage de l'arbre (sous forme arborescente) */ | |
760a8310 | 68 | void affiche_arbre(NOEUD * p, int col) |
5f72f302 | 69 | { |
760a8310 JB |
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 | } | |
5f72f302 JB |
79 | } |
80 | ||
81 | ||
82 | /* Copie d'arbre (on cree physiquement le double de l'arbre de racine p) */ | |
760a8310 | 83 | NOEUD *copie_arbre(NOEUD * p) |
5f72f302 | 84 | { |
760a8310 JB |
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 | } | |
5f72f302 JB |
97 | |
98 | ||
99 | /* Destruction de l'arbre de racine p en recuperant la place occupee (free) par chacun des noeuds */ | |
760a8310 | 100 | NOEUD *detruis_arbre(NOEUD * p) |
5f72f302 | 101 | { |
760a8310 JB |
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 | } | |
5f72f302 JB |
111 | } |
112 | ||
113 | ||
114 | /* Maximum d'un sous-arbre de racine p (i.e., le noeud le plus a droite) */ | |
760a8310 | 115 | NOEUD *max(NOEUD * p, NOEUD * r) |
5f72f302 | 116 | { |
760a8310 JB |
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; | |
5f72f302 JB |
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 */ | |
760a8310 | 133 | NOEUD *supprime(NOEUD * p, element x) |
5f72f302 | 134 | { |
760a8310 JB |
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; | |
5f72f302 JB |
155 | } |
156 | ||
157 | ||
158 | /* Chargement d'un arbre depuis un fichier */ | |
760a8310 | 159 | NOEUD *charge(NOEUD * p, FILE * fich) |
5f72f302 | 160 | { |
760a8310 JB |
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; | |
5f72f302 JB |
168 | } |
169 | ||
170 | ||
171 | /* Sauvegarde d'un arbre dans un fichier */ | |
760a8310 | 172 | NOEUD *sauve(NOEUD * p, FILE * fich) |
5f72f302 | 173 | { |
760a8310 JB |
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; | |
5f72f302 JB |
180 | } |
181 | ||
182 | ||
183 | ||
184 | ||
185 | /*****************************************************************************/ | |
186 | main() | |
187 | { | |
760a8310 JB |
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); | |
5f72f302 JB |
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 | ******************************************************************************/ |