Infoforall

Identification

Infoforall

Résumé 18 - PARCOURS EN LARGEUR D'ABORD (AB)

⏬


Lien vers l'activité : Parcours en largeur d'abord (AB)

Dernière modif. : 31 01 2024

1 - Principe

Le parcours en largeur consiste à lire les étiquettes des noeuds de l'Arbre Binaire en les listant étage par étage, souvent de la gauche vers la droite.

Parcours en largeur

L'ordre de lecture des noeuds donne donc Alice - Bob - Clara - Didier - Eleonore...

2 - Algorithme

L'algorithme de lecture nécessite d'avoir :

  • un Arbre à lire
  • une File permettant de sortir naturellement le premier arrivé dans la File

Objectif : explorer les noeuds de l'arbre niveau par niveau.

ENTREE : arbre, l'arbre qu'on veut explorer

SORTIE : Vide (sur cet exemple), ou une réponse correspondant à la séquence des noeuds rencontrés.

La fonction explorer est à définir. Ici, on affichera juste la clé ou l'étiquette du noeud.


    arbre doit contenir l'Arbre Binaire à explorer

    SI NON estArbreVide(arbre)

      f ← nouvelleFile()

      enfiler(arbre, f)

      TANT QUE NON estFileVide(f)


        étape 1 : on extrait le prochain AB et on affiche sa racine

        arbre_en_cours ← defiler(f)

        explorer(racine(arbre_en_cours))


        étape 2 : on voit si on rajoute le sous-arbre gauche dans la File

        g ← gauche(arbre_en_cours)

        SI NON estArbreVide(g)

          enfiler(g, f)

        Fin Si


        étape 3 : on voit si on rajoute le sous-arbre droite dans la File

        d ← droite(arbre_en_cours)

        SI NON estArbreVide(d)

          enfiler(d, f)

        Fin Si

      Fin Tant Que

    Fin Si

    Renvoyer VIDE (∅)

3 - Implémentation en version itérative et récursive

1 2 3 4 5 6 7 8 9 10 11 12 13 14
def parcours_largeur(arbre:Arbre) -> None : '''Exploration (et affichage) en largeur de l'arbre (version iterative)''' if not estArbreVide(arbre): f = nvFile() enfiler(arbre, f) while not estFileVide(f): arbre_en_cours = defiler(f) print(cle(racine(arbre_en_cours))) g = gauche(arbre_en_cours) if not estArbreVide(g): enfiler(g, f) d = droite(arbre_en_cours) if not estArbreVide(d): enfiler(d, f)


On peut transformer le TANT QUE en appel récursif, plutôt que d'utiliser la version itérative.


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
def parcours_largeur_rec(arbre:Arbre) -> None: '''Exploration (et affichage) en largeur de l'arbre (version récursive)''' if not estArbreVide(arbre): f = nvFile() enfiler(arbre, f) exploration_suivante(f) def exploration_suivante(f:File) -> None: '''Affiche la prochaine racine et stocke dans f les sous-arbres détectés''': if estFileVide(f): # Condition d'arrêt return None # Cas de base else: # Cas récursif arbre_en_cours = defiler(f) print(cle(racine(arbre_en_cours))) g = gauche(arbre_en_cours) if not estArbreVide(g): enfiler(g, f) d = droite(arbre_en_cours) if not estArbreVide(d): enfiler(d, f) exploration_suivante(f)

4 - Exercice

Arbre de test

Déterminer l'ordre des noeuds affichés en montrant l'état de la File au fur et à mesure de l'avancement de la progression de l'algorithme.






⏫