Accueil > > > ARBRE BINAIRE RÉCURISIVITÉ C
ARBRE BINAIRE RÉCURISIVITÉ C
Information sur la source
Description
Création d'un arbre binaire, affichage, suppression d'un noeud...
Source
- /*******************************************************
- * 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();
- }
- }
/*******************************************************
* 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
Sources du même auteur
Sources de la même categorie
Commentaires et avis
|
Derniers Blogs
VOTEZ POUR LE TOP 10 DES INFLUENCEURS SHAREPOINT FRANCOPHONES !VOTEZ POUR LE TOP 10 DES INFLUENCEURS SHAREPOINT FRANCOPHONES ! par Patrick Guimonet
Si ce n'est déjà fait (comme plus de 600 personnes déjà), il est encore temps de voter pour le concours TOP 10 des influenceurs SharePoint francophones ! Il est organisé par harmon.ie et accessible ici : http://harmon.ie/top-...
Cliquez pour lire la suite de l'article par Patrick Guimonet [CONF'SHAREPOINT] DERNIER RAPPEL ! :-)[CONF'SHAREPOINT] DERNIER RAPPEL ! :-) par Patrick Guimonet
La Conf'SharePoint en chiffres c'est : 3 jours de SharePoint ! 4 parcours et 60 sessions 17 partenaires représentant toutes les fac...
Cliquez pour lire la suite de l'article par Patrick Guimonet [ #SHAREPOINT 2013 ] LES MODèLES DE SITES STANDARDS.[ #SHAREPOINT 2013 ] LES MODèLES DE SITES STANDARDS. par Patrick Guimonet
C'est un point peu mis en avant mais SharePoint 2013 a été l'occasion de remettre de l'ordre dans les modèles de sites. Tout d'abord, un certain nombre de modèles ont été tout simplement rendus obsolètes (cf. Fonctionnalités déco...
Cliquez pour lire la suite de l'article par Patrick Guimonet 10 ERREURS DE COMPRéHENSION CONCERNANT SHAREPOINT.10 ERREURS DE COMPRéHENSION CONCERNANT SHAREPOINT. par Patrick Guimonet
Une excellente infographie (qui a sa source ici :http://www.evokeit.com/sharepoint-blog/misconceptions-of-microsoft-sharepoint) que j'ai traduite et commentée sur le blog d'Abalon : http://abalon.fr/blog/10-erreurs-de-comprhension-...
Cliquez pour lire la suite de l'article par Patrick Guimonet
Forum
RE : JEU SDLRE : JEU SDL par yahayaass
Cliquez pour lire la suite par yahayaass
Logiciels
Devis-Factures PHMSD (2.1.0.1)DEVIS-FACTURES PHMSD (2.1.0.1)Configuration minimale
Nécessite Windows™ 2000, XP, Windows 7, 8, Vista (Service Pack à... Cliquez pour télécharger Devis-Factures PHMSD Ludoprêt (3.2)LUDOPRêT (3.2)Logiciel gratuit de gestion de ludothèque.
Gestion des jeux et des adhérents.
Gestion des for... Cliquez pour télécharger Ludoprêt Revealer Keylogger Free (2.05)REVEALER KEYLOGGER FREE (2.05)Keylogger invisible et gratuit pour Windows 8, 7, Vista ou XP. Revealer Keylogger Free vous perme... Cliquez pour télécharger Revealer Keylogger Free 974 Application Server (13.2.1.3)974 APPLICATION SERVER (13.2.1.3)Ecommerce, Blogueur, Vitrine, Newsletter, Java IDE, ..., in the cloud et sous haute dispo. Facile... Cliquez pour télécharger 974 Application Server WDmemoCode (1.0.0)WDMEMOCODE (1.0.0)WDmemoCode a été créé pour aider les développeurs Windev à créer/compléter et conserver une base ... Cliquez pour télécharger WDmemoCode
|