18 - Parcours en largeur d'abord (AB)

⏪

⏬

⏩

1 - Largeur

2 - Algo

3 - Python

4 - récursive

5 - FAQ

Après les parcours en profondeur (prefixe, infixe et suffixe), nous allons aujourd'hui voir comment explorer un arbre en partant de la racine et en explorant chaque niveau, profondeur par profondeur.

Logiciel nécessaire pour l'activité : -

Prérequis :

Données : Arbre et Arbre Binaire
Algos : Parcours d'Arbres
Algos : Algorithmes des Arbres Binaires

Evaluation ✎ :

Documents de cours : open document ou pdf

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

MODE COURS (cacher les questions)

1 - Principe du parcours en largeur

⇩ ⇧ ⤊

Ce parcours consiste à d'abord explorer le niveau 1 (qui ne contient que la racine). Puis le niveau 2...

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

Résumons ce que nous allons voir:

Le parcours en Profondeur d'abord utilise une Pile (soit la pile d'appels, soit une vraie pile).
Le parcours en largeur d'abord utilise une File.

2 - Algorithme de parcours en largeur

⇩ ⇧ ⤊

(Rappel) 2.1 Parcours en profondeur d'abord, version itérative

Voir

On remplace la pile d'appels par une vraie pile.

Description de l'ALGORITHME (sans précondition) (ici prefixe RGD)

Description de parcourir(arbre: Arbre Binaire)

SI NON estABV(arbre)

p ← nouvellePileVide()

empiler(p, arbre)

TANT QUE NON estPileVide(p)

a ← depiler(p)

visiter(racine(a))

SI NON estABV(droite(a))

empiler(p, droite(a))

Fin SI

SI NON estABV(gauche(a))

empiler(p, gauche(a))

Fin SI

Fin TANT QUE

Fin SI

Renvoyer VIDE

Seul l'ordre des 3 blocs changent dans les 3 versions.

L'algorithme préfixe en français

L'algorithme consiste à :

Si l'arbre n'est pas VIDE

Empiler l'arbre dans une Pile
Tant que la Pile n'est pas vide

Dépiler le prochain arbre, nommons le a.
Explorer la racine de l'arbre a
Empiler le sous-arbre gauche de a si le sous-arbre n'est pas VIDE.
Empiler le sous-arbre gauche de a si le sous-arbre n'est pas VIDE.

2.2 Parcours en largeur d'abord, version itérative

Voir

Description de l'ALGORITHME (sans précondition)

Description de parcourir(arbre: Arbre Binaire)

SI NON estABV(arbre)

f ← nouvelleFileVide()

enfiler(f, arbre)

TANT QUE NON estFileVide(f)

a ← defiler(f)

visiter(racine(a))

SI NON estABV(gauche(a))

enfiler(f, gauche(f))

Fin SI

SI NON estABV(droite(a))

enfiler(f, droite(a))

Fin SI

Fin TANT QUE

Fin SI

Renvoyer VIDE

Seul l'ordre des 3 blocs changent dans les 3 versions.

Lien avec l'algorithme en profondeur d'abord

Il s'agit d'une modification d'un profondeur d'abord en préfixe RGD
obtenue en utilisant une File et pas une Pile
avec des phases RGD (contrairement à la version profondeur avec pile en RDG)

L'algorithme en français

L'algorithme consiste à :

Si l'arbre n'est pas VIDE

Enfiler l'arbre dans une File
Tant que la File n'est pas vide

Défiler le prochain arbre a, nommons le a.
Explorer la racine de l'arbre a
Enfiler le sous-arbre gauche de a si le sous-arbre n'est pas VIDE.
Enfiler le sous-arbre gauche de a si le sous-arbre n'est pas VIDE.

01° Appliquer l'algorithme à la main sur l'Arbre ci-dessous.

Ecrire le contenu de la File à chaque changement et signaler lorsqu'on devrait afficher un résultat.

Vous devriez aboutir à l'affichage A-B-C-D.

Correction ?

...CORRECTION...

On enfile l'arbre aa.

Contenu de la File : aa

On démarre le TANT QUE.

On défile et on travaille donc avec l'arbre aa.

