ARBRE BINAIRE

#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;
         }
     }
 }

}