[Algorithmic_C.git] / TP6 / arbres / ABR / ABR.c

/*****************************************************************************/
/*                      ABR : arbres binaires de recherche                   */
/*****************************************************************************/

#include <stdio.h>
#include <stdlib.h>

typedef int element;

typedef struct noeud {
 element valeur;
 struct noeud *gauche;
 struct noeud *droit;
} NOEUD, *ABR;


/* Creation d'un ABR vide */
NOEUD *arbre_vide() 
{
 return NULL;
}


/* Insertion/Ajout d'un nouvel element dans l'ABR */
NOEUD *insere(NOEUD *p, element x)
{
 if(p == NULL) 
 {
  p = (NOEUD *)malloc(sizeof(NOEUD));
  p->valeur = x;
  p->gauche = NULL;
  p->droit = NULL;
 }
 else if (x == p->valeur) printf("%d est deja dans l'arbre\n",x);
      else if (x < p->valeur)  p->gauche = insere(p->gauche,x);
           else p->droit  = insere(p->droit,x);			  
 return p;			  
}


/* Recherche d'un element dans l'ABR */
int recherche(NOEUD *p, element x)
{
 if(p == NULL) return 0;
 if(x == p->valeur) return 1;
 if(x < p->valeur) return recherche(p->gauche,x);
 else return recherche(p->droit,x);
}


/* Affichage du contenu de l'ABR en ordre croissant (par parcours profondeur infixe) */
void affiche(NOEUD *p)
{
 if(p)
 {
  affiche(p->gauche);
  printf("%d ",p->valeur);
  affiche(p->droit);
 }  	
}


/* Affichage de l'arbre (sous forme arborescente) */
void affiche_arbre(NOEUD *p, int col)
{
 int i;
 if(p)
 {
  affiche_arbre(p->droit,col+1);
  for (i=0;i<col;i++) printf("   ");
  printf("%d\n",p->valeur);
  affiche_arbre(p->gauche,col+1);
 }  	
}


/* Copie d'arbre (on cree physiquement le double de l'arbre de racine p) */
NOEUD *copie_arbre(NOEUD *p) 
{
 NOEUD *q;
 if(p == NULL) return NULL;
 else 
  {
   q = (NOEUD *)malloc(sizeof(NOEUD));
   q->valeur = p->valeur;
   q->gauche = copie_arbre(p->gauche);
   q->droit  = copie_arbre(p->droit);
   return q;
  }
} 


/* Destruction de l'arbre de racine p en recuperant la place occupee (free) par chacun des noeuds  */
NOEUD *detruis_arbre(NOEUD *p)
{
 if(p == NULL) return p;
 else
  {
   p->gauche = detruis_arbre(p->gauche);
   p->droit  = detruis_arbre(p->droit);
   free(p);
   p = NULL;
   return p;
  }
}


/* Maximum d'un sous-arbre de racine p (i.e., le noeud le plus a droite) */
NOEUD *max(NOEUD *p, NOEUD *r)
{
 NOEUD *q;
 if (r->droit == NULL) 
 {
  p->valeur = r->valeur;
  q = r; /* q : l'element a supprimer par free */
  r = r->gauche;
  free(q);
 }
 else r->droit = max(p,r->droit);
 return r;
}


/* Suppression du noeud de valeur x dans l'arbre de racine p.
 Suppression d'un noeud interne : la valeur du noeud a supprimer est
 remplacee par celle du noeud le plus a droite de son sous-arbre gauche */
NOEUD *supprime(NOEUD *p, element x)
{
 NOEUD *q;
 if(p == NULL) printf("%d  n'est pas dans l'arbre\n",x);
 else
   if(x == p->valeur)
     { /* suppression de p */
      if (p->droit == NULL) {q = p ; p = p->gauche; free(q); }
      else if (p->gauche == NULL) {q = p ; p = p->droit; free (q); }
           else p-> gauche = max(p,p->gauche);
     }
   else if (x < p->valeur) p->gauche = supprime(p->gauche,x);
        else p->droit  = supprime(p->droit,x);
 return p;
}


