Algo AB Largeur

Identification

Infoforall

16 - Parcours en largeur


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 ✎ :

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

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...

Parcours en largeur

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

2 - Algorithme de parcours en largeur

En Français

L'algorithme consiste à :

  1. Enfiler l'arbre dans une file
  2. Tant que la file n'est pas vide
    1. Défiler le prochain arbre
    2. Explorer la racine de l'arbre
    3. Enfiler les enfants gauche et droite de cet arbre dans la file si ce ne sont pas des arbres vides.

En version algorithme

Algorithme du parcours en largeur

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)

      fnouvelleFile()

      enfiler(arbre, f)

      TANT QUE NON estFileVide(f)


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

        arbre_en_coursdefiler(f)

        explorer(racine(arbre_en_cours))


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

        ggauche(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

        ddroite(arbre_en_cours)

        SI NON estArbreVide(d)

          enfiler(d, f)

        Fin Si

      Fin Tant Que

    Fin Si

    Renvoyer 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.

Arbre exercice

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

...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) acad (arrière)


Contenu de la File (v2 ): (arrière) adac (avant)

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.

Arbre de la partie 1

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) acae (arrière)


...CORRECTION...

Contenu de la File : vide


On enfile aa : aa

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


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


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


On défile (G) et on enfile ah : (avant) abadafah (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

...arbre_binaire_ifa.py...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
'''Module implémentant un Arbre Binaire (AB) Classes non accessibles implémentant l'Arbre Binaire (hors interface) --------------------------------------------------------------------- CLASSE Noeud Attributs (accessibles en lecture directement) + cle : la valeur de la clé / étiquette associé à ce noeud + data : les données qu'on veut y stocker CLASSE AB Attributs (accessibles en lecture directement) + racine : la référence du noeud-racine de l'arbre + gauche : la référence du sous-arbre gauche + droite : la référence du sous-arbre droit Méthodes : + ajout_a_gauche(sous_arbre:Arbre) + ajout_a_droite(sous_arbre:Arbre) CLASSES créée uniquement pour faciliter la documentation des pre et post conditions + Cle : pour dire qu'on veut ou renvoie une clé + Data : pour dire qu'on veut ou renvoie les données associées + Arbre : pour dire qu'on veut ou renvoie un AB ou None (Arbre Vide) Fonctions d'Interface permettant de gérer l'Arbre Binaire (interface) --------------------------------------------------------- + nvAV() -> Arbre + nvAB(racine:Noeud, g:Arbre=None, d:Arbre=None) -> AB + estArbreVide(arbre:Arbre) -> bool + racine(arbre:Arbre) -> Noeud + gauche(arbre:Arbre) -> Arbre + droite(arbre:Arbre) -> Arbre + nvND(cle:Cle, data:Data) -> Noeud + data(noeud:Noeud) -> Data + cle(noeud:Noeud) -> Cle ''' # Importation # Déclaration des fausses classes (pour la documentation) class Cle: pass class Data: pass class Arbre: pass # AB ou Arbre vide # Déclaration des classes (hors interface) class Noeud: '''Implémentation d'un noeud sous forme d'objet''' def __init__(self, cle, data=None): '''Méthode-initialisateur ou méthode-constructeur :: param cle(voir type_cle) :: la clé associée au noeud :: param data(divers) :: les données associée au noeud :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Initialisation des attributs utilisés self.cle = cle # La clé associée au noeud self.data = data # Les données à stockées class AB: '''Implémentation d'un Arbre Binaire sous forme d'objet''' def __init__(self, racine, type_cle=str, gauche=None, droite=None): '''Méthode-initialisateur ou méthode-constructeur :: param racine(Noeud) :: la racine de l'Arbre :: param type_cle(type) :: le type attendu des clés des noeuds de cet arbre :: param gauche(AB|None) :: le sous-arbre binaire gauche (qui peut être Vide/None) :: param droite(AB|None) :: le sous-arbre binaire droite (qui peut être Vide/None) :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur racine, gauche et droite assert isinstance(racine, Noeud) assert type(racine.cle) == type_cle assert gauche is None or isinstance(gauche, AB) assert droite is None or isinstance(droite, AB) # Initialisation des attributs utilisés self.racine = racine # Référence du noeud-racine self.gauche = gauche # Référence du sous-arbre gauche self.droite = droite # Référence du sous-arbre droite def ajout_a_gauche(self, sous_arbre:Arbre): '''Méthode d'ajout d'un sous-arbre gauche :: param self(AB) :: l'arbre non vide à modifier :: param sous_arbre(AB|None) :: le sous-arbre binaire à ajouter à gauche :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur les sous-arbres à rajouter assert sous_arbre is None or isinstance(sous_arbre, AB) # Modification du sous-arbre gauche self.gauche = sous_arbre def ajout_a_droite(self, sous_arbre:Arbre): '''Méthode d'ajout d'un sous-arbre droite :: param self(AB) :: l'arbre non vide à modifier :: param sous_arbre(AB|None) :: le sous-arbre binaire à ajouter à droite :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur les sous-arbres à rajouter assert sous_arbre is None or isinstance(sous_arbre, AB) # Modification du sous-arbre gauche self.droite = sous_arbre # Fonctions d'interface accessibles de l'extérieur def nvND(cle:Cle, data:Data=None) -> Noeud: return Noeud(cle, data) def cle(noeud:Noeud) -> Cle: '''Renvoie la clé du noeud''' if isinstance(noeud, Noeud): return noeud.cle elif DEBUG: print("L'argument envoyé n'est pas un Noeud") def data(noeud:Noeud) -> Data: '''Renvoie les données associées au noeud''' if isinstance(noeud, Noeud): return noeud.data elif DEBUG: print("L'argument envoyé n'est pas un Noeud") def nvAV() -> Arbre: return None def nvAB(racine:Noeud, g:Arbre=nvAV(), d:Arbre=nvAV()) -> AB: return AB(racine, gauche=g, droite=d) def estArbreVide(arbre:Arbre) -> bool: '''True si l'arbre est vide''' return arbre == None def racine(arbre:Arbre) -> Noeud: '''Renvoie la référence du noeud Racine de l'Arbre Binaire (arbre peut être vide)''' if isinstance(arbre, AB): return arbre.racine elif DEBUG and not estArbreVide(arbre): print("L'argument envoyé n'est pas un Arbre") def gauche(arbre:Arbre) -> Arbre: '''Renvoie le sous-arbre gauche de l'arbre (arbre peut être vide)''' if isinstance(arbre, AB): return arbre.gauche elif DEBUG and not estArbreVide(arbre): print("L'argument envoyé n'est pas un Arbre") def droite(arbre:Arbre) -> Arbre: '''Renvoie le sous-arbre droit de l'arbre (arbre peut être vide)''' if isinstance(arbre, AB): return arbre.droite elif DEBUG and not estArbreVide(arbre): print("L'argument envoyé n'est pas un Arbre") # Programme de test du module DEBUG = False if __name__ == "__main__": DEBUG = True # Pour voir les messages d'erreur ad = nvAB(nvND("D")) af = nvAB(nvND("F"), g=ad) ae = nvAB(nvND("E"), d=af) ah = nvAB(nvND("H")) ag = nvAB(nvND("G"), d=ah) ab = nvAB(nvND("B")) ac = nvAB(nvND("C"), g=ag, d=ab) aa = nvAB(nvND("A"), g=ac, d=ae)

...file_ifa.py...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
'''Module implémentant une File (sous forme de Cellules Chainées) Classes non accessibles implémentant la File -------------------------------------------- CLASSE Cellule Attributs (accessibles en lecture directement) + v : la valeur des données qu'on veut y stocker + s : la référence de la Cellule suivante CLASSE File Attributs (accessibles en lecture directement) + avant : la référence de la Cellule Avant (lecture) : Tête de liste chaînée + arriere : la référence de la Cellule Arrière (insertion) : Dernière Cellule + nombre : le nombre d'éléments dans la File Méthodes : + renvoyerCelluleFinale : renvoie la Cellule Arriere connaissant l'Avant CLASSES pour faciliter la documentation des pre et post conditions + Elt : la donnée à stocker dans la Cellule Fonctions d'Interface permettant de gérer la File --------------------------------------------------------------------- + nvFile() -> File + estFileVide(f:File) -> bool + enfiler(x:Elt, f:File) -> None + lireAvant(f:File) -> Elt + defiler(f:File) -> Elt + taille(f:File) -> int + representationFile(f:File) -> str ''' # Déclaration des classes créées pour les documentations rapides dans le prototype class Elt: pass # Déclaration des classes Cellule et File class Cellule: '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant): assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self): if self.s == None: return self else: return self.s.renvoyerCelluleFinale() class File: '''Classe implémentant une Liste sous forme Liste chaînée ''' def __init__(self): self.avant = None self.arriere = None self.nombre = 0 def __str__(self): return representationFile(self) # Fonction d'observation qui n'a rien à faire dans l'interface d'une File ! def representationFile(f): '''Fonction debug, ce n'est pas une fonction d'interface.''' if not estFileVide(f): tableau = recupererValeur(f.avant) reponse = "" for element in tableau: reponse = " -> " + str(element) + reponse reponse = "(arrière) " + reponse + " (avant)" else: reponse = None return reponse def recupererValeur(cellule): if cellule.s == None: return [cellule.v] else: return [cellule.v] + recupererValeur(cellule.s) # Fonctions d'interface de la File def nvFile() -> File: '''Renvoie la référence d'une File vide''' return File() def estFileVide(f:File) -> bool: '''Fonction booléenne qui teste si f est une File vide''' return f.nombre == 0 def enfiler(x:Elt, f:File) -> None: '''On insére la nouvelle valeur x à l'arrière de f (f peut être vide)''' if estFileVide(f): # C'est vide : Avant et Arrière sont la même Cellule cellule = Cellule(x, None) f.avant = cellule f.arriere = cellule f.nombre = 1 else: # Il y a déja une cellule Arrière : on lui rajoute une suite cellule = Cellule(x, None) f.arriere.s = cellule # on rajoute la cellule à la suite de l'actuelle arrière f.arriere = cellule # on déclare la nouvelle cellule comme l'arrière f.nombre = f.nombre + 1 def lireAvant(f:File) -> Elt: '''On lit le contenu de l'Avant de la File f (f peut être vide)''' if not estFileVide(f): return f.avant.v def defiler(f:File) -> Elt: '''On supprime et renvoie l'Arrière de la File f (f peut être vide)''' if not estFileVide(f): reponse = f.avant.v # on mémorise l'ancienne valeur à l'avant f.avant = f.avant.s # la nouvelle Cellule avant est le successeur de la précédente if f.avant == None: # si l'avant n'existe pas en réalité f.arriere = None f.nombre = f.nombre - 1 return reponse # on renvoie la valeur supprimée def taille(f:File) -> int: '''Renvoie la taille de la File f''' return f.nombre if __name__ == '__main__': f = nvFile() rajout = [5,10,15,20] for elt in rajout: enfiler(elt, f) print(representationFile(f)) defiler(f) print(representationFile(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 :

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

📁 algoParcoursLargeur

📄 arbre_binaire_ifa.py

📄 file_ifa.py

📄 programme_parcours.py

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
# Importations from arbre_binaire_ifa import nvAV from arbre_binaire_ifa import nvAB from arbre_binaire_ifa import estArbreVide from arbre_binaire_ifa import racine from arbre_binaire_ifa import gauche from arbre_binaire_ifa import droite from arbre_binaire_ifa import nvND from arbre_binaire_ifa import cle from arbre_binaire_ifa import data from file_ifa import nvFile from file_ifa import estFileVide from file_ifa import enfiler from file_ifa import defiler from file_ifa import taille as tailleFile # Déclarations des fausses classes (pour la documentation) class Cle: pass class Data: pass class Arbre: pass class File: pass # Déclarations des fonctions def hauteur(arbre:Arbre, profondeur_vide=-1) -> int: '''Renvoie la hauteur de l'Arbre Binaire (arbre peut être vide)''' if estArbreVide(arbre): return profondeur_vide else: return 1 + max(hauteur(gauche(arbre)), hauteur(droite(arbre))) def nb_feuilles(arbre:Arbre) -> int: '''Renvoie le nombre de feuilles de l'Arbre Binaire (arbre peut être vide)''' if estArbreVide(arbre): return 0 elif estArbreVide(gauche(arbre)) and estArbreVide(droite(arbre)): return 1 else: return nb_feuilles(gauche(arbre)) + nb_feuilles(droite(arbre)) def taille(arbre:Arbre) -> int: '''Renvoie la taille de l'Arbre Binaire (arbre peut être vide)''' if estArbreVide(arbre): return 0 elif estArbreVide(gauche(arbre)) and estArbreVide(droite(arbre)): return 1 else: return 1 + taille(gauche(arbre)) + taille(droite(arbre)) def estPresent(arbre:Arbre, c:Cle) -> bool: '''Fonction booléenne : True si c est la clé d'un des noeuds(arbre peut être vide) ''' if estArbreVide(arbre): return False elif cle(arbre) == c: return True else: return estPresent(gauche(arbre), c) or estPresent(droite(arbre), c) def parcours_prefixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en préfixe RGD (arbre peut être vide)''' if not estArbreVide(arbre): print(cle(racine(arbre))) parcours_prefixe(gauche(arbre)) parcours_prefixe(droite(arbre)) def parcours_postfixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en postfixe GDR(arbre peut être vide)''' if not estArbreVide(arbre): parcours_postfixe(gauche(arbre)) parcours_postfixe(droite(arbre)) print(cle(racine(arbre))) def parcours_infixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en infixe GRD(arbre peut être vide)''' if not estArbreVide(arbre): parcours_infixe(gauche(arbre)) print(cle(racine(arbre))) parcours_infixe(droite(arbre)) 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 # Programme principal if __name__ == "__main__": ah = nvAB(nvND("H")) af = nvAB(nvND("F")) ag = nvAB(nvND("G")) ac = nvAB(nvND("C"), g=af, d=ag) ad = nvAB(nvND("D"), d=ah) ae = nvAB(nvND("E")) ab = nvAB(nvND("B"), g=ad, d=ae) aa = nvAB(nvND("A"), g=ab, d=ac)

...CORRECTION...

La ligne 18 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 :

Arbre de test

05° Utiliser la fonction native help pour aller retrouver la documentation (notamment le prototype pour savoir quoi envoyer).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
# Importations from arbre_binaire_ifa import nvAV from arbre_binaire_ifa import nvAB from arbre_binaire_ifa import estArbreVide from arbre_binaire_ifa import racine from arbre_binaire_ifa import gauche from arbre_binaire_ifa import droite from arbre_binaire_ifa import nvND from arbre_binaire_ifa import cle from arbre_binaire_ifa import data from file_ifa import nvFile from file_ifa import estFileVide from file_ifa import enfiler from file_ifa import defiler from file_ifa import taille as tailleFile

Par exemple :

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

06° Compléter le code de la fonction parcours_largeur pour qu'elle parvienne à implémenter l'algorithme proposé.

    arbre doit contenir l'Arbre Binaire à explorer

    SI NON estArbreVide(arbre)

      fnouvelleFile()

      enfiler(arbre, f)

      TANT QUE NON estFileVide(f)


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

        arbre_en_coursdefiler(f)

        explorer(racine(arbre_en_cours))


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

        ggauche(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

        ddroite(arbre_en_cours)

        SI NON estArbreVide(d)

          enfiler(d, f)

        Fin Si

      Fin Tant Que

    Fin Si

    Renvoyer VIDE (∅)

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

>>> parcours_largeur(aa) A B C D E F G H

...CORRECTION...

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)

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.

On lance alors le premier appel à la fonction récursive exploration_suivante qui doit recevoir la file.

1 2 3 4 5 6 7 8 9 10
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 la File f les deux prochains sous-arbres détectés''': pass

08° 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

      arbre_en_coursdefiler(f)

      explorer(racine(arbre_en_cours))


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

      ggauche(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

      ddroite(arbre_en_cours)

      SI NON estArbreVide(d)

        enfiler(d, f)

      Fin Si

      exploration_suivante(f)

On prendra toujours une fonction explorer qui ne fait qu'afficher dans la console la clé de la racine de l'arbre en cours d'exploration.

...CORRECTION...

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 la File f les deux prochains 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)

5 - FAQ

Rien pour le moment

Prochaine étape : l'Arbre Binaire de Recherche.

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