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.
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.
Ce ne serait pas 1 + le niveau de son père, sachant que la racine a le niveau 0 ou 1 ?
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
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.
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.
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...
Voici le pseudo-code de l'algo :
Désolé, la mise en forme s'est perdue en chemin
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 nest 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 dune passe début de la nouvelle : la F2 devient vide // profondeur change tant que F1 nest pas vide
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)
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager