6064c006a8543035227ed670c86d66a3deac83d0
1 /*****************************************************************************/
2 /* ABR : arbres binaires de recherche */
3 /*****************************************************************************/
10 typedef struct noeud
{
17 /* Creation d'un ABR vide */
24 /* Insertion/Ajout d'un nouvel element dans l'ABR */
25 NOEUD
*insere(NOEUD
*p
, element x
)
29 p
= (NOEUD
*)malloc(sizeof(NOEUD
));
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
);
41 /* Recherche d'un element dans l'ABR */
42 int recherche(NOEUD
*p
, element x
)
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
);
51 /* Affichage du contenu de l'ABR en ordre croissant (par parcours profondeur infixe) */
52 void affiche(NOEUD
*p
)
57 printf("%d ",p
->valeur
);
63 /* Affichage de l'arbre (sous forme arborescente) */
64 void affiche_arbre(NOEUD
*p
, int col
)
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);
77 /* Copie d'arbre (on cree physiquement le double de l'arbre de racine p) */
78 NOEUD
*copie_arbre(NOEUD
*p
)
81 if(p
== NULL
) return NULL
;
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
);
93 /* Destruction de l'arbre de racine p en recuperant la place occupee (free) par chacun des noeuds */
94 NOEUD
*detruis_arbre(NOEUD
*p
)
96 if(p
== NULL
) return p
;
99 p
->gauche
= detruis_arbre(p
->gauche
);
100 p
->droit
= detruis_arbre(p
->droit
);
108 /* Maximum d'un sous-arbre de racine p (i.e., le noeud le plus a droite) */
109 NOEUD
*max(NOEUD
*p
, NOEUD
*r
)
112 if (r
->droit
== NULL
)
114 p
->valeur
= r
->valeur
;
115 q
= r
; /* q : l'element a supprimer par free */
119 else r
->droit
= max(p
,r
->droit
);
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
)
130 if(p
== NULL
) printf("%d n'est pas dans l'arbre\n",x
);
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
);
138 else if (x
< p
->valeur
) p
->gauche
= supprime(p
->gauche
,x
);
139 else p
->droit
= supprime(p
->droit
,x
);
144 /* Chargement d'un arbre depuis un fichier */
145 NOEUD
*charge(NOEUD
*p
, FILE *fich
)
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
);
156 /* Sauvegarde d'un arbre dans un fichier */
157 NOEUD
*sauve(NOEUD
*p
, FILE *fich
)
159 if (p
) {fwrite(p
,sizeof(NOEUD
),1,fich
);
160 p
->gauche
= sauve(p
->gauche
,fich
);
161 p
->droit
= sauve(p
->droit
,fich
);
169 /*****************************************************************************/
172 NOEUD
*abr
; /* on peut travailler sur 3 arbres */
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");
183 printf("Commande ? ");
187 case 'v' : abr
= arbre_vide(); break;
189 case 'r' : printf("indiquer l'element a rechercher : ");
191 if (recherche(abr
,x
) == 0) printf("pas trouve\n");
192 else printf("trouve\n");
195 case 'i' : printf("indiquer l'element a inserer : ");
200 case 'c' : abr2
= copie_arbre(abr
);
203 case 'd' : abr
= detruis_arbre(abr
);
204 if(abr2
) abr2
= detruis_arbre(abr2
);
207 case 'a' : affiche(abr
);
208 if(abr2
) {printf("\nLa copie : \n");
212 case 'A' : affiche_arbre(abr
,1);
213 if(abr2
) {printf("\nLa copie : \n");
214 affiche_arbre(abr2
,1);};
217 case 's' : printf("indiquer l'element a supprimer : ");
219 abr
= supprime(abr
,x
);
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
);
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
);
242 printf("\n"); c
= getchar();
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)
253 indiquer l'element a inserer : 2
256 indiquer l'element a inserer : 6
259 indiquer l'element a inserer : 4
262 indiquer l'element a inserer : 5
265 indiquer l'element a inserer : 1
268 indiquer l'element a inserer : 0
281 indiquer l'element a rechercher : 4
285 indiquer l'element a rechercher : 3
289 indiquer l'element a supprimer : 4
301 indiquer le nom de fichier pour la sauvegarde : sauv.txt
304 indiquer le nom de fichier pour le chargement : sauv.txt
317 ******************************************************************************/