Arbre binaire récurisivité c

Soyez le premier à donner votre avis sur cette source.

Snippet vu 45 696 fois - Téléchargée 34 fois

Contenu du snippet

Création d'un arbre binaire, affichage, suppression d'un noeud...

Source / Exemple :


/*******************************************************

  • Langage C TP6.2 10/12/2002 *
  • Ecrire les algorithmes traitant quelques opération *
  • concernant les arbres binaires ordonnés. *
  • *
                                                                                                              • /
#include <stdio.h> #include <stdlib.h> #include <conio.h> typedef struct Arbre { int Noeud; struct Arbre * SAG; struct Arbre * SAD; } Arbre; AfficherArbreCroissant(Arbre * Racine) { if (Racine!=NULL) { AfficherArbreCroissant(Racine->SAG); printf("%d ",Racine->Noeud); AfficherArbreCroissant(Racine->SAD); } } Arbre * CreerNoeud(Arbre * Racine,int valeur) { if (Racine!=NULL) { if (Racine->Noeud>valeur) { Racine->SAG=CreerNoeud(Racine->SAG,valeur); } else { Racine->SAD=CreerNoeud(Racine->SAD,valeur); } } else { Racine=(Arbre *)malloc(sizeof(Arbre)); Racine->Noeud=valeur; Racine->SAD=NULL; Racine->SAG=NULL; } return Racine; } AfficherArbre(Arbre * Racine) { if (Racine!=NULL) { printf("%d ",Racine->Noeud); if (Racine->SAD!=NULL || Racine->SAG!=NULL) { AfficherArbre(Racine->SAG); AfficherArbre(Racine->SAD); } } } EnregArbre(Arbre * Racine,char * NomFic) { int nb; FILE * fic; fic=fopen(NomFic,"at"); if (Racine!=NULL) { nb=Racine->Noeud; fwrite(&nb,sizeof(int),1,fic); fclose(fic); if (Racine->SAD!=NULL || Racine->SAG!=NULL) { EnregArbre(Racine->SAG,NomFic); EnregArbre(Racine->SAD,NomFic); } } } Arbre * ChargerArbre(Arbre * Racine,char * NomFic) { int nb; FILE * fic; fic=fopen(NomFic,"rt"); fread(&nb,sizeof(int),1,fic); while (!feof(fic)) { Racine = CreerNoeud(Racine,nb); fread(&nb,sizeof(int),1,fic); } fclose(fic); return Racine; } AfficherArbreDecroissant(Arbre * Racine) { if (Racine!=NULL) { AfficherArbreDecroissant(Racine->SAD); printf("%d ",Racine->Noeud); AfficherArbreDecroissant(Racine->SAG); } } int Somme(Arbre * Racine) { int total=0; if (Racine!=NULL) { total=Somme(Racine->SAG); total+=Racine->Noeud; total+=Somme(Racine->SAD); } return total; } int CompteNoeud(Arbre * Racine) { int total=0; if (Racine!=NULL) { total=CompteNoeud(Racine->SAG); total++; total+=CompteNoeud(Racine->SAD); } return total; } Arbre * RechercheNoeud(Arbre * Racine, int valeur) { if (Racine!=NULL) { if (Racine->Noeud>valeur) { Racine=RechercheNoeud(Racine->SAG,valeur); } else { if (Racine->Noeud<valeur) { Racine=RechercheNoeud(Racine->SAD,valeur); } } return Racine; } } Arbre * OterNoeud(Arbre * Racine, int valeur) { Arbre * NoeudASupprimer; if (Racine->Noeud==valeur) // on a trouvé l'élément à supprimer { NoeudASupprimer=Racine; if (NoeudASupprimer->SAG==NULL) //si ya pa de SAG, on retourne SAD return NoeudASupprimer->SAD; else { Racine=NoeudASupprimer->SAG; //sinon on recherche dans SAG l'endroit pour insérer le SAD while (Racine->SAD!=NULL) { Racine=Racine->SAD; } Racine->SAD=NoeudASupprimer->SAD; return NoeudASupprimer->SAG; } free(NoeudASupprimer); } else { if (Racine->Noeud>valeur) { Racine->SAG=OterNoeud(Racine->SAG,valeur); } else { Racine->SAD=OterNoeud(Racine->SAD,valeur); } } return Racine; } int Menu() { int Choix; do { system("cls"); //efface l'écran printf(" ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n"); printf(" º º\n"); printf(" º Menu Principal º\n"); printf(" º º\n"); printf(" ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n"); printf("\n 1- Ajouter un noeud"); printf("\n 2- Afficher l'arbre"); printf("\n 3- Afficher l'arbre dans l'ordre croissant"); printf("\n 4- Afficher l'arbre dans l'ordre decroissant"); printf("\n 5- Somme des noeuds"); printf("\n 6- Nombre de noeuds"); printf("\n 7- Rechercher un noeud"); printf("\n 8- Enlever un noeud"); printf("\n 9- Enregister l'arbre dans un fichier"); printf("\n 10- Charger l'arbre \205 partir d'un fichier"); printf("\n 11- Quitter\n"); printf("\n\n\n\n\n\n\nChoix :"); scanf("%d",&Choix); } while (Choix <1 || Choix >11); system("cls"); return Choix; } main() { int valeur; int Choix; char * NomFic="Fic.txt"; Arbre * Racine; Arbre * RepRecherche; Racine=NULL; Choix = Menu(); while (Choix!=11) { if (Racine==NULL && Choix>1 && Choix <10) { printf("Vous devez d'abord saisir un arbre"); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); } else { switch (Choix) { case 1 : printf("Saisir un entier (0 pour finir la saisie) : "); scanf("%d",&valeur); while (valeur != 0) { Racine=CreerNoeud(Racine,valeur); printf("Saisir un entier (0 pour finir la saisie) : "); scanf("%d",&valeur); } break; case 2 : AfficherArbre(Racine); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; case 3 : AfficherArbreCroissant(Racine); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; case 4 : AfficherArbreDecroissant(Racine); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; case 5 : AfficherArbreCroissant(Racine); printf("\nTotal : %d",Somme(Racine)); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; case 6 : AfficherArbreCroissant(Racine); printf("\nTotal : %d",CompteNoeud(Racine)); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; case 7 : printf("Saisir la valeur \205 rechercher : "); scanf("%d", &valeur); RepRecherche=RechercheNoeud(Racine,valeur); if (RepRecherche->Noeud==valeur) { printf("%d", RepRecherche->Noeud); } else { printf("Impossible de trouver la valeur recherch\202e"); } printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; case 8 : printf("Saisir la valeur du noeud \205 supprimer : \n"); scanf("%d",&valeur); Racine=OterNoeud(Racine,valeur); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; case 9 : system("del Fic.txt"); system("cls"); EnregArbre(Racine,NomFic); printf("Arbre enregistr\202\n"); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; case 10 : Racine=ChargerArbre(Racine,NomFic); printf("Arbre charg\202\n"); printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nAppuyez sur une touche pour retourner au menu principal"); getch(); break; } } Choix=Menu(); } }

Conclusion :


Reste plus qu'a faire l'affichage par niveau

A voir également

Ajouter un commentaire

Commentaires

cs_LordBob
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
8 -
est ce ke tu peux résumer ce ke fait ta source... car pour moi c pas tres clair...
cs_fred33
Messages postés
9
Date d'inscription
vendredi 17 janvier 2003
Statut
Membre
Dernière intervention
14 juin 2007
-
Simple, concis... Ce code est bienvenue.
watchabongo
Messages postés
6
Date d'inscription
mercredi 29 janvier 2003
Statut
Membre
Dernière intervention
31 mars 2005
-
Bien pour une fois qu'un code est concis (;
c'est toujours mieux en recursif
par contre tu parles d'arbre ordonné tu veux dire AVL ?
pasque il me semble pas que c'est le cas la
il manque toutes les permutations? DD GG DG GD
C'est seulement un ABOH dis moi si je me trompe
watchabongo
Messages postés
6
Date d'inscription
mercredi 29 janvier 2003
Statut
Membre
Dernière intervention
31 mars 2005
-
Bien pour une fois qu'un code est concis (;
c'est toujours mieux en recursif
par contre tu parles d'arbre ordonné tu veux dire AVL ?
pasque il me semble pas que c'est le cas la
il manque toutes les permutations? DD GG DG GD
C'est seulement un ABOH dis moi si je me trompe
crbtarek
Messages postés
1
Date d'inscription
jeudi 22 janvier 2004
Statut
Membre
Dernière intervention
23 janvier 2004
-
Bonjour
il y'a pas une vérification pour les élements saisis??

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.