Parcours

Il est intéressant de parcourir tous les éléments d'un arbre, et surtout de manipuler l'ordre du parcours.

Il existe quatre types majoritaires de parcours :

• Parcours préfixe
• Parcours infixe
• Parcours postfixe
• Parcours en largeur

L'arbre ci-dessus va permettre de montrer les différents parcours avec des exemples. Nous supposerons que l'opération de traitement sera simplement d'afficher la valeur du nœud traité.

Parcours préfixe

Le nœud est traité avant de traiter les sous-arbres.

Cela donne l'affichage suivant : 3 7 5 2 1 8

Parcours infixe

Le sous-arbre gauche est traité, puis le nœud courant, et enfin le sous-arbre droit.

Cela donne l'affichage suivant : 5 7 2 3 8 1

Parcours postfixe

Le nœud est traité après avoir traité les sous-arbres.

Cela donne l'affichage suivant : 5 2 7 8 1 3

Moyen mémo-technique pour connaître l'ordre de chaque parcours

Exercice

Donner cinq arbres de taille 3 dont les nœuds contiennent 1, 2 et 3 et le parcours infixe traite les nœuds 1, 2 et 3 dans cet ordre.

Parcours en largeur

Les sous-arbres rencontrés sont enregistrés dans une file (gauche puis droit) avant de traiter le premier élément de la file.

Cela donne l'affichage suivant : 3 7 1 5 2 8