{"cells":[{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["# TP - Correction\n","\n","## 1. Arbres binaires\n","\n","On utilisera dans ce TP l'implémentation des arbres binaire suivante utilisant les classes."]},{"cell_type":"code","execution_count":1,"metadata":{"trusted":false},"outputs":[],"source":["class Arbre:\n","    def __init__(self, etiquette):\n","        self.etiquette = etiquette\n","        self.droite = None\n","        self.gauche = None\n","    \n","        \n","mon_arbre = Arbre(\"P\")\n","mon_arbre.gauche = Arbre(\"Y\")\n","mon_arbre.droite = Arbre(\"T\")\n","mon_arbre.gauche.gauche = Arbre(\"H\")\n","mon_arbre.gauche.droite = Arbre(\"O\")\n","mon_arbre.droite.gauche = Arbre(\"N\")"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["Ceci devrait modéliser l'arbre suivant:\n","\n","![arbre1](./../data/arbre1.png)"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["## 2. Quelques méthodes pratiques\n","\n","### 2.1 Est feuille ?\n","\n","Ajouter une méthode `est_feuille` retournant `True` si l'arbre n'a ni sous arbre gauche, ni sous arbre droit."]},{"cell_type":"code","execution_count":2,"metadata":{"trusted":false},"outputs":[],"source":["class Arbre:\n","    def __init__(self, etiquette):\n","        self.etiquette = etiquette\n","        self.droite = None\n","        self.gauche = None\n","    \n","    def est_feuille(self):\n","        return self.gauche is None and self.droite is None"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["### 2.2 Taille\n","\n","Ajouter une méthode récursive `taille` à la classe Arbre retournant la taille d'un arbre. La méthode est la suivante:\n","\n","```\n","à partir de la racine:\n"," - récupérer la taille du sous arbre gauche si il existe\n"," - récupérer le taille du sous arbre droite si il existe\n"," - ajouter les deux et compter le noeud lui-meme.\n","```"]},{"cell_type":"code","execution_count":null,"metadata":{"trusted":false},"outputs":[],"source":["class Arbre:\n","    def __init__(self, etiquette):\n","        self.etiquette = etiquette\n","        self.droite = None\n","        self.gauche = None\n","        \n","    def taille(self):\n","        taille_g, taille_d = 0, 0\n","        if self.gauche is not None:\n","            taille_g = self.gauche.taille()\n","        if self.droite is not None:\n","            taille_d = self.droite.taille()\n","        return taille_g + taille_d + 1"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["### Hauteur\n","\n","Ajouter une méthode récursive `hauteur`à la classe Arbre retournant la hauteur d'un arbre. La méthode est la suivante:\n","\n","```\n","à partir de la racine:\n"," - récupérer la hauteur du sous arbre gauche si il existe\n"," - récupérer la hauteur du sous arbre droite si il existe\n"," - prendre le max des deux sous-arbres et compter le noeud lui-meme.\n","```"]},{"cell_type":"code","execution_count":3,"metadata":{"trusted":false},"outputs":[],"source":["class Arbre:\n","    def __init__(self, etiquette):\n","        self.etiquette = etiquette\n","        self.droite = None\n","        self.gauche = None\n","        \n","    def hauteur(self):\n","        hauteur_g, hauteur_d = 0, 0\n","        if self.gauche is not None:\n","            hauteur_g = self.gauche.hauteur()\n","        if self.droite is not None:\n","            hauteur_d = self.droite.hauteur()\n","        return max(hauteur_g, hauteur_d) + 1"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["## 3. Parcours\n","\n","On souhaite réaliser des parcours de ce graphe à l'aide de trois méthodes de la classe arbre: `parcours_préfixe`, `parcours_infixe` et `parcours_postfixe`.\n","\n","Les résultats prévus sont les suivants:\n","```python\n",">>> mon_arbre.parcours_prefixe()\n","'PYHOTN'\n",">>> mon_arbre.parcours_infixe()\n","'HYOPNT'\n",">>> mon_arbre.parcours_postfixe()\n","'HOYNTP'\n","```\n","\n","### 3.1 Préfixe\n","\n","1. Compléter la méthode récursive de la classe Arbre ci-dessous pour réaliser le parcours préfixe"]},{"cell_type":"code","execution_count":4,"metadata":{"trusted":false},"outputs":[],"source":["class Arbre:\n","    def __init__(self, etiquette):\n","        self.etiquette = etiquette\n","        self.droite = None\n","        self.gauche = None\n","        \n","    def parcours_prefixe(self):\n","        ch = self.etiquette\n","        if self.gauche is not None:\n","            ch += self.gauche.parcours_prefixe()\n","        if self.droite is not None:\n","            ch += self.droite.parcours_prefixe()\n","        return ch\n","    \n","mon_arbre = Arbre(\"P\")\n","mon_arbre.gauche = Arbre(\"Y\")\n","mon_arbre.droite = Arbre(\"T\")\n","mon_arbre.gauche.gauche = Arbre(\"H\")\n","mon_arbre.gauche.droite = Arbre(\"O\")\n","mon_arbre.droite.gauche = Arbre(\"N\")\n","assert mon_arbre.parcours_prefixe() == 'PYHOTN'"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["2. Combien d'appels à la fonction `parcours_prefixe` sont réalisés lors de l'appel `mon_arbre.parcours_prefixe()` ?"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["### 3.2 Infixe et postfixe\n","\n","1. Sur le même modèle créer les méthode infixe et postfixe de la classe Arbre"]},{"cell_type":"code","execution_count":6,"metadata":{"trusted":false},"outputs":[],"source":["class Arbre:\n","    def __init__(self, etiquette):\n","        self.etiquette = etiquette\n","        self.droite = None\n","        self.gauche = None\n","        \n","    def parcours_infixe(self):\n","        ch = ''\n","        if self.gauche is not None:\n","            ch += self.gauche.parcours_infixe()\n","        ch += self.etiquette\n","        if self.droite is not None:\n","            ch += self.droite.parcours_infixe()\n","        return ch\n","    \n","    def parcours_postfixe(self):\n","        ch = ''\n","        if self.gauche is not None:\n","            ch += self.gauche.parcours_postfixe()\n","        if self.droite is not None:\n","            ch += self.droite.parcours_postfixe()\n","        ch += self.etiquette\n","        return ch\n","    \n","mon_arbre = Arbre(\"P\")\n","mon_arbre.gauche = Arbre(\"Y\")\n","mon_arbre.droite = Arbre(\"T\")\n","mon_arbre.gauche.gauche = Arbre(\"H\")\n","mon_arbre.gauche.droite = Arbre(\"O\")\n","mon_arbre.droite.gauche = Arbre(\"N\")\n","assert mon_arbre.parcours_infixe() == 'HYOPNT'\n","assert mon_arbre.parcours_postfixe() == 'HOYNTP'"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["2. Refaire les trois parcours de manière à renvoyer une liste des étiquettes au lieu d'une chaine de caractères.\n","\n","Exemple:\n","```python\n",">>> mon_arbre.parcours_infixe_liste()\n","['H','Y','O','P','N','T']\n","```"]},{"cell_type":"code","execution_count":7,"metadata":{"trusted":false},"outputs":[],"source":["class Arbre:\n","    def __init__(self, etiquette):\n","        self.etiquette = etiquette\n","        self.droite = None\n","        self.gauche = None\n","    \n","    def parcours_prefixe(self):\n","        ch = [self.etiquette]\n","        if self.gauche is not None:\n","            ch.extend(self.gauche.parcours_prefixe())\n","        if self.droite is not None:\n","            ch.extend(self.droite.parcours_prefixe())\n","        return ch\n","\n","    def parcours_infixe(self):\n","        ch = []\n","        if self.gauche is not None:\n","            ch.extend(self.gauche.parcours_infixe())\n","        ch.append(self.etiquette)\n","        if self.droite is not None:\n","            ch.extend(self.droite.parcours_infixe())\n","        return ch\n","    \n","    def parcours_postfixe(self):\n","        ch = []\n","        if self.gauche is not None:\n","            ch.extend(self.gauche.parcours_postfixe())\n","        if self.droite is not None:\n","            ch.extend(self.droite.parcours_postfixe())\n","        ch.append(self.etiquette)\n","        return ch"]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["### 3.3 Parcours en largeur\n","\n","1. Réfléchir à un algorithme de parcours en largeur"]},{"cell_type":"markdown","metadata":{},"source":["Idées: "]},{"cell_type":"markdown","metadata":{"deletable":false,"editable":false},"source":["2. Implémenter une méthode `parcours_largeur` de la classe Arbre renvoyant une liste des étiquettes en réalisant un parcours en largeur."]},{"cell_type":"code","execution_count":8,"metadata":{"trusted":true},"outputs":[{"data":{"text/plain":["['P', 'Y', 'T', 'H', 'O', 'N']"]},"execution_count":8,"metadata":{},"output_type":"execute_result"}],"source":["class Arbre:\n","    def __init__(self, etiquette):\n","        self.etiquette = etiquette\n","        self.droite = None\n","        self.gauche = None\n","\n","    def parcours_largeur(self):\n","        file = [self]\n","        parcours = []\n","        while len(file) != 0:\n","            noeud_courant = file.pop(0)\n","            parcours.append(noeud_courant.etiquette)\n","            if noeud_courant.gauche is not None:\n","                file.append(noeud_courant.gauche)\n","            if noeud_courant.droite is not None:\n","                file.append(noeud_courant.droite)\n","        return parcours\n","    \n","mon_arbre = Arbre(\"P\")\n","mon_arbre.gauche = Arbre(\"Y\")\n","mon_arbre.droite = Arbre(\"T\")\n","mon_arbre.gauche.gauche = Arbre(\"H\")\n","mon_arbre.gauche.droite = Arbre(\"O\")\n","mon_arbre.droite.gauche = Arbre(\"N\")\n","mon_arbre.parcours_largeur()"]}],"metadata":{"celltoolbar":"Format de la Cellule Texte Brut","kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.11.6"}},"nbformat":4,"nbformat_minor":2}