A Rappels algorithmiques
401
Nous voyons que, dans le parcours en profondeur d’un arbre binaire, chaque
nœud interne peut être visité à trois moments différents. Il existe trois variantes
classiques de ce parcours, lorsqu’une seule de ces visites est effectuée et suivant
le moment de visite ; ce sont les parcours préfixe, symétrique et suffixe que nous
présentons maintenant.
Parcours préfixe
Dans le parcours préfixe d’un arbre, la visite d’un nœud a lieu lors du premier
passage en ce nœud.
Procedure parcoursPréfixe(Arbre A)
// Précondition : A est un arbre.
// Postcondition : A n’a pas été modifié ; l’arbre est visité par un parcours en
ordre préfixe.
// Utilise : parcoursPréfixe, visite
si A != None alors
visite(A)
parcoursPréfixe(A.gauche)
parcoursPréfixe(A.droit)
Parcours symétrique
Dans le parcours symétrique d’un arbre, la visite d’un nœud a lieu lors du second
passage en ce nœud.
Procedure parcoursSymétrique(Arbre A)
// Précondition : A est un arbre.
// Postcondition : A n’a pas été modifié ; l’arbre est visité par un parcours en
ordre symétrique.
// Utilise : parcoursSymétrique, visite
si A != None alors
parcoursSymétrique(A.gauche)
visite(A)
parcoursSymétrique(A.droit)