<jupyter_start><jupyter_text>CH10 Parcours en largeur d'un arbre - ELEVE Nous avons étudié 3 parcours en ***profondeur d'abord*** (infixe, postfixe, préfixe). C'est à dire qu'une branche est explorée jusqu'à la feuille avant de passer aux autres fils. Ex 1 : Rappel .Donner l'affichage résultant de parcours infixe, postfixe et préfixe pour l'arbre binaire suivant :   réponse : - préfixe :  - infixe :  - postfixe :   Ex 2 : Parcours en largeur d'abord.On considère l'organigramme suivant.Il s'agit de faire la liste du personnel de direction, en respectant l'ordre hiérarchique. Il s'agit d'un parcours en largeur d'abord. Donner cette liste "à la main".   Ex 3. Implémentation en Python du parcours en largeuridée : On stocke les noeuds dans une file. A chaque fois qu'un noeud est traité, on le supprime de la file et on enfile les fils etc. ..On a besoin de la classe ArbreBinaire :<jupyter_code>class Noeud:
    def __init__(self, valeur, gauche, droit):
        self.r = valeur
        self.g = gauche
        self.d = droit

class ArbreBinaire:
    def __init__(self, c):  # si le noeud = None cela signifie un arbre vide
        self.n = c
    def creeVide(): # c'est une methode de classe
        return ArbreBinaire(None)
    def creeNGD(valeur, gauche, droit):
        return ArbreBinaire(Noeud(valeur, gauche, droit))   # c'est une méthode de classe
    def estVide(self):
        return self.n is None
    def racine(self):
        assert not(self.n is None), 'Arbre vide'
        return self.n.r
    def filsGauche(self):
        assert not(self.n is None), 'Arbre vide'
        return self.n.g
    def filsDroit(self):
        assert not(self.n is None), 'Arbre vide'
        return self.n.d 
    # affichage
    def affiche_r(self,p):# affichage parcours postfixe , p est la profondeur
        if not self.estVide(): # recursivité
            self.filsDroit().affiche_r(p+1)
            print('                          '*p,self.racine())
            self.filsGauche().affiche_r(p+1)    
    def affiche(self):
        self.affiche_r(0)
vide = ArbreBinaire(None)   
def creeFeuille(x): #fonction pratique pour créer une feuille qui est un arbre binaire sans fils
    return ArbreBinaire.creeNGD(x, vide, vide)<jupyter_output><empty_output><jupyter_text>et de la classe Queue (file) :<jupyter_code>class Queue:
    '''
    attribut : la liste sous jacente. Cet attribut est normalement inaccessible
       méthodes : enqueue, dequeue, empty, size'''
    def __init__(self):
        self.l=[]
    def enqueue(self,e):
        self.l.append(e)
    def dequeue(self):
        if len(self.l)>0:
            return self.l.pop(0)
        else:
            return None
    def empty(self):
        return len(self.l)==0
    def size(self):
        return len(self.l)
    def __str__(self):
        return str(self.l)
#création de l'arbre binaire "Organigramme"
orga=ArbreBinaire.creeNGD('<NAME>',
                ArbreBinaire.creeNGD('<NAME>',creeFeuille('<NAME>'),vide),
                ArbreBinaire.creeNGD('<NAME>',creeFeuille('M.Herbert'),creeFeuille('J.Martinez')))<jupyter_output><empty_output><jupyter_text>Ex 4:coder la fonction `largeur(arbre):` qui affiche les valeurs de l'arbre en largeur d'abord<jupyter_code>largeur(orga)<jupyter_output><NAME>
<NAME>
<NAME>
<NAME>
M.Herbert
J.Martinez
StarcoderdataJupyterStructuredCleanDedup