--- /dev/null
+/*****************************************************************************/
+/* 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
+
+******************************************************************************/
repositories / Algorithmic_C.git / blobdiff