X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=TP6%2Farbres%2FABR%2FABR.c;h=b5d3956837b5142602630894d0a4282178752685;hb=760a83108ff8caa7036c81d21d4dc4581de98860;hp=6064c006a8543035227ed670c86d66a3deac83d0;hpb=e06ddf2d662693efef1a0060797f169947ff3d9d;p=Algorithmic_C.git

diff --git a/TP6/arbres/ABR/ABR.c b/TP6/arbres/ABR/ABR.c
index 6064c00..b5d3956 100644
--- a/TP6/arbres/ABR/ABR.c
+++ b/TP6/arbres/ABR/ABR.c
@@ -8,159 +8,175 @@
 typedef int element;
 
 typedef struct noeud {
- element valeur;
- struct noeud *gauche;
- struct noeud *droit;
+    element valeur;
+    struct noeud *gauche;
+    struct noeud *droit;
 } NOEUD, *ABR;
 
 
 /* Creation d'un ABR vide */
-NOEUD *arbre_vide() 
+NOEUD *arbre_vide()
 {
- return NULL;
+    return NULL;
 }
 
 
 /* Insertion/Ajout d'un nouvel element dans l'ABR */
-NOEUD *insere(NOEUD *p, element x)
+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;			  
+    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)
+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);
+    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)
+void affiche(NOEUD * p)
 {
- if(p)
- {
-  affiche(p->gauche);
-  printf("%d ",p->valeur);
-  affiche(p->droit);
- }  	
+    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)
+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);
- }  	
+    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 *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;
-  }
-} 
+    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)
+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;
-  }
+    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 *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;
+    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 *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;
+    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)
+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;
+    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)
+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;
+    if (p) {
+	fwrite(p, sizeof(NOEUD), 1, fich);
+	p->gauche = sauve(p->gauche, fich);
+	p->droit = sauve(p->droit, fich);
+    }
+    return p;
 }
 
 
@@ -169,79 +185,99 @@ NOEUD *sauve(NOEUD *p, FILE *fich)
 /*****************************************************************************/
 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);
+    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);
 }