Arbre binaire récurisivité c

Soyez le premier à donner votre avis sur cette source.

Snippet vu 48 739 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

Messages postés
4
Date d'inscription
mercredi 5 mars 2014
Statut
Membre
Dernière intervention
22 mars 2014

svp j'ai un grand problème je doit écrire un dictionnaire baser sur les arbres binaire de recherche en utilisant les fichier en langage C
et je voudrai votre aide comment je commence
Messages postés
14854
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
11 octobre 2020
444 >
Messages postés
4
Date d'inscription
mercredi 5 mars 2014
Statut
Membre
Dernière intervention
22 mars 2014

Bonjour,
Merci de garder à l'esprit que CodeS-SourceS est une communauté d'entraide. Toutes les réponses sur le forum sont assurées par des bénévoles qui donnent de leur temps libre pour aider à résoudre les problèmes.
A noter également que nous ne faisons pas dans le "tout cuit".

Soit tu trouves ton bonheur avec ce code, soit tu viens poser un question sur le forum ou nous aidons volontiers sur une difficulté technique, précise et parfaitement isolée rencontrée dans le cours du développement.

Ici http://codes-sources.commentcamarche.net/forum/affich-1557761-bar-sujet-de-pfe-tp-et-autres-devoirs-scolaires#top et là http://codes-sources.commentcamarche.net/contents/11-charte-de-commentcamarche-net-conseils-d-ecriture des conseils d'écriture des messages.

Ici http://codes-sources.commentcamarche.net/faq/10686-le-nouveau-codes-sources-comment-ca-marche#balises-code comment utiliser la coloration syntaxique.

Et enfin, le plus important, Bonjour, S'il vous plait, et Merci sont des petits mots qui permettent d'obtenir plus facilement une réponse.

Merci donc de reformuler ta demande en respectant ces quelques points.
Messages postés
2
Date d'inscription
mercredi 18 janvier 2012
Statut
Membre
Dernière intervention
18 avril 2014

merci
Messages postés
1
Date d'inscription
jeudi 6 octobre 2011
Statut
Membre
Dernière intervention
9 novembre 2011

salut
je veux just dire que la fonction de recherche sa marche par dans le cas une valeur n'existe pas dans l'arbre (si on chererche dans une arbre ne contien pas la valeur donner)
pour sa tu doit ajoutter
if((RepRecherche!=NULL)&&(RepRecherche->Noeud==valeur)) dans la fontion main
au lieu de if(RepRecherche->Noeud==valeur)
bey
Messages postés
2
Date d'inscription
jeudi 18 juin 2009
Statut
Membre
Dernière intervention
18 juin 2009

Le code de suppression ne semble pas fonctionner (segfault)
Afficher les 11 commentaires

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.