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