Discussion :

[alex2746]

Bonjour,
J'arrive à parcourir un arbre Binaire (parcours en largeur et parcours en profondeur RGD, GRD, GDR) mais je n'arrive pas à faire en sorte de trouver le niveau de chaque noeud.

Pourriez-vous m'aider?

Merci d'avance.

[Trap D]

Ce ne serait pas 1 + le niveau de son père, sachant que la racine a le niveau 0 ou 1 ?

[alex2746]

Oui c'est bien cela, la racine a 0 et ensuite c'est le niveau du père +1.

Mais je n'arrive pas à écrire un algorithme qui reçoit un arbre binaire d'entier et qui place comme valeur dans chaque noeud de l'arbre le niveau.

Donc dans la valeur de racine je placerai 0, ensuite dans ses fils je place 1, etc.

Merci d'avance.

[nono_31]

Bonjour,

C'est possible d'étiqueter les sommets avec leur profondeur en modifiant un peu le parcours en largeur.
Il faut faire une passe par niveau en dupliquant la file.

[alex2746]

C'est ce que je voulais faire mais je n'arrive pas à transformer mon parcours en largeur... Je n'arrive pas à me rendre compte du moment ou je passe au niveau suivant...

[nono_31]

Voici le pseudo-code de l'algo :

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
Bfs(T) : array
r := racine(T)
créer deux files F1 et F2 et ajouter r dans F1
i:=0
faire
tant que (F1 n’est pas vide)
x :=premier(F1); supprimer x de F1
array[i] := x
i++
pour chaque fils y de x
ajouter y dans F2
fin pour
fin tant que
F1 := F2
// fin d’une passe début de la nouvelle : la
F2 devient vide // profondeur change
tant que F1 n’est pas vide

Désolé, la mise en forme s'est perdue en chemin

[benratti]

De manière générale, tu peux faire cette alog en te basant sur un parcours en profondeur ou en largeur, peux importe. Le principale, dans les deux algos, c'est qu'au moment où tu récupères les fils d'un noeuds, tu en profites pour marquer leur profondeur. En effet, à ce moment, tu as la profondeur du père et tu peux facilement affecter la profondeur aux fils (prof(fils) = prof(père) + 1)