Contenu de la File : VIDE

On affiche la clé de la racine : A.

On enfile le sous-arbre droite ab de l'arbre aa.

Contenu de la File : ab

Deuxième tour de TANT QUE.

On défile et on travaille donc avec l'arbre ab.

Contenu de la File : vide

On affiche la clé de la racine : B.

On enfile le sous-arbre gauche ac de l'arbre ab.

Contenu de la File : ac

On enfile le sous-arbre droite ad de l'arbre ab.

Contenu de la File (v1) : (avant) ac ← ad (arrière)

Troisième tour de TANT QUE.

On défile et on travaille donc avec l'arbre ac.

Contenu de la File : ad

On affiche la clé de la racine : C.

Aucun enfilement car les deux-sous arbres sont vides.

Quatrième tour de TANT QUE.

On défile et on travaille donc avec l'arbre ad.

Contenu de la File : vide

On affiche la clé de la racine : D.

Aucun enfilement car les deux-sous arbres sont vides.

Fin du TANT QUE car la File est vide.

02° Même question en ne fournissant que les états successifs de la File.

Début de la rédaction :

Contenu de la File : vide

On enfile aa : aa

On défile (A) et on enfile ac puis ae : (avant) ac ← ae (arrière)

Correction ?

...CORRECTION...

Contenu de la File : vide

On enfile aa : aa

On défile (A) et on enfile ac puis ae : (avant) ac ← ae (arrière)

On défile (C) et on enfile ag puis ab : (avant) ae ← ag ← ab (arrière)

On défile (D) et on enfile ad puis af : (avant) ag ← ab ← ad ← af(arrière)

On défile (G) et on enfile ah : (avant) ab ← ad ← af ← ah (arrière)

Il suffit de défiler car il ne s'agit que de feuilles.

On aura donc B - D - F - H.

3 - Implémentation et programmation en Python

⇩ ⇧ ⤊

Nous avions utilisé le module arbre_binaire_ifa, nous allons simplement rajouter le module file_ifa et importer ces fonctions d'interface permettant de gérer une File.

03° Créer la structure ci-dessous en utilisant les codes fournis pour les fichiers arbre_binaire_ifa.py et file_ifa.py.

📁 algoParcoursLargeur

📄 arbre_binaire_ifa.py

📄 file_ifa.py

Module arbre_binaire_ifa (objet)

Voir

"""Module implémentant un Arbre Binaire (AB) sous forme d'objets
"""
 
# Déclaration de la classe AB
 
class AB:
    """Implémentation d'un Arbre Binaire sous forme objet simple"""
 
    def __init__(self, valeur=None, gauche=None, droite=None):
     
        assert valeur or (valeur == None and gauche == None and droite == None)
     
        self.v = valeur
        self.g = gauche
        self.d = droite
     
        if valeur and gauche is None:
            self.g = AB()
        if valeur and droite is None:
            self.d = AB()
 
    def relier_a_gauche(self:'AB NON VIDE', sous_arbre:'AB'):
        """Méthode qui définit sous_arbre comme le sous-arbre gauche de l'arbre actif"""
        self.g = sous_arbre
 
    def relier_a_droite(self:'AB NON VIDE', sous_arbre:'AB'):
        """Méthode qui définit sous_arbre comme le sous-arbre droite de l'arbre actif"""
        self.d = sous_arbre
 
    def definir_donnees_racine(self:'AB', element:'Element NON VIDE'):
        """Méthode qui place l'élément NON VIDE en tant que racine de l'arbre"""
        self.v = element
 
    def vider(self:'AB'):
        """Méthode qui transforme l'arbre en AB VIDE"""
        self.v = None
        self.g = None
        self.d = None
 
# Fonctions d'interface (accessibles de l'extérieur)
 
def contenu(noeud:'Noeud') -> 'Element':
    """Renvoie le contenu associé au noeud fourni"""
    return noeud.v
 
def nv_ABV() -> 'AB VIDE':
    """Renvoie un nouvel Arbre Binaire Vide"""
    return AB()
 
def nv_AB(valeur:'Element', g:'AB|None'=None, d:'AB|None'=None) -> 'AB NON VIDE':
    """Renvoie un nouvel Arbre Binaire dont la racine porte valeur et qui mène aux sous-arbres g et d"""
    return AB(valeur, g, d)
 
def est_ABV(arbre:'AB') -> bool:
    """Prédicat qui renvoie True si l'arbre est vide"""
    return arbre.v is None and arbre.g is None and arbre.d is None
 
def racine(arbre:'AB NON VIDE') -> 'Noeud':
    """Renvoie le noeud-racine de l'Arbre Binaire NON VIDE"""
    return arbre  # dans cette implémentation, un AB non vide est un pointeur vers sa racine
 
def gauche(arbre:'AB NON VIDE') -> 'AB':
    """Renvoie le sous-arbre gauche de l'Arbre Binaire NON VIDE"""
    return arbre.g
 
def droite(arbre:'AB NON VIDE') -> 'AB':
    """Renvoie le sous-arbre droite de l'Arbre Binaire NON VIDE"""
    return arbre.d
 
# Programme de test du module
 
if __name__ == "__main__":
 
    ad = nv_AB("D")
    af = nv_AB("F", g=ad)
    ae = nv_AB("E", d=af)
    ah = nv_AB("H")
    ag = nv_AB("G", d=ah)
    ab = nv_AB("B")
    ac = nv_AB("C", g=ag, d=ab)
    aa = nv_AB("A", g=ac, d=ae)

Module file_ifa (deque)

Voir

"""Module implémentant une File (sous forme de deque, double ended queue)
 
Primitives permettant de gérer la File
---------------------------------------------------------------------
+ nv_FV() -> File VIDE
+ est_file_vide(f:File) -> bool
+ enfiler(f:File, x:Element) -> None
+ lire_avant(f:File NON VIDE) -> Elt
+ defiler(f:File NON VIDE) -> Elt
+ taille(f:File) -> int
 
+ representation_file(f:File) -> str
 
"""
# Importation
 
import collections
 
 
# Fonction d'observation qui n'a rien à faire dans l'interface d'une File !
 
def representation_file(f):
    """Fonction debug, ce n'est pas une fonction d'interface."""
    if not est_file_vide(f):
        tableau = list(f)
        reponse = ""
        for element in tableau:
            reponse = " -> " + str(element) +  reponse
        reponse = "(arrière) " + reponse + " (avant)"
    else:
        reponse = None
    return reponse
 
# Fonctions d'interface de la File
 
def nv_FV() -> 'File VIDE':
    """Renvoie la référence d'une File vide"""
    return collections.deque()
 
def est_file_vide(f:'File') -> bool:
    """Prédicat qui teste si f est une File vide"""
    return f == collections.deque()
 
def enfiler(f:'File', x:'Element') -> None:
    """On insére la nouvelle valeur x à l'Arrière de f"""
    f.append(x)
 
def lire_avant(f:'File NON VIDE') -> 'Element':
    """On lit le contenu de l'Avant de la File f """
    return f[0]
 
def defiler(f:'File NON VIDE') -> 'Element':
    """On supprime et renvoie l'Avant de la File f (f peut être vide)"""    
    return f.popleft()  
 
def taille(f:'File') -> int:
    """Renvoie la taille de la File f"""
    return len(f)
 
if __name__ == '__main__':
    f = nv_FV()
    rajout = [5,10,15,20]
    for elt in rajout:
        enfiler(f, elt)
        print(representation_file(f))
    defiler(f)
    print(representation_file(f))

04° Utiliser le fichier programme_parcours.py suivant. Il importe les deux ensembles de fonctions d'Interface (les primitives des Files et des Arbres Binaires).

Deux questions :

à quoi sert la ligne 15 ? Regarder notamment la ligne 45.
représenter l'arbre construit par le programme de test.

📁 algoParcoursLargeur

📄 arbre_binaire_ifa.py

📄 file_ifa.py

📄 programme_parcours.py

# Importations
 
from arbre_binaire_ifa import nv_ABV
from arbre_binaire_ifa import nv_AB
from arbre_binaire_ifa import est_ABV
from arbre_binaire_ifa import racine
from arbre_binaire_ifa import contenu
from arbre_binaire_ifa import gauche
from arbre_binaire_ifa import droite
 
