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
Définition : Parcours préfixe
Le noeud est traité avant de traiter les sous-arbres.
Cela donne l'affichage suivant : 3 7 5 2 1 8
Définition : Parcours infixe
Le sous-arbre gauche est traité, puis le noeud courant, et enfin le sous-arbre droit.
Cela donne l'affichage suivant : 5 7 2 3 8 1
Définition : Parcours postfixe
Le noeud est traité après avoir traité les sous-arbres.
Cela donne l'affichage suivant : 5 2 7 8 1 3
Parcours visuel - Moyen mémo-technique
Simulation : Exercice
Donner cinq arbres de taille 3 dont les noeuds contiennent 1, 2 et 3 et le parcours infixe traite les noeuds 1, 2 et 3 dans cet ordre.
Définition : 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.
Ou dit plus simplement :
Le parcours en largeur d’un arbre binaire non vide consiste à le parcourir par niveaux.
Cela donne l'affichage suivant : 3 7 1 5 2 8