Discussion :

[beegees]

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

[PRomu@ld]

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 ?

Je ne comprend pas trop ta question. Qu'est ce qui te gène ?

[Alp]

Les appels récursifs vont s'arrêter quand, en allant de fils en fils, tu vas enfin t'arrêter sur un noeud qui n'a plus de fils. Ainsi, ce noeud renverra 1 pour lui-même à son père, comme tous les fils de ce même père, puis le père saura donc le nombre de noeuds fils qu'il a, renverra 1 + ce nombre à son père à lui, ainsi de suite ... et ce jusqu'à revenir au premier appel de cette fonction, qui a été effectué sur le premier noeud. Ainsi, tous les appels à NbNoeuds auront été effectués, terminés, et tu auras enfin ce fameux nombre

[beegees]

Les appels récursifs vont s'arrêter quand, en allant de fils en fils, tu vas enfin t'arrêter sur un noeud qui n'a plus de fils. Ainsi, ce noeud renverra 1 pour lui-même à son père, comme tous les fils de ce même père, puis le père saura donc le nombre de noeuds fils qu'il a, renverra 1 + ce nombre à son père à lui, ainsi de suite ... et ce jusqu'à revenir au premier appel de cette fonction, qui a été effectué sur le premier noeud. Ainsi, tous les appels à NbNoeuds auront été effectués, terminés, et tu auras enfin ce fameux nombre

Bonjour Alp,

Merci pour ta réponse.

J'aimerais mettre en pratique (en C) ton explication et le code que j'ai trouvé dans le tuto, quelles données utilisées ? Je dois créer des variables comme ceci pour tester le code :

long a = 1;
long b = 2;
long c = 3;

...


???

Désolé mais j'ai du mal à comprendre la récursivité.

beegees

[Alp]

Non. Tu dois d'abord créer une structure Node et les fonctions qui servent à se déplacer de Node en Node. Chaque node possèdera une information (un entier par exemple), et c'est donc dans la structure de Node que tu devras mettre les informations.
(Node = Noeud, mais en anglais)

A priori, ça aurait cette tête là :

Code :

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

1
2
3
4
5
6
typedef struct Node_t
{
Node_t* filsGauche;
Node_t* filsDroit;
int information;
} Node ;

puis :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
struct Node* Left(struct Node* T)
{
return T->filsGauche;
}
 
struct Node* Right(struct Node* T)
{
return T->filsDroit;
}

Maintenant, tout est prêt pour que tu écrive ta fonction récursive ...

PS : excuse moi s'il y a des erreurs de C, mais ça fait des lustres que je n'en ai plus fait

[HanLee]

J'pense qu'une part de l'incompréhension vient du fait sans explications, c'est pas évident de voir que la fonction termine.

C'est vrai, pourquoi il n'y aurait pas d'arbre infini ?

Si on exprime la structure d'arbre sous forme algébrique, on comprend les choses plus simplement :

Un arbre est soit l'arbre vide, soit le triplet composé d'un élément et deux arbres binaires, celui de gauche et celui de droite.

Définition récursive, qui n'empêche pas d'avoir des arbres de hauteur infinie.
Il faut alors préciser que l'arbre doit être dans le plus petit ensemble clos par l'opération de construction du triplet, et là, c'est bon !

- sous forme d'équations on arrive naturellement à écrire l'algorithme : le nombre de noeuds d'un arbre c'est quoi ? Si l'arbre est vide, c'est 0, mais sinon, c'est le nombre de noeuds du gauche et du droite + 1, parce qu'il faut compter la racine. C'est exactement ce que tu as écrit.

- est-ce que l'algorithme s'arrête ? Il suffit de te dire que tu ne manipules que des arbres finis, et que donc tout arbre a été construit selon l'opération de construction en un nombre fini de fois. Ainsi, tu n'as plus besoin de partir dans des raisonnements qui donnent le vertige. Pour le cas ici présent, la preuve de terminaison est donc super simple.

Mais attention : en C, à cause des pointeurs, tu pourrais très bien tomber sur un cas d'arbre infini s'il y a eu des manipulations hasardeuses.

Le type d'arbre binaire représenté en C est en quelque sorte l'ensemble des arbres binaires "rationnels", au sens des nombres rationnels, qui se termine par un suffixe périodique.