Bonjour tout le monde,

Nous sommes occupés à étudier les arbres binaires (simplement chainée).

J'ai trouvé un bon tuto sur developpez.com à propos du calcul du nombre de noeud.

Je me pose quelques questions sur cette explication :

Le calcul du nombre de nœud est très simple. On définit le calcul en utilisant la définition récursive :

- Si l'arbre est vide : renvoyer 0
- Sinon renvoyer 1 plus la somme du nombre de nœuds des sous arbres.
On aura donc le pseudo code suivant :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
fonction NombreNoeud( T : arbre ) renvoie un entier
 
	si ( EstVide( T ) )
		renvoyer 0;
	sinon
		renvoyer 1 + NombreNoeud(FilsGauche(T)) + NombreNoeud(FilsDroit(T));
	fin si
On peut donc traduire celà en langage C :

1) Si l'arbre n'est pas vide, on va rappeler la fonction mais quand cela va s'arrêter (quand arbre sera à vide) mais comment va t'il se vider ? qu'est-ce qui se décrémente dans ce code ?

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
 
unsigned NbNode(tree T)
{
	if( IsEmpty(T) )
		return 0;
	else
		return 1 + NbNode(Left(T)) + NbNode(Right(T));
}
Merci d'avance pour votre aide très très précieuse.

beegees