Discussion :

[GouKen]

Bonjour, je suis a la recherche d'une fonction permettant de calculer la hauteur d'un arbre, j'ai codé ceci mais ça ne semble pas fonctionné :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int hauteur(ptr_arbre a)
{
   int h;
   h = 0;
 
   if(a == NULL)
   {
       return ;
   }
   else
   {
       h = 1 + hauteur(a->sag) + hauteur(a->sad);
   }
   return h;
}

[jowo]

Bonjour, je suis a la recherche d'une fonction permettant de calculer la hauteur d'un arbre, j'ai codé ceci mais ça ne semble pas fonctionné :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int hauteur(ptr_arbre a)
{
   int h;
   h = 0;
 
   if(a == NULL)
   {
       return ;
   }
   else
   {
       h = 1 + hauteur(a->sag) + hauteur(a->sad);
   }
   return h;
}

Ton code n'est pas correct.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
int hauteur(ptr_arbre a)  {
   int h;
 
   h = 0;   
   if (a != NULL) {
       h = 1 + hauteur(a->sag) + hauteur(a->sad);
   }
   return h;
}

Mais je ne suis pas sûr que ce soit le bon algo pour calculer l'hauteur d'un arbre. Il te retourne, à mon avis et en première lecture, le nombre d'éléments de ton arbre.

[GouKen]

en effet il retourne le nb d'éléments de l'arbre...
quelqu'un aurait une idée pour calculer la hauteur d'un arbre ?!

[GouKen]

personne ne sait m'aider?!

[archer]

Salut
A vrai dire je ne sais pas ce que tu désignes par la hauteur de l’arbre, est ce la plus longue branche de cet arbre ou est ce le nombre de branche ?

[GouKen]

la hauteur correspond finalement au nombre d'étage de l'arbre..le soucis est de ne pas compter 2x un élément sur le même étage..

[jowo]

Bonjour,

La hauteur d'un arbre binaire est la longueur du plus grand chemin de la racine aux feuilles.

Donc il suffit de conserver la valeur maximale retournée par la visite des sous-arbres et de la retourner en l'incrémentant de 1.

A toi de trouver le code. Il suffit de peu de changement pour que ton code fonctionne.

[jmi23]

j'ai fait un devoir dessus, testé et vérifié, la fonction hauteur ;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
int hauteur(ptr_ArbreBinaire a)
{
    if(estVide(a))         
        return ERREUR;
 
 
    if(est1feuille(a))
        return 0;
    else
        return 1+max(hauteur(filsgauche(a)), hauteur(filsdroit(a)));
 
}

La fonction max renvoyant simplement le plus grand de 2 entiers passés en paramètres. (Pour les arbres déséquilibrés)

[archer]

Salut
tout d'abord je m’excuse pour le retard. Je vous propose de déclarer une variable globale de type entier pour y mettre la hauteur par exemple b, puis essayez le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
void hauteur( ptr_arbre a,int n)
{
	if(a !=NULL)
        {
	        hauteur(a->sag,n+1) ;
                if(n>b)  b=n;
	        hauteur(a->sad,n+1) ;
        }
}

Puis dans le main() apellez le fonction en mettant 1 comme deuxième argument.
J’espère que ça va marcher

[jowo]

Salut
tout d'abord je m’excuse pour le retard. Je vous propose de déclarer une variable globale de type entier pour y mettre la hauteur par exemple b, puis essayez le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
void hauteur( ptr_arbre a,int n)
{
	if(a !=NULL)
        {
	        hauteur(a->sag,n+1) ;
                b=max(n,b) ;
	        hauteur(a->sad,n+1) ;
        }
}

Puis dans le main() apellez le fonction en mettant 1 comme deuxième argument.
J’espère que ça va marcher

Monsieur Archer,

Il faut immédiatement arrêter de fumer la moquette. Les acariens grillés, ce n'est pas bons pour les petites cellules grises.

Soyons sérieux, déclarer un variable globale pour sauvegarder la valeur retournée par une fonction!!
Voyons même en Basic ou en assembleur, on n'utilise pas de telles horreurs...

[archer]

Salut
je me demande bien pourquoi tu es si agressif alors que mon but est d’aider. D’autant plus si tu as d’autres solutions allez vas s’y j’attends sinon essayes au moins de l’améliorer.

[jowo]

Salut

Je ne suis pas agressif... . Je suis mordant.

La solution, je la connais déjà et en plus jmi23 l'a déjà donnée.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
int hauteurArbre(Noeud n)
{
   int h = 0;
 
   if (n != NULL) {
       h = 1 + max(hauteurArbre(n->sag) + hauteurArbre(a->sad));
   }
   return h;
}

Je te prie de bien vouloir m'excuser si tu t'es senti agressé.

[archer]

Salut
Ce n’est rien
Essayes ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
void hauteur( ptr_arbre a,int n,int *b)
{
	if(a !=NULL)
{
	hauteur(a->sag,n+1,b) ;
        if(n>*b) *b=n ;
	hauteur(a->sad,n+1,b) ;
}
}

Puis dans le main() déclarez une variable qui contiendra la hauteur de l’arbre puis faîtes appelle à la fonction en mettant 1 comme deuxième argument et cette variable comme dernier.
Je ne crois pas que là aussi je fume le ‘tapis’.