Parcours d'un arbre

Pour exemple, prenons un arbre.

Supposons que nous voulions effectuer un traitement sur chaque nœud de l'arbre.

Par exemple afficher le contenu, ou chercher une valeur, …

• on dispose d'une fonction traitement(noeud),
• on souhaite l'exécuter tour à tour sur chaque nœud de l'arbre

On doit donc parcourir tous les nœuds, une fois, sans en oublier…

Mais dans quel ordre ?

Les parties ci-dessous correspondent à différents choix possibles.

On effectue le traitement, niveau après niveau, dans l'ordre de la lecture : A, B, C, D, E, F, G, J, H

On utilise une file.

FONCTION parcourir_arbre_en_largeur
ENTRÉE : arbre
DÉBUT
  créer une file vide,
  enfiler la racine de l'arbre
  TANT QUE la file n'est pas vide RÉPÉTER
    défiler un noeud
    enfiler les enfants de ce noeud
    exécuter le traitement sur ce noeud
  FIN
FIN

Ce n'est pas si simple, détaillons un peu l'algorithme.

Version diaporama

On notera le contenu de la file sous la forme <A:B:C:D< où les éléments entrent par la droite et sortent par la gauche, dans le sens des flèches.

• Ligne 4, la file est vide → <<
• Ligne 5, la file reçoit A → <A<
• Ligne 6, la file n'étant pas vide, on exécute la boucle
  • Ligne 7, on défile, le nœud en cours est donc A et la file contient <<
  • Ligne 8, on enfile les enfants de A → <B:C<
  • Ligne 9, on exécute le traitement sur A
• Ligne 6, la file n'est pas vide
  • Ligne 7, défilement → nœud en cours B et file <C<
  • Ligne 8, enfilement des enfants de B → <C:D:E<
  • Ligne 9, traitement de B
• Ligne 6, file non vide
  • Ligne 7, défilement → nœud en cours C et file <D:E<
  • Ligne 8, enfilement des enfants de C → <D:E:F:G<
  • Ligne 9, traitement de C
• Ligne 6, file non vide
  • Ligne 7, défilement → nœud en cours D et file <E:F:G<
  • Ligne 8, enfilement des enfants de D… il n'y en a pas
  • Ligne 9, traitement de D
• etc.

La file fonctionne sur le principe du premier arrivé, premier servi. Comme on rencontre les parents en premiers, ils sont les premiers servis.

C'est un peu plus compliqué :

• Quand on traite un nœud, on termine tous ses enfants avant de passer à un autre nœud ;
• il faut décider si on exécute le traitement d'abord sur les nœuds enfants ou le parent, ce qui donne différents parcours en profondeur :
  • prefixe, quand le nœud parent est traité avant ses enfants,
  • sufixe, quand le nœud parent est traité après ses enfants,
  • infixe, quand le nœud parent est traité entre ses enfants. Celui-ci n'a de sens que dans le cas d'un arbre binaire. On traite l'enfant gauche, puis le parent puis l'enfant droit.

C'est le plus simple et le plus naturel.

C'est l'ordre – pour l'exemple – A, B, D,E, J, H, C, F, G
Vous constatez que l'on traite tout le sous arbre de B avant de traiter C.

On retrouve le même algorithme, mais avec une pile.

FONCTION parcourir_arbre_en_profondeur
ENTRÉE: arbre
DÉBUT
  créer une pile vide,
  empiler la racine de l'arbre
  TANT QUE la pile n'est pas vide RÉPÉTER
    dépiler un noeud
    empiler les enfants de ce noeud dans l'ordre inverse
    exécuter le traitement sur ce noeud
  FIN
FIN

Ce n'est pas si simple, détaillons un peu l'algorithme.

Version diaporama

On notera le contenu de la pile sous la forme A:B:C:D: où, dans ce cas, D est le dessus de la pile.

• Ligne 4, la pile est vide → :
• Ligne 5, la pile reçoit A → A:
• Ligne 6, la pile n'étant pas vide, on exécute la boucle
  • Ligne 7, on dépile, le nœud en cours est donc A et la pile contient :
  • Ligne 8, on empile les enfants de A à l'envers → C:B:
  • Ligne 9, on exécute le traitement sur A
• Ligne 6, la pile n'est pas vide
  • Ligne 7, dépilement → nœud en cours B et pile C:
  • Ligne 8, empilement des enfants de B à l'envers → C:E:D:
  • Ligne 9, traitement de B
• Ligne 6, pile non vide
  • Ligne 7, dépilement → nœud en cours D et pile C:E:
  • Ligne 8, empilement des enfants de D… il n'y en a pas
  • Ligne 9, traitement de D
• Ligne 6, pile non vide
  • Ligne 7, dépilement → nœud en cours E et pile C:
  • Ligne 8, empilement des enfants de E à l'envers → C:H:J:
  • Ligne 9, traitement de E
• etc.

Vous remarquez que le principe de la pile – dernier arrivé, premier servi – conduit à traiter les enfants de B avant le “frère” de B.

Vous remarquez aussi qu'on empile les enfants à l'envers pour qu'ils soient à l'endroit au moment du dépilement.

C'est un peu plus compliqué car on doit dissocier le moment où un nœud est parcouru et le moment où il est traité.

Prenons l'exemple de B : On devra parcourir B avant de partir à la découverte de sa descendance D et E, mais on doit attendre d'avoir terminer le parcours de toute la descendance avant de pouvoir traiter B…

Il serait possible de trouver une méthode de même genre que la précédente, en utilisant deux piles par exemple, une pile pour le parcours et une pile pour le traitement. Ce serait bien-sûr un peu plus compliqué.

À la place, je vous propose une approche différente : une approche récursive.

La récursivité permet une écriture très simple et intuitive mais cache des difficulté techniques que nous aborderons plus tard.

Nous définissions la fonction suivante :

FONCTION : parcourir_noeud
ENTRÉE : le noeud à traiter
DÉBUT
  POUR CHAQUE enfant du noeud RÉPÉTER
    exécuter parcourir_noeud avec l'enfant
  FIN
  traiter le noeud
FIN

• Cette fonction est récursive puisque elle s'appelle elle-même en ligne 5.
• Quand on en arrive aux feuilles de l'arbre, le nœud en cours n'a pas d'enfant et la fonction parcourir arrête de s'appeler elle-même. Sans cela, l'algorithme n'aurait pas de fin.

Le programme principal est maintenant très simple :

FONCTION : parcourir_arbre_en_profondeur_suffixe
ENTRÉE : arbre
DÉBUT
  SI arbre n'est pas vide ALORS
    exécuter parcourir_noeud avec la racine
  FIN
FIN