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
  • Nous ajoutons ses deux enfants dans la structure de donnĂ©es : [2,5]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [2,5] => 2, [5]

2ème étape :

  • Nous traitons la valeur du noeud : 2
  • Nous ajoutons ses deux enfants dans la structure de donnĂ©es : [3, 4, 5]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [3, 4, 5] => 3, [4,5]

3ème étape :

  • Nous traitons la valeur du noeud : 3
  • Pas d’enfant, la structure est inchangĂ©e : [4, 5]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [4, 5] => 4, [5]

4ème étape :

  • Nous traitons la valeur du noeud : 4
  • Pas d’enfant, la structure est inchangĂ©e : [5]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [5] => 5, []

5ème étape :

  • Nous traitons la valeur du noeud : 5
  • Nous ajoutons ses deux enfants dans la structure de donnĂ©es : [6,7]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [6,7] => 6, [7]

6ème étape :

  • Nous traitons la valeur du noeud : 6
  • Pas d’enfant, la structure est inchangĂ©e : [7]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [7] => 7, []

7ème étape :

  • Nous traitons la valeur du noeud : 7
  • Pas d’enfant, la structure est inchangĂ©e : []
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [] => x, []

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
  • Nous ajoutons ses deux enfants dans la structure de donnĂ©es : [2,5]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [2,5] => 2, [5]

2ème étape :

  • Nous traitons la valeur du noeud : 2
  • Nous ajoutons ses deux enfants dans la structure de donnĂ©es : [3, 4, 5]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [3, 4, 5] => 5, [3, 4]

3ème étape :

  • Nous traitons la valeur du noeud : 5
  • Nous ajoutons ses deux enfants dans la structure de donnĂ©es : [3, 4, 6, 7]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [3, 4, 6, 7] => 3, [4, 6, 7]

4ème étape :

  • Nous traitons la valeur du noeud : 3
  • Pas d’enfant, la structure est inchangĂ©e : [4, 6, 7]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [4, 6, 7] => 4, [6, 7]

5ème étape :

  • Nous traitons la valeur du noeud : 4
  • Pas d’enfant, la structure est inchangĂ©e : [6,7]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [6,7] => 6, [7]

6ème étape :

  • Nous traitons la valeur du noeud : 6
  • Pas d’enfant, la structure est inchangĂ©e : [7]
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [7] => 7, []

7ème étape :

  • Nous traitons la valeur du noeud : 7
  • Pas d’enfant, la structure est inchangĂ©e : []
  • Nous rĂ©cupĂ©rons le prochain Ă©lĂ©ment : [] => x, []

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
  • et une structure respectant la logique FIFO pour un parcours en largeur

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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

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