Algorithmic and Data Structures Courses

Chapitre V : Les arbres
3. Parcours
3.1 Parcours des arbres (arbres ordonnés).
a- Parcours en profondeur
Dans un parcours en profondeur d’abord, on descend le plus
profondément possible dans l’arbre puis, une fois qu’une feuille a
été atteinte, on remonte pour explorer les autres branches en
commençant par la branche « la plus basse » parmi celles non
encore parcourues ; les fils d’un noeud sont bien évidemment
parcourus suivant l’ordre sur l’arbre.

PP(A)
si A n’est pas réduit à une feuille faire
pour tous les fils u de racine(A) faire dans l’ordre PP(u)

, Chapitre V : Les arbres
 On distingue trois algorithmes qui affichent les valeurs contenues dans les noeuds d’un
arbre binaire, suivant des parcours en profondeur préfixe, infixe et postfixe.

PRÉFIXE(A)
si A ≠NIL faire
affiche racine(A)
PRÉFIXE(FILS-GAUCHE(A))
PRÉFIXE(FILS-DROIT(A))

INFIXE(A)
si A ≠ NIL faire
INFIXE(FILS-GAUCHE(A))
affiche racine(A)
INFIXE(FILS-DROIT(A))

POSTFIXE(A)
si A ≠ NIL faire
POSTFIXE(FILS-GAUCHE(A)) Affichage préfixe : 1, 2, 4, 8, 9, 5, 10, 3, 6, 7
POSTFIXE(FILS-DROIT(A)) Affichage infixe : 8, 4, 9, 2, 10, 5,1, 6, 3, 7
affiche racine(A) Affichage postfixe : 8, 9,4, 10, 5,2, 6, 7,3,1