402
A Rappels algorithmiques
Fig. A.1 Représentation
d’une expression
arithmétique par un arbre
Parcours suffixe, ou postfixe
Dans le parcours postfixe d’un arbre, la visite d’un nœud a lieu lors du troisième et
dernier passage en ce nœud.
Procedure parcoursSuffixe(Arbre A)
// Précondition : A est un arbre.
// Postcondition : A n’a pas été modifié ; l’arbre est visité par un parcours en
ordre suffixe.
// Utilise : parcoursSuffixe, visite
si A != None alors
parcoursSuffixe(A.gauche)
parcoursSuffixe(A.droit)
visite(A)
Par exemple, sur l’arbre de la figure A.1 représentant une expression arithmétique, et lorsque l’effet de la visite d’un nœud est d’écrire sa marque, l’ordre préfixe
donne + − x ∗ 5 z + a / x 3, l’ordre postfixe (ou suffixe) x 5 z ∗ − a x 3 / + +,
et l’ordre symétrique x − 5 ∗ z + a + x / 3. Remarquons que ce dernier ordre est
ambigu : il peut correspondre à plusieurs arbres (et donc expressions) distincts. Les
ordres préfixe et postfixe ne sont pas ambigus ; ils correspondent respectivement
aux notations polonaise et polonaise inverse.
A.1.3 Parcours en largeur, ou hiérarchique
Il existe un autre type de parcours : le parcours en ordre hiérarchique, dit aussi
parcours en largeur. Dans ce parcours, les nœuds sont visités par niveaux de
profondeur croissante, et sur chaque niveau de gauche à droite ; il s’agit d’une
spécialisation du parcours en largeur de graphes.
A Rappels algorithmiques
Fig. A.1 Représentation
d’une expression
arithmétique par un arbre
Parcours suffixe, ou postfixe
Dans le parcours postfixe d’un arbre, la visite d’un nœud a lieu lors du troisième et
dernier passage en ce nœud.
Procedure parcoursSuffixe(Arbre A)
// Précondition : A est un arbre.
// Postcondition : A n’a pas été modifié ; l’arbre est visité par un parcours en
ordre suffixe.
// Utilise : parcoursSuffixe, visite
si A != None alors
parcoursSuffixe(A.gauche)
parcoursSuffixe(A.droit)
visite(A)
Par exemple, sur l’arbre de la figure A.1 représentant une expression arithmétique, et lorsque l’effet de la visite d’un nœud est d’écrire sa marque, l’ordre préfixe
donne + − x ∗ 5 z + a / x 3, l’ordre postfixe (ou suffixe) x 5 z ∗ − a x 3 / + +,
et l’ordre symétrique x − 5 ∗ z + a + x / 3. Remarquons que ce dernier ordre est
ambigu : il peut correspondre à plusieurs arbres (et donc expressions) distincts. Les
ordres préfixe et postfixe ne sont pas ambigus ; ils correspondent respectivement
aux notations polonaise et polonaise inverse.
A.1.3 Parcours en largeur, ou hiérarchique
Il existe un autre type de parcours : le parcours en ordre hiérarchique, dit aussi
parcours en largeur. Dans ce parcours, les nœuds sont visités par niveaux de
profondeur croissante, et sur chaque niveau de gauche à droite ; il s’agit d’une
spécialisation du parcours en largeur de graphes.