Discussion :

[Invité]

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 :

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

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++ :

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

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

[Invité]

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++ :

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

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

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

Code :

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

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é...