Arbre binaire
cs_phebus709
Messages postés
58
Date d'inscription
mercredi 16 février 2005
Statut
Membre
Dernière intervention
23 septembre 2006
-
28 mai 2005 à 00:55
thebadskull Messages postés 20 Date d'inscription dimanche 14 décembre 2003 Statut Membre Dernière intervention 29 mai 2005 - 2 juin 2005 à 22:37
thebadskull Messages postés 20 Date d'inscription dimanche 14 décembre 2003 Statut Membre Dernière intervention 29 mai 2005 - 2 juin 2005 à 22:37
3 réponses
thebadskull
Messages postés
20
Date d'inscription
dimanche 14 décembre 2003
Statut
Membre
Dernière intervention
29 mai 2005
28 mai 2005 à 13:36
28 mai 2005 à 13:36
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;
}
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;
}
cs_phebus709
Messages postés
58
Date d'inscription
mercredi 16 février 2005
Statut
Membre
Dernière intervention
23 septembre 2006
2 juin 2005 à 15:22
2 juin 2005 à 15:22
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;
};
typedef struct personne
{
char nom[40];
personne* fils;
personne* frere;
};
thebadskull
Messages postés
20
Date d'inscription
dimanche 14 décembre 2003
Statut
Membre
Dernière intervention
29 mai 2005
2 juin 2005 à 22:37
2 juin 2005 à 22:37
je le sais !!!
tu met ce que tu veu !!!
mais c'est pour te donner un exemple ^^
tu met ce que tu veu !!!
mais c'est pour te donner un exemple ^^
