Arbre binaire

Commenter

Contenu du snippet

c'est un programme qui montre les différentes fonctions de manipulation d'arbres binaires .
parcours,ajout...

Source / Exemple : 


#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
  struct cellule
		{
		int val ;
		struct cellule  *gch ;
      struct cellule *drt;
		};

typedef struct cellule   *arbre ; //arbre defenie comme type pointeur de cellule
void prefixer(arbre);
arbre creefeuille(int);
void infixer(arbre);
void postfixer(arbre);
int hauteur (arbre);
int taille(arbre);
void recherche(int ,arbre );
arbre ajout(int ,arbre);
void attacher_new(arbre ,arbre );
arbre ajout_new(int ,arbre );
arbre cons(int x, arbre G, arbre D )
	{
		arbre A = ( arbre ) malloc( sizeof( cellule )) ;
		A -> val = x ;
		A -> gch = G ;
		A -> drt = D ;
		return A ;
	}

arbre cree_racine(int x)
{

 arbre A = ( arbre ) malloc( sizeof( cellule )) ;
    A->val=x;
    A->gch=NULL;
    A->drt=NULL;
    return A;
}

void afficher_arbre (arbre A)
{
 if(A!=NULL)
  {
   afficher_arbre(A->drt);
   printf("%d\t",A->val);
   afficher_arbre(A->gch);

  }
}

              void main()
           {
           do
             {
           int x,choix,s,s1,el;
          arbre fd1;
          arbre r;
         arbre fg1,fg2,r1,r2,fd2;
        printf("si vous voulez :");
         printf("\n\n\ncreer un arbre  1.\n\nafficher l'arbre 2.\n\nexploration prefixer 3.\n\nexploration infixer 4.");
         printf("\n\nexploration postfixer 5.\n\ndeterminer la hauteur de l'arbre 6.\n\ndeterminer la taille de l'arbre 7.\n\nrechercher un element dans l'arbre 8.\n\najouter un element à l'arbre 9.\n\nnb d'occurence d'un element donnée 10.\n\n");
         gotoxy(29,25); printf("tapper votre choix ici :");scanf("%d",&choix);
         clrscr();

        switch (choix)
          {
           case 1:
          // printf("entrer un elt ");
          //scanf("%d",&x);

            fd1=creefeuille( 4);
               fg1=creefeuille(1)   ;
                r1=cons(3,fg1,fd1);
                 fd2=creefeuille( 8);
               //fg2=creefeuille(6)   ;
                r2=cons(7,NULL,fd2);
                 r=cons(5,r1,r2);
                 printf("l'arbre est construit avec succé ");break ;
         case 2:    afficher_arbre ( r);break;
         case 3:prefixer(r);printf("\nc'est le parcour prefixer");break;
         case 4:infixer(r);printf("\nc'est le parcour infixer");break;
         case 5:postfixer(r);printf("\nc'est le parcour postfixer");break;
         case 6:s=hauteur(r);
                printf("\nla hauteur de l'arbre est :%d ",s); break;
         case 7:s1=taille(r);
                printf("la taille de l'arbre est :%d",s1); break;
         case 8:printf("entrer l'elt rechercher: ");
                scanf("%d",&el);
                recherche(el,r);break;
         case 9:printf("entrer l'elt à ajouter: ");
                scanf("%d",&el);
                 r= ajout_new(el,r);
                 printf("\nc'est bien l'arbre se construit dynamiquement");break;//aj=ajout(el,r);break;
         case 10: printf("la racine :");
                      scanf("%d",&x);
                 r=cree_racine( x);break;
           default:printf("taper un nbr entre en 1 et 10");break;

          }
           getch();
           clrscr();
     }

      while(1);
     }
 arbre creefeuille(int x)
{
 arbre f;
 f=(arbre)malloc(sizeof(cellule));
 f->val=x;
 f->drt=NULL;
 f->gch=NULL;
 return f;
}
//les trois parcours :prefixer , infixer , postfixer
void prefixer(arbre a)
{
if(a!=NULL)
{
printf("%d\t",a->val);
prefixer(a->gch);
prefixer(a->drt);
}
}
void infixer(arbre a)
{
if(a!=NULL)
{
infixer(a->gch);
printf("%d\t",a->val);
infixer(a->drt);
}
}
void postfixer(arbre a)
{
if(a!=NULL)
   {
     postfixer(a->gch);
        if(a->drt==NULL)
        printf("%d\t",a->val);
        else{
        postfixer(a->drt);
        printf("%d\t",a->val);}
   }
 }
 int hauteur (arbre ar)
{
int h1,h2;
if(ar==NULL)
return(-1);
else
h1=hauteur(ar->drt);
h2=hauteur(ar->gch);
if(h1>h2)
return h1+1;
else
return h2+1;
}
int taille(arbre ar)
{
int t1,t2;
if(ar==NULL)
return 0;
t1=taille(ar->gch);
t2=taille(ar->drt);
return(t1+t2+1);
}
//la recherche d'un elt ds l'arbre
void recherche(int x,arbre ar)
{
if(ar==NULL)
printf("l'elt rechercher n'existe pas dans l'arbre ");
else
   if(ar->val==x)
   printf("l'elt existe dans l'arbre");
   else
      if(ar->val>x)
      {
      recherche(x,ar->gch);
        if(ar->val==x)
          printf("l'elt existe dans l'arbre");}
       else
       {
       recherche(x,ar->drt);
        if(ar->val==x)
          printf("l'elt existe dans l'arbre");}
}

arbre ajout_new(int el,arbre s_pre)
{
arbre s;
s=(arbre)malloc(sizeof(cellule));
s->val=el;
s->gch=NULL;
s->drt=NULL;
if(s_pre==NULL)
 {
s_pre=s; }
else
attacher_new( s_pre, s);
return s_pre;
}
//definition de la fonction qui attache le nouveau arbre(construit dans la fct ajout_new
void attacher_new(arbre s_pre,arbre s)
{
int a=0;
while(a==0)
 {
   if(s_pre->val<s->val)
     {
      if(s_pre->drt!=NULL)
        s_pre=s_pre->drt;
      else
        {
       s_pre->drt=s;
       a=1;}
     }
   else
     {
       if(s_pre->gch!=NULL)
         s_pre=s_pre->gch;
       else
         {
          s_pre->gch=s;
          a=1;
         }
     }
 }

}

A voir également

S'inscrire maintenant

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.