Arbre binaire

Signaler
Messages postés
58
Date d'inscription
mercredi 16 février 2005
Statut
Membre
Dernière intervention
23 septembre 2006
-
Messages postés
20
Date d'inscription
dimanche 14 décembre 2003
Statut
Membre
Dernière intervention
29 mai 2005
-
je cherche comment faire toutes les operations(recherche ,supression insertion....) dans une arbre binaire!mais dans les deux formes (itterative et recursive)! et merci!de votre reponse(code ou algorithme)!! [mailto:phebus709@hotmail.com phebus709@hotmail.com]

3 réponses

Messages postés
20
Date d'inscription
dimanche 14 décembre 2003
Statut
Membre
Dernière intervention
29 mai 2005

je te file tout ça ya p-e des erreur mais je croi pas...

jlé pas compilé...

mais c'est a peu pres ça :





//declarations de types

typedef struct n

{

int val;

struct n *fg,*fd;

}Noeud;



typedef Noeud* Arbre;







int degenere(Arbre a)

{

if(a==NULL) return 1;

if(a->fg!=NULL && a->fd!=NULL) return 0;

return(degenere(a->fg) && degenere(a->fd));

}







int max(int a,int b)

{

if(a>b) return a;

return b;

}







Arbre creation()

{

Arbre a=NULL;

int i,j,k;

printf("\nEntrer le nombre de valeurs à saisir : ");

scanf("%d",&i);

for(j=0;jfg)+nb_noeud(a->fd));

}



int hauteur(Arbre a)

{

if(a==NULL) return 0;

return (1+max(hauteur(a->fg),hauteur(a->fd)));

}





int nb_feuilles(Arbre a)

{

if(a==NULL) return 0;

if(a->fg==NULL && a->fd==NULL) return 1;

return nb_feuilles(a->fg)+nb_feuilles(a->fd);

}





int be(Arbre a)

{

return abs(hauteur(a->fg)-hauteur(a->fd))<=1;

}



Arbre creation_abe(int n)

{

Arbre a=(Arbre) malloc(sizeof(Noeud));

int x;

if(n>0)

{

printf("Valeur %d : ",n);

scanf("%d",&x);

a->val=x;

a->fg=creation_abe((n-1)/2);

a->fd=creation_abe((n-1)-(n-1)/2);

return a;

}

return NULL;

}























Arbre suppression(Arbre a,int x)

{

Arbre tmp;

if(a!=NULL)

{

if(a->val>x) a->fg=suppression(a->fg,x);

else if(a->val<x) a->fd=suppression(a->fd,x);

else // il y a égalité

{

if(a->fg==NULL) {tmp=a->fd; free(a); a=tmp;}

else if(a->fd==NULL) {tmp=a->fg; free(a); a=tmp;}

else

{

a->fg=suppmax(a->fg,&x);

a->val=x;

}

}

}

return a;

}





Arbre suppmax(Arbre a,int *pmax)

{

Arbre tmp;

if(a->fd==NULL)

{

*pmax=a->val;

tmp=a->fg;

free(a);

a=tmp;

}

else a->fd=suppmax(a->fd,pmax);

return a;

}







void affich_paren(Arbre a)

{

if(a!=NULL)

{

printf("%d",a->val);

if(a->fg!=NULL || a->fd!=NULL) printf("(");

affich_paren(a->fg);

if(a->fg!=NULL || a->fd!=NULL) printf(",");

affich_paren(a->fd);

if(a->fg!=NULL || a->fd!=NULL) printf(")");

}

}



void affich2(Arbre a)

{

Arbre prec=a;

if(a!=NULL)

{

printf("%d",a->val);

if(a->fg!=NULL || a->fd!=NULL) printf("(");

a=a->fg;

while(prec!=NULL)

{

affich2(a);

a=prec->fd;

prec=prec->fd;

if(a!=NULL) printf(",");

}

printf(")");

}

}



void affich_tri(Arbre a)

{

if(a!=NULL)

{

affich_tri(a->fg);

printf("%3d",a->val);

affich_tri(a->fd);

}

}



Arbre ajout(Arbre a,int x)

{

if(a!=NULL)

{

if(a->val>x) a->fg=ajout(a->fg,x);

else a->fd=ajout(a->fd,x);

}

else

{

a=(Arbre) malloc(sizeof(Noeud));

a->val=x;

a->fg=NULL;

a->fd=NULL;

}

return a;

}
Messages postés
58
Date d'inscription
mercredi 16 février 2005
Statut
Membre
Dernière intervention
23 septembre 2006

merci thebadskull pr la reponse mais la structure de de chaque element de l'arbre ne doit contient forcement un entier!!la structure est sous cette forme::
typedef struct personne
{
char nom[40];
personne* fils;
personne* frere;
};
Messages postés
20
Date d'inscription
dimanche 14 décembre 2003
Statut
Membre
Dernière intervention
29 mai 2005

je le sais !!!

tu met ce que tu veu !!!

mais c'est pour te donner un exemple ^^