from file_ifa import nv_FV
from file_ifa import est_file_vide
from file_ifa import enfiler
from file_ifa import defiler
from file_ifa import taille as taille_file
 
# Déclarations des fonctions
 
def hauteur(arbre:'AB', profondeur_vide=-1) -> int:
    """Renvoie la hauteur de l'Arbre Binaire"""
     
    if est_ABV(arbre):
        return profondeur_vide
    else:
        return 1 + max(hauteur(gauche(arbre)), hauteur(droite(arbre)))
 
def nb_feuilles(arbre:'AB') -> int:
    """Renvoie le nombre de feuilles de l'Arbre Binaire (arbre peut être vide)"""
     
    if est_ABV(arbre):
        return 0
    elif est_ABV(gauche(arbre)) and est_ABV(droite(arbre)):
        return 1
    else:
        return nb_feuilles(gauche(arbre)) + nb_feuilles(droite(arbre))
 
def taille(arbre:'AB') -> int:
    """Renvoie la taille de l'Arbre Binaire"""
     
    if est_ABV(arbre):
        return 0
    elif est_ABV(gauche(arbre)) and est_ABV(droite(arbre)):
        return 1
    else:
        return 1 + taille(gauche(arbre)) + taille(droite(arbre))
 
def est_present(arbre:'AB', c:'Clé') -> bool:
    """Prédicat : True si c est la clé d'un noeud"""
     
    if est_ABV(arbre):
        return False
    elif contenu(racine(arbre)) == c:
        return True
    else:
        return est_present(gauche(arbre), c) or est_present(droite(arbre), c)
 
def parcours_prefixe_rec(arbre:'Arbre') -> None:
    """RECURSIVE Exploration (et affichage) en profondeur en préfixe RGD (arbre peut être vide)"""
     
    if not est_ABV(arbre):
        print(contenu(racine(arbre)))
        parcours_prefixe_rec(gauche(arbre))
        parcours_prefixe_rec(droite(arbre))
 
def parcours_prefixe_ite(arbre:'Arbre') -> None:
    """ITERATIVE Exploration (et affichage) en profondeur en préfixe RGD (arbre peut être vide)"""
     
    pass
 
def parcours_largeur(arbre:'Arbre') -> None:
    """Exploration (et affichage) en largeur de l'arbre (version iterative) (arbre peut être vide)"""
     
    pass
 
def parcours_largeur_2(arbre:'Arbre') -> None:
    """Exploration (et affichage) en largeur de l'arbre (version récursive)(arbre peut être vide)"""
     
    pass
 
# Instructions du programme principal
 
if __name__ == "__main__":
 
    ah = nv_AB("H")
    af = nv_AB("F")
    ag = nv_AB("G")
    ac = nv_AB("C", g=af, d=ag)
    ad = nv_AB("D", d=ah)
    ae = nv_AB("E")
    ab = nv_AB("B", g=ad, d=ae)
    aa = nv_AB("A", g=ab, d=ac)

Correction ?

...CORRECTION...

