begin process at 2008 07 05 07:13:58
1 205 054 membres
40 nouveaux aujourd'hui
14 118 membres club

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum.
Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

ARBRE BINAIRE RÉCURISIVITÉ C


Information sur la source

Catégorie :.Net Niveau : Débutant Date de création : 07/01/2003 Date de mise à jour : 07/01/2003 16:08:53 Vu : 13 013

Note :
5,83 / 10 - par 6 personnes
5,83 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

Commentaire sur cette source (7)
Ajouter un commentaire et/ou une note

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
  • signaler à un administrateur
    Commentaire de LordBob le 07/01/2003 21:43:24

    est ce ke tu peux résumer ce ke fait ta source... car pour moi c pas tres clair...

  • signaler à un administrateur
    Commentaire de fred33 le 31/01/2003 22:06:42

    Simple, concis... Ce code est bienvenue.

  • signaler à un administrateur
    Commentaire de watchabongo le 15/01/2004 20:50:57

    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

  • signaler à un administrateur
    Commentaire de watchabongo le 15/01/2004 20:51:48

    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

  • signaler à un administrateur
    Commentaire de crbtarek le 23/01/2004 15:30:51

    Bonjour
    il y'a pas une vérification pour les élements saisis??

  • signaler à un administrateur
    Commentaire de elbougouma le 03/04/2008 01:20:40

    Bon travail mais si tu y avais mis l'affichage par niveau ainsi que les testes pour les erreurs ça serait coooooool.

  • signaler à un administrateur
    Commentaire de alatox le 06/06/2008 20:30:32

    Le code de suppression ne semble pas fonctionner (segfault)

Ajouter un commentaire

Pub



Appels d'offres

CalendriCode

Juillet 2008
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Boutique

Boutique de goodies CodeS-SourceS