A Rappels algorithmiques
403
L’implémentation usuelle du parcours en largeur fait appel à une file, structure
de données qui obéit au principe « premier arrivé, premier sorti ».
La structure de données File est supposée admettre les fonctions suivantes :
– La fonction créerFile() ne prend pas d’argument, et renvoie une file vide.
– La fonction estFileVide(File F) renvoie un booléen valant vrai ou faux
selon que la pile est vide ou non.
– La procédure enfiler(File F, élément X) ajoute l’élément X en queue de
file.
– La fonction défiler(File F) supprime le premier élément à la tête de la file
(si elle est non vide) et renvoie cet élément.
L’algorithme du parcours en largeur à l’aide d’une file s’écrit alors de la façon
suivante.
Procedure parcoursLargeur(Arbre A)
// Précondition : A est un arbre.
// Postcondition : A n’a pas été modifié ; l’arbre est visité par un parcours en
largeur.
// Utilise : enfiler, défiler, visite, créerFile , estFileVide
// Variables locales : élément X, File F
F = créerFile()
// Crée une file vide
enfiler(F, A)
// Insère la racine dans la file
tant que non estFileVide(F) faire
X = défiler(F)
// Prend le premier nœud de la file. . .
enfiler(F, A.gauche)
enfiler(F, A.droit)
// . . . puis ajoute à la file les deux enfants du nœud qui vient d’en être
retiré
visite(X)
Le parcours en largeur appliqué à notre exemple d’expression arithmétique (cf. la
figure A.1) donne l’ordre hiérarchique + − + x ∗ a / 5 z x 3.