CH10 Parcours en largeur - ELEVE.ipynb

{"cells":[{"metadata":{},"cell_type":"markdown","source":"# CH10 Parcours en largeur d'un arbre - ELEVE \n\nNous 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.\n\n\n## Ex 1 : Rappel .\nDonner l'affichage résultant de parcours infixe, postfixe et préfixe pour l'arbre binaire suivant :\n<img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/245px-Binary_search_tree.svg.png\">"},{"metadata":{},"cell_type":"markdown","source":" ### réponse :\n - préfixe : \n - infixe : \n - postfixe : "},{"metadata":{},"cell_type":"markdown","source":"## Ex 2 : Parcours en largeur d'abord.\n\nOn considère l'organigramme suivant.\n<img src=\"orga.jpg\" width=300>\n\nIl s'agit de faire la liste du personnel de direction, en respectant l'ordre hiérarchique. \nIl s'agit d'un parcours en largeur d'abord. Donner cette liste \"à la main\". "},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Ex 3. Implémentation en Python du parcours en largeur\n\nidé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. ..\n\nOn a besoin de la classe ArbreBinaire :"},{"metadata":{"trusted":true},"cell_type":"code","source":"class Noeud:\n    def __init__(self, valeur, gauche, droit):\n        self.r = valeur\n        self.g = gauche\n        self.d = droit\n\nclass ArbreBinaire:\n    def __init__(self, c):  # si le noeud = None cela signifie un arbre vide\n        self.n = c\n    def creeVide(): # c'est une methode de classe\n        return ArbreBinaire(None)\n    def creeNGD(valeur, gauche, droit):\n        return ArbreBinaire(Noeud(valeur, gauche, droit))   # c'est une méthode de classe\n    def estVide(self):\n        return self.n is None\n    def racine(self):\n        assert not(self.n is None), 'Arbre vide'\n        return self.n.r\n    def filsGauche(self):\n        assert not(self.n is None), 'Arbre vide'\n        return self.n.g\n    def filsDroit(self):\n        assert not(self.n is None), 'Arbre vide'\n        return self.n.d \n    # affichage\n    def affiche_r(self,p):# affichage parcours postfixe , p est la profondeur\n        if not self.estVide(): # recursivité\n            self.filsDroit().affiche_r(p+1)\n            print('                          '*p,self.racine())\n            self.filsGauche().affiche_r(p+1)    \n    def affiche(self):\n        self.affiche_r(0)\nvide = ArbreBinaire(None)   \ndef creeFeuille(x): #fonction pratique pour créer une feuille qui est un arbre binaire sans fils\n    return ArbreBinaire.creeNGD(x, vide, vide)","execution_count":1,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"et de la classe Queue (file) :"},{"metadata":{"trusted":true},"cell_type":"code","source":"class Queue:\n    '''\n    attribut : la liste sous jacente. Cet attribut est normalement inaccessible\n       méthodes : enqueue, dequeue, empty, size'''\n    def __init__(self):\n        self.l=[]\n    def enqueue(self,e):\n        self.l.append(e)\n    def dequeue(self):\n        if len(self.l)>0:\n            return self.l.pop(0)\n        else:\n            return None\n    def empty(self):\n        return len(self.l)==0\n    def size(self):\n        return len(self.l)\n    def __str__(self):\n        return str(self.l)","execution_count":6,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"#création de l'arbre binaire \"Organigramme\"\norga=ArbreBinaire.creeNGD('A. Michaud',\n                ArbreBinaire.creeNGD('N. Richard',creeFeuille('G. Lucas'),vide),\n                ArbreBinaire.creeNGD('M. Riboud',creeFeuille('M.Herbert'),creeFeuille('J.Martinez')))","execution_count":5,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Ex 4:\n\ncoder la fonction `largeur(arbre):` qui affiche les valeurs de l'arbre en largeur d'abord"},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":9,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"largeur(orga)","execution_count":10,"outputs":[{"name":"stdout","output_type":"stream","text":"A. Michaud\nN. Richard\nM. Riboud\nG. Lucas\nM.Herbert\nJ.Martinez\n"}]},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"language_info":{"name":"python","version":"3.7.8","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":2}