La ligne 15 permet d'importer la fonction d'interface taille qui permet d'obtenir le nombre d'éléments dans la file. Comme il existe déjà une fonction taille dans notre programme (elle donne la taille de l'arbre binaire), on change le nom de la fonction importée.

Pour l'Arbre Binaire, il suffit de regarder ci-dessous.

Voici notre Arbre Binaire de test :

05° Utiliser 4 appels à la fonction native help pour aller retrouver la documentation (notamment le prototype pour savoir quoi envoyer) de 4 fonctions issues des modules.

# Importations
 
from arbre_binaire_ifa import nv_ABV
from arbre_binaire_ifa import nv_AB
from arbre_binaire_ifa import est_ABV
from arbre_binaire_ifa import racine
from arbre_binaire_ifa import contenu
from arbre_binaire_ifa import gauche
from arbre_binaire_ifa import droite
 
from file_ifa import nv_FV
from file_ifa import est_file_vide
from file_ifa import enfiler
from file_ifa import defiler
from file_ifa import taille as taille_file

Par exemple :


>>> help(enfiler)
Help on function enfiler in module file_ifa:
 
enfiler(f: 'File', x: 'Element') -> None
    On insére la nouvelle valeur x à l'Arrière de f

07° Donner l'algorithme du parcours en profondeur d'abord ITERATIF. Voir le rappel en début de cours si vous bloquez.

08° Ecrire la fonction python parcours_prefixe_ite() en utilisant la list Python comme une pile.

09° Donner l'algorithme du parcours en LARGEUR d'abord ITERATIF. Voir le début de cours si vous bloquez.

10° Compléter le code de la fonction parcours_largeur pour qu'elle parvienne à implémenter l'algorithme proposé. Vous utiliserez le module file_ifa.

Vous devriez parvenir à explorer les noeuds dans l'ordre suivant :


>>> parcours_largeur(aa)

A
B
C
D
E
F
G
H

Correction ?

...CORRECTION...

def parcours_largeur(arbre:'AB') -> None:
    """Exploration (et affichage) en largeur de l'arbre (version iterative)"""
    if not est_ABV(arbre):
        f = nv_FV()
        enfiler(f, arbre)
        while not est_file_vide(f):
            a =  defiler(f)
            print(contenu(racine(a)))
            g = gauche(a)
            if not est_ABV(g):
                enfiler(f, g)
            d = droite(a)
            if not est_ABV(d):
                enfiler(f, d)

4 - Version récursive

⇩ ⇧ ⤊

Nous pouvons réaliser une version récursive utilisant également une File qu'on transmettra à chaque appel. On lance donc un appel à une première fonction parcours_largeur_2(). On lui transmet l'arbre sur lequel on doit travailler.

Cette fonction va alors créer une file et y placer un unique élément : l'arbre reçu.

Ce n'est pas réellement cette fonction qui est récursive. Par contre, elle sert à lancer le premier appel à la fonction récursive exploration_suivante().

def parcours_largeur_2(arbre:'AB') -> None:
    """Exploration (et affichage) en largeur de l'arbre (version récursive)"""
    if not est_ABV(arbre):
        f = nv_FV()
        enfiler(f, arbre)
        exploration_suivante(f)
 
def exploration_suivante(f:'File') -> None:
    """Affiche la prochaine racine et stocke dans la File f les deux prochains sous-arbres détectés"""
    pass

11° Réaliser la fonction récursive exploration_suivante() pour qu'elle réagisse de cette façon :

Condition d'arrêt : la file est vide.
Cas de base : on ne renvoie rien (et donc on sort de cet appel)
Sinon, cas récursif : il s'agit du code interne au TANT QUE de l'algorithme purement itératif. Le TANT QUE est donc remplacé par un appel récursif à la fonction.

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

a ← defiler(f)

visiter(racine(a))

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

g ← gauche(a)

SI NON est_ABV(g)

enfiler(f, g)

Fin Si

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

d ← droite(a)

SI NON est_ABV(d)

enfiler(f, d)

Fin Si

Renvoyer exploration_suivante(f)

On considère toujours une fonction visiter() qui ne fait qu'afficher dans la console la clé de la racine de l'arbre en cours d'exploration.

Correction ?

...CORRECTION...

def parcours_largeur_2(arbre:'AB') -> None:
    """Exploration (et affichage) en largeur de l'arbre (version récursive)"""
    if not est_ABV(arbre):
        f = nv_FV()
        enfiler(arbre, f)
        exploration_suivante(f)
 
def exploration_suivante(f:'File') -> None:
    """Affiche la prochaine racine et stocke dans la File f les deux prochains sous-arbres détectés""":
    if est_FV(f):  # Condition d'arrêt
        return None     # Cas de base
    else:               # Cas récursif 
        a =  defiler(f)
        print(contenu(racine(a)))
        g = gauche(a)
        if not est_ABV(g):
            enfiler(f, g)
        d = droite(a)
        if not est_ABV(d):
            enfiler(f, d)
        return exploration_suivante(f)

5 - FAQ

⇩ ⇧ ⤊

Rien pour le moment

Activité publiée le 15 12 2020
Dernière modification : 31 01 2024
Auteur : ows. h.

⏪

⏫

⏩