Parcours d’arbre : Depth First & Breadth First 🌳

Alexandre Cantin
Apr 30 · 5 min read

Le parcours d’arbre est un grand classique lors d’entretiens algorithmiques et bien que cet exercice peut sembler intimidant au premier abord, nous allons découvrir qu’il y a, en réalité, plus de peur que de mal !

Ainsi, dans cet article, nous nous intéressons aux deux méthodes les plus courantes afin de parcourir un arbre que sont :

  • le parcours en profondeur (Depth First), oĂą le choix du prochain noeud se porte sur le premier enfant du noeud courant :
Image for post
Image for post
Parcours en profondeur
  • le parcours en largeur (Breadth First), oĂą le prochain noeud est celui adjacent au noeud courant, c’est-Ă -dire celui situĂ© au mĂŞme niveau de profondeur :
Image for post
Image for post
Parcours en largeur

Parcours en profondeur — Depth first

Au niveau algorithmique, l’utilisation de la récursivité reste le choix le plus pertinent. Ainsi, nous utiliserons la récursivité pour notre parcours mais nous y ajouterons toutefois une étape supplémentaire, pour les besoins de l’article, en stockant les noeuds dans une structure de données.

En effet, dès l’entrée dans un noeud et après le traitement de sa valeur, nous stockerons ses enfants dans une structure de données (contenant une méthode saveNode), récupérerons ensuite le prochain noeud (méthode getNextNode) et passerons à la prochaine étape de notre parcours. En pseudo-code, nous obtenons ainsi :

Maintenant, si nous déroulons un exemple plus concret avec l’arbre présenté en début d’article et le pseudo-code ci-dessus :

1ère étape :

  • Nous traitons la valeur du noeud : 1, nous sommes Ă  la racine

2ème étape :

  • Nous traitons la valeur du noeud : 2

3ème étape :

  • Nous traitons la valeur du noeud : 3

4ème étape :

  • Nous traitons la valeur du noeud : 4

5ème étape :

  • Nous traitons la valeur du noeud : 5

6ème étape :

  • Nous traitons la valeur du noeud : 6

7ème étape :

  • Nous traitons la valeur du noeud : 7

8ème étape :

  • Pas de valeur et la structure est vide : le parcours est terminĂ©

Après ce long déroulé, nous constatons que l’ordre d’ajout dans la liste à son importance : nous ne prenons que le noeud inséré le plus récemment. En algorithmique, ce concept est appelé Last In First Out, abrégé LIFO, et notre structure de données doit respecter cette règle pour devenir compatible avec le parcours en profondeur; comme par exemple une stack.

Un ajustement est juste nécessaire vis-à-vis du pseudo algorithme précédent : le noeud gauche y est inséré avant le noeud de droite. On parcourt ainsi l’arbre par la droite (1 -5–7–6–2–4–3) et on doit ainsi permuter les deux lignes saveNode :

Nous en avons ainsi fini avec le parcours en profondeur. L’ajout d’une structure de données peut sembler au premier abord superflu mais, rassurez-vous, ce socle nous sera très utile pour le parcours en largeur.

Parcours en largeur — Breadth First

Pour le parcours en largeur, nous utiliserons une base identique à celle du parcours en profondeur, à savoir le pseudo-algorithme associé à une structure de données (encore inconnue à ce stade). Si, comme précédent, nous effectuons un déroulé des différentes étapes du parcours, nous obtenons :

1ère étape :

  • Nous traitons la valeur du noeud : 1, nous sommes Ă  la racine

2ème étape :

  • Nous traitons la valeur du noeud : 2

3ème étape :

  • Nous traitons la valeur du noeud : 5

4ème étape :

  • Nous traitons la valeur du noeud : 3

5ème étape :

  • Nous traitons la valeur du noeud : 4

6ème étape :

  • Nous traitons la valeur du noeud : 6

7ème étape :

  • Nous traitons la valeur du noeud : 7

8ème étape :

  • Pas de valeur et la structure est vide : le parcours est terminĂ©

Ici, et contrairement au parcours en profondeur, ce n’est pas le dernier noeud inséré qui nous intéresse mais le plus ancien. Ce concept algorithmique, appelé First In First Out et abrégé FIFO, se doit donc d’être respecté par notre structure de données et comme exemple, nous pouvons citer une queue, cette dernière étant similaire à une file d’attente.

Conclusion

Plusieurs domaines de l’informatique exploitent la puissance des arbres : index de base de données, arbres de décision, analyse de code source (Abstract syntax tree)… et cela explique ainsi leur présence en entretien technique.

Toutefois comme nous venons de le voir, le parcours d’arbre en profondeur ou en largeur n’est pas si complexe et peut se résumer à une simple association avec une structure de données :

  • une structure respectant la logique LIFO pour un parcours en profondeur

Deux concepts finalement faciles et rapides à retenir et qui, j’espère, ne vous fera plus craindre de futurs entretiens avec des parcours d’arbres !

CodeShake

Learnings and insights from SFEIR community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store