Taille D'un arbre AVL [Résolu]

[nejibos]

je suis entrain de travaillé sur un petit projet en utilisant les arbres AVL
SVP quelqu’un peux m'aider pour implémenter le fonction Taille sachant qu'il une autre fonction max que normalement sera utile

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
///private:
    class Noeud{
      public:
        Noeud(const T&);
        Noeud *gauche;
        Noeud *droite;
        int equilibre;
        T element;
    };
/********************/
 
 
Template <class T>
int  ArbreAVL<T>::hauteur() const{
    Noeud* n=racine;
   assert(n!=NULL)
 
    if(n->gauche!=NULL)
 
	 if(n->equilibre > 0)
           n = n->gauche;
    if(n->droite!=NULL)
 
 
 
    hauteur(n->contenu);
   }
    return 0;
}
/***********************/
template <class T>
const T& ArbreAVL<T>::max(Noeud* n) const
{
         assert(n!=NULL)
 
	while (n->droite != NULL)
		n = n->droite;
	return  n->element;;
}

[Médinoc]

Commence par définir ce que tu appelles la taille. Est-ce le nombre total d'éléments? Si oui, c'est assez facile:

Code C++ :

1
2
3
4
5
6
7
8
9
10
static int STaille(const Noeud *pNoeud)
{
	int taille = 0;
	if(pNoeud==NULL)
		return taille;
	taille += STaille(pNoeud->gauche);
	taille += 1;
	taille += STaille(pNoeud->droite);
	return taille;
}

[nejibos]

Envoyé par Médinoc

Commence par définir ce que tu appelles la taille. Est-ce le nombre total d'éléments? Si oui, c'est assez facile:

Code C++ :

merci
deja j'ai l'impelemnter comme ca avant de voir votre reponse

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template <class T>
int  ArbreAVL<T>::hauteur() const{
    hauteur(racine);
 
}
template <class T>
int  ArbreAVL<T>::hauteur(Noeud*& noeud) const
 
    if (noeud == NULL) return 0;
 
    int hauteur_gauche = hauteur(noeud->gauche);
    int hauteur_droit = hauteur(noeud->droite);
  return 1 + ((hauteur_gauche > hauteur_droit) ? hauteur_gauche : hauteur_droit);

[Médinoc]

Attention, je considère la hauteur différente du nombre total d'éléments. Je t'avais bien dit que le mot "taille" était ambigu.
Ta fonction calcule la hauteur, la mienne le nombre total d'élements.

Ensuite:

• Pourquoi prendre le pointeur par référence? On ne le modifie pas...
• Pourquoi le pointeur n'est-il pas const? On ne modifie pas le noeud pointé...