/* Chargement d'un arbre depuis un fichier */
NOEUD *charge(NOEUD *p, FILE *fich)
{
 if (p) {p = (NOEUD *)malloc(sizeof(NOEUD));
         fread(p,sizeof(NOEUD),1,fich);
	 p->gauche = charge(p->gauche,fich);
	 p->droit =  charge(p->droit,fich);
        }
 return p;
}


/* Sauvegarde d'un arbre dans un fichier */
NOEUD *sauve(NOEUD *p, FILE *fich)
{
 if (p) {fwrite(p,sizeof(NOEUD),1,fich);
	 p->gauche = sauve(p->gauche,fich);
	 p->droit =  sauve(p->droit,fich);
        }
 return p;
}


/*****************************************************************************/
main()
{
 NOEUD *abr; /* on peut travailler sur 3 arbres */
 NOEUD *abr2 = NULL;
 char c;
 int i, j;
 element x;
 char nom_fich[20];
 FILE *fich;

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");

 do {
     printf("Commande ? "); 
     c = getchar();
     switch(c)
     {
      case 'v' : abr = arbre_vide(); break;

      case 'r' : printf("indiquer l'element a rechercher : ");
		 scanf("%d",&x);
                 if (recherche(abr,x) == 0) printf("pas trouve\n");
                 else printf("trouve\n"); 
		 break;

      case 'i' : printf("indiquer l'element a inserer : ");
		 scanf("%d",&x); 
		 abr = insere(abr,x); 
		 break;

      case 'c' : abr2 = copie_arbre(abr); 
		 break;

      case 'd' : abr = detruis_arbre(abr); 
		 if(abr2) abr2 = detruis_arbre(abr2); 
		 break;

      case 'a' : affiche(abr); 
		 if(abr2) {printf("\nLa copie : \n"); 
	 	           affiche(abr2);}; 
		 break;

      case 'A' : affiche_arbre(abr,1); 
		 if(abr2) {printf("\nLa copie : \n"); 
			   affiche_arbre(abr2,1);}; 
		 break;     

      case 's' : printf("indiquer l'element a supprimer : ");
		 scanf("%d",&x); 
		 abr = supprime(abr,x); 
		 break;

      case 'C' : printf("indiquer le nom de fichier pour le chargement : ");
		 scanf("%s",nom_fich);
                 if ((fich = fopen(nom_fich,"rb")) != NULL) 
		  {abr =  (NOEUD *)malloc(sizeof(NOEUD));
		   abr = charge(abr,fich);
		   fclose(fich);
		  };
		 break;
      
      case 'S' : printf("indiquer le nom de fichier pour la sauvegarde : ");
		 scanf("%s",nom_fich);
                 if ((fich = fopen(nom_fich,"wb")) != NULL) 
		  {abr = sauve(abr,fich);
		   abr = NULL;
		   fclose(fich);
		  };  
		 break;

      case 'q' : exit(0); 
     }
     printf("\n"); c = getchar();
 }
 while (1);
}


/* Trace d'execution ************************************** 	
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)
Commande ? v

Commande ? i
indiquer l'element a inserer : 2

Commande ? i
indiquer l'element a inserer : 6

Commande ? i
indiquer l'element a inserer : 4

Commande ? i
indiquer l'element a inserer : 5

Commande ? i
indiquer l'element a inserer : 1

Commande ? i
indiquer l'element a inserer : 0

Commande ? a
0 1 2 4 5 6 
Commande ? A
      6
            5
         4
   2
      1
         0

Commande ? r
indiquer l'element a rechercher : 4
trouve

Commande ? r
indiquer l'element a rechercher : 3
pas trouve

Commande ? s
indiquer l'element a supprimer : 4

Commande ? a
0 1 2 5 6 
Commande ? A
      6
         5
   2
      1
         0

Commande ? S
indiquer le nom de fichier pour la sauvegarde : sauv.txt

Commande ? C
indiquer le nom de fichier pour le chargement : sauv.txt

Commande ? a
0 1 2 5 6 
Commande ? A
      6
         5
   2
      1
         0

Commande ? q

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