{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Algorithmes sur les arbres binaires\n", "> Cours NSI Terminale - Thème 5.\n", "- toc: true \n", "- badges: true\n", "- comments: false\n", "- categories: [python, NSI, Terminale, Arbres binaires, Algorithmique, POO, TP]\n", "- image: images/nsi5.png" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "a42ca7e9efa722f7b312477d99c7c4d9", "grade": false, "grade_id": "cell-aaf9141db4c08dcd", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "## Algorithmes sur les arbres\n", "\n", "Dans ce classeur, nous allons mettre en oeuvre les algorithmes vus en cours. Nous partirons de deux classes : \n", "- Noeud permettant de décrire la structure d'un noeud dans un arbre binaire\n", "- Arbrebin qui est l'arbre proprement dit. Il se caractérise par\n", " - sa racine qui est un Noeud\n", " - des méthodes pour peupler cet arbre et l'afficher sous forme graphique\n", " - des méthodes que vous allez construire pour mettre le cours en pratique\n", "\n", "### Découverte des classes de base\n", "\n", "Validez les cellules suivantes et analysez bien la structure proposée." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "c56f565b8524b2048011551ed41133c1", "grade": false, "grade_id": "cell-9617d31793fa30c8", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "from graphviz import Digraph" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "9d857a21acf8782b7b3f69b113d4993b", "grade": false, "grade_id": "cell-a57a67e6efe990bb", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "class Noeud():\n", " \"\"\"Représente un noeud dans un arbre binaire\n", " - Propriétés :\n", " * valeur : valeur du noeud\n", " * gauche : noeud gauche ou None\n", " * droit : noeud droit ou None\n", " - Méthodes :\n", " * est_feuille() \n", " * __repr__() : affichage d'un noeud\"\"\"\n", " \n", " def __repr__(self):\n", " \"\"\"la méthode __repr__ définit ce qui sera affiché\n", " lorsqu'on tapera l'objet dans Jupyter ou un terminal\n", " Ici, on affiche juste la valeur du noeud\"\"\"\n", " return str(f\"## {self.valeur} ##\")\n", " \n", " def __init__(self,valeur):\n", " self.valeur = valeur\n", " self.gauche = None\n", " self.droit = None\n", " \n", " def est_feuille(self):\n", " \"\"\"Renvoie un booleen selon que le noeud est une feuille\"\"\"\n", " return self.gauche is None and self.droit is None" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "9e2fbee51e82fd16c83a6e2cc1189f62", "grade": false, "grade_id": "cell-e27ad9008dc180c0", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "class Arbrebin:\n", " \"\"\"Représente un objet arbre binaire\n", " - Propriétés : \n", " * racine : objet de type Noeud désignant la racine de l'arbre\n", " - Méthodes :\n", " * show() : représentation graphique de l'arbre à l'aide de graphviz\n", " \"\"\"\n", " \n", " def __init__(self, nd = None):\n", " # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel\n", " self.racine = nd\n", " \n", " def importe(self, tableau):\n", " \"\"\"Importe un arbre depuis un tableau\n", " [\"Noeud\", [S_A_G], [S_A_D]]\n", " [ ] désigne un arbre vide\"\"\"\n", " def importe_tableau(tableau):\n", " # Cas particuliers\n", " if tableau == []:\n", " return None\n", " if len(tableau) == 1:\n", " return Noeud(tableau[0])\n", "\n", " # tableau a une longueur >= 2\n", " nd = Noeud(tableau[0])\n", " nd.gauche = importe_tableau(tableau[1])\n", " nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None\n", " return nd\n", " \n", " self.racine = importe_tableau(tableau)\n", " \n", " def show(self):\n", " \"\"\"Renvoie un objet graphviz pour la visualisation graphique de l'arbre\"\"\"\n", " def representation(dot, noeud, aretes):\n", " # Ajoute la représentation du noeud à la représentation dot de l'arbre\n", " if noeud is not None:\n", " dot.node(str(id(noeud)), str(noeud.valeur))\n", " # Appel récursif de la fonction representation\n", " if noeud.gauche is not None:\n", " representation(dot, noeud.gauche, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.gauche))))\n", " if noeud.droit is not None:\n", " representation(dot, noeud.droit, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.droit))))\n", " \n", " dot = Digraph(comment=\"Arbre binaire\", format='svg')\n", " aretes = []\n", " representation(dot, self.racine, aretes)\n", " dot.edges(aretes)\n", " return dot" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "1741573819a5e0d332e0e6327c86fc7c", "grade": false, "grade_id": "cell-5d3953260bf87240", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "Regardons notre classe en action : Nous allons recréer l'arbre exemple du cours." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "fe555df5fbf4b59e7b9de156b6e0e6da", "grade": false, "grade_id": "cell-88998924f9174332", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "# On crée la structure d'arbre à l'aide d'un tableau [\"Noeud\", [S_A_G], [S_A_D]]\n", "arbre_liste = [\"A\",\n", " [\"B\", [\"C\",[],[\"E\"]], \n", " [\"D\"]],\n", " [\"F\", [\"G\", [\"I\"]], \n", " [\"H\",[\"J\", [\"K\"]]] ],\n", " ]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "46de645c2f4b297068327c417bc4b387", "grade": false, "grade_id": "cell-20daf286d93e2f29", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "# On crée une instance vide de notre arbre\n", "arbre = Arbrebin()\n", "# On importe le tableau ci-dessus\n", "arbre.importe(arbre_liste)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "6f52e6ad178e61d34f609c247bd33c8b", "grade": false, "grade_id": "cell-39915d6041eacd79", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "# On visualise l'arbre graphiquement\n", "arbre.show()" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "b33bb461bba44fc263e45b7fbe340f6e", "grade": false, "grade_id": "cell-1ec2dc93cb77f198", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Taille et Hauteur d'un arbre\n", "\n", "Nous allons ajouter nos premières méthodes personelles à la classe **Arbrebin**. Commençons par la taille de l'arbre. Nous avons conçu un algorithme récursif en cours se basant sur le principe que la taille d'un arbre est égal à 1 + la taille du Sous Arbre Gauche + la taille du Sous Arbre Droit. Voici une implémentation de cet algorithme dans la classe **Arbrebin**, elle vous servira de modèle pour les autres méthodes que vous aurez à implémenter dans ce TD.\n", "\n", "Vous remarquerez que pour éviter la multiplication des méthodes, nous créons une **fonction locale** `taille_arbre` qui n'est visible que dans la méthode `taille`. C'est cette fonction qui implémente en réalité l'algorithme, la méthode n'étant là que pour invoquer la fonction `taille_arbre` sur la racine de l'arbre." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "26ec05fbf38526dc70e18562ba051273", "grade": false, "grade_id": "cell-ebfb71e32c366110", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "class Arbrebin:\n", " \"\"\"Représente un objet arbre binaire\n", " - Propriétés : \n", " * racine : objet de type Noeud désignant la racine de l'arbre\n", " - Méthodes :\n", " * show() : représentation graphique de l'arbre à l'aide de graphviz\n", " \"\"\"\n", " \n", " def __init__(self, nd = None):\n", " # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel\n", " self.racine = nd\n", " \n", " def importe(self, tableau):\n", " \"\"\"Importe un arbre depuis un tableau\n", " [\"Noeud\", [S_A_G], [S_A_D]]\n", " [ ] désigne un arbre vide\"\"\"\n", " def importe_tableau(tableau):\n", " # Cas particuliers\n", " if tableau == []:\n", " return None\n", " if len(tableau) == 1:\n", " return Noeud(tableau[0])\n", "\n", " # tableau a une longueur >= 2\n", " nd = Noeud(tableau[0])\n", " nd.gauche = importe_tableau(tableau[1])\n", " nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None\n", " return nd\n", " \n", " self.racine = importe_tableau(tableau)\n", " \n", " def show(self):\n", " \"\"\"Renvoie un objet graphviz pour la visualisation graphique de l'arbre\"\"\"\n", " def representation(dot, noeud, aretes):\n", " # Ajoute la représentation du noeud à la représentation dot de l'arbre\n", " if noeud is not None:\n", " dot.node(str(id(noeud)), str(noeud.valeur))\n", " # Appel récursif de la fonction representation\n", " if noeud.gauche is not None:\n", " representation(dot, noeud.gauche, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.gauche))))\n", " if noeud.droit is not None:\n", " representation(dot, noeud.droit, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.droit))))\n", " \n", " dot = Digraph(comment=\"Arbre binaire\", format='svg')\n", " aretes = []\n", " representation(dot, self.racine, aretes)\n", " dot.edges(aretes)\n", " return dot\n", " \n", " def taille(self):\n", " \"\"\"Renvoie la taille de l'arbre\"\"\"\n", " def taille_arbre(nd):\n", " # condition d'arrêt\n", " if nd is None:\n", " return 0\n", " # Appel récursif\n", " return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)\n", " \n", " return taille_arbre(self.racine)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "0010c6f802e2cdaeedf4f6ba7b82d5d7", "grade": false, "grade_id": "cell-56cf2c08022a7afa", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "# Utilisation sur l'arbre exemple :\n", "\n", "# On instancie notre arbre\n", "arbre = Arbrebin()\n", "arbre.importe(arbre_liste)\n", "\n", "# On invique la méthode taille\n", "arbre.taille()" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "ef0cd9a7a148cab64a2f68f58ad1ed23", "grade": false, "grade_id": "cell-e24ac4efd889c198", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "#### A vous de jouer\n", "\n", "En utilisant le même modèle que pour la taille, vous allez implémenter la méthode `hauteur` déterminant la hauteur de l'arbre. Vous complèterez donc la cellule ci-dessous et vérifierez qu'elle passe bien le test." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "457fd4a57709b23cee737f00acff8476", "grade": false, "grade_id": "cell-038247cf1106e3ad", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "class Arbrebin:\n", " \"\"\"Représente un objet arbre binaire\n", " - Propriétés : \n", " * racine : objet de type Noeud désignant la racine de l'arbre\n", " - Méthodes :\n", " * show() : représentation graphique de l'arbre à l'aide de graphviz\n", " \"\"\"\n", " \n", " def __init__(self, nd = None):\n", " # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel\n", " self.racine = nd\n", " \n", " def importe(self, tableau):\n", " \"\"\"Importe un arbre depuis un tableau\n", " [\"Noeud\", [S_A_G], [S_A_D]]\n", " [ ] désigne un arbre vide\"\"\"\n", " def importe_tableau(tableau):\n", " # Cas particuliers\n", " if tableau == []:\n", " return None\n", " if len(tableau) == 1:\n", " return Noeud(tableau[0])\n", "\n", " # tableau a une longueur >= 2\n", " nd = Noeud(tableau[0])\n", " nd.gauche = importe_tableau(tableau[1])\n", " nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None\n", " return nd\n", " \n", " self.racine = importe_tableau(tableau)\n", " \n", " def show(self):\n", " \"\"\"Renvoie un objet graphviz pour la visualisation graphique de l'arbre\"\"\"\n", " def representation(dot, noeud, aretes):\n", " # Ajoute la représentation du noeud à la représentation dot de l'arbre\n", " if noeud is not None:\n", " dot.node(str(id(noeud)), str(noeud.valeur))\n", " # Appel récursif de la fonction representation\n", " if noeud.gauche is not None:\n", " representation(dot, noeud.gauche, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.gauche))))\n", " if noeud.droit is not None:\n", " representation(dot, noeud.droit, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.droit))))\n", " \n", " dot = Digraph(comment=\"Arbre binaire\", format='svg')\n", " aretes = []\n", " representation(dot, self.racine, aretes)\n", " dot.edges(aretes)\n", " return dot\n", " \n", " def taille(self):\n", " \"\"\"Renvoie la taille de l'arbre\"\"\"\n", " def taille_arbre(nd):\n", " # condition d'arrêt\n", " if nd is None:\n", " return 0\n", " # Appel récursif\n", " return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)\n", " \n", " return taille_arbre(self.racine)\n", " \n", " def hauteur(self):\n", " \"\"\"Renvoie la hauteur de l'arbre\"\"\"\n", " def hauteur_arbre(nd):\n", " # YOUR CODE HERE\n", " raise NotImplementedError()\n", " \n", " return hauteur_arbre(self.racine)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "fd1cacf8308d08ec4041c11fc7c40443", "grade": true, "grade_id": "cell-0ecd4ecd2eeaa70a", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "# Cellule de tests\n", "arbre = Arbrebin()\n", "arbre.importe(arbre_liste)\n", "\n", "assert arbre.hauteur() == 5\n", "# On indique la méthode taille" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "251f754593ac98fd6fbf1ab8d63235ca", "grade": false, "grade_id": "cell-126a27221dc9d0c6", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Parcours en profondeur\n", "Voici la méthode permettant le parcours en profondeur préfixe.\n", "0. Ajoutez-la à la classe Arbrebin\n", "0. Vérifiez son bon fonctionnement\n", "0. Implémentez de même les parcours suffixe et infixe.\n", "0. Validez votre travail grâce à la cellule de tests. \n", "\n", "Vous ferez attention de choisir les mêmes noms de méthodes que dans la cellule de test pour passer ces derniers avec succès.\n", "```python\n", " def parcours_prefixe(self):\n", " \"\"\"Renvoie la liste des noeuds dans un parcours Prefixe\"\"\"\n", " def prefixe(noeud):\n", " # Condition d'arrêt\n", " if noeud is None:\n", " return []\n", " # Appel récursif et renvoi réponse\n", " # La valeur est insérée AVANT les appels\n", " return [noeud.valeur] + prefixe(noeud.gauche) + prefixe(noeud.droit)\n", " \n", " return prefixe(self.racine)\n", " ```" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "5dcfa228880cd381796809324b0cced9", "grade": false, "grade_id": "cell-6ccb6cf1e7a4d9f7", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "class Arbrebin:\n", " \"\"\"Représente un objet arbre binaire\n", " - Propriétés : \n", " * racine : objet de type Noeud désignant la racine de l'arbre\n", " - Méthodes :\n", " * show() : représentation graphique de l'arbre à l'aide de graphviz\n", " \"\"\"\n", " \n", " def __init__(self, nd = None):\n", " # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel\n", " self.racine = nd\n", " \n", " def importe(self, tableau):\n", " \"\"\"Importe un arbre depuis un tableau\n", " [\"Noeud\", [S_A_G], [S_A_D]]\n", " [ ] désigne un arbre vide\"\"\"\n", " def importe_tableau(tableau):\n", " # Cas particuliers\n", " if tableau == []:\n", " return None\n", " if len(tableau) == 1:\n", " return Noeud(tableau[0])\n", "\n", " # tableau a une longueur >= 2\n", " nd = Noeud(tableau[0])\n", " nd.gauche = importe_tableau(tableau[1])\n", " nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None\n", " return nd\n", " \n", " self.racine = importe_tableau(tableau)\n", " \n", " def show(self):\n", " \"\"\"Renvoie un objet graphviz pour la visualisation graphique de l'arbre\"\"\"\n", " def representation(dot, noeud, aretes):\n", " # Ajoute la représentation du noeud à la représentation dot de l'arbre\n", " if noeud is not None:\n", " dot.node(str(id(noeud)), str(noeud.valeur))\n", " # Appel récursif de la fonction representation\n", " if noeud.gauche is not None:\n", " representation(dot, noeud.gauche, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.gauche))))\n", " if noeud.droit is not None:\n", " representation(dot, noeud.droit, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.droit))))\n", " \n", " dot = Digraph(comment=\"Arbre binaire\", format='svg')\n", " aretes = []\n", " representation(dot, self.racine, aretes)\n", " dot.edges(aretes)\n", " return dot\n", " \n", " def taille(self):\n", " \"\"\"Renvoie la taille de l'arbre\"\"\"\n", " def taille_arbre(nd):\n", " # condition d'arrêt\n", " if nd is None:\n", " return 0\n", " # Appel récursif\n", " return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)\n", " \n", " return taille_arbre(self.racine)\n", " \n", " # YOUR CODE HERE\n", " raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "08835f0021353bebdeb28561ff4dda8a", "grade": true, "grade_id": "cell-33e6775f9c780fcf", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "# Cellule de tests\n", "arbre = Arbrebin()\n", "arbre.importe(arbre_liste)\n", "\n", "assert arbre.parcours_prefixe() == ['A', 'B', 'C', 'E', 'D', 'F', 'G', 'I', 'H', 'J', 'K']\n", "assert arbre.parcours_suffixe() == ['E', 'C', 'D', 'B', 'I', 'G', 'K', 'J', 'H', 'F', 'A']\n", "assert arbre.parcours_infixe() == ['C', 'E', 'B', 'D', 'A', 'I', 'G', 'F', 'K', 'J', 'H']\n" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "fa6e5c3a4f98a858f44ef3aed2248935", "grade": false, "grade_id": "cell-ce11b359c55ab394", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Parcours en largeur\n", "Pour finir, ajoutez à la classe **Arbrebin** la méthode `parcours_largeur()`\n", "\n", "Vous vérifierez votre travail avec la cellule de tests. \n", "Il pourra être utile de revoir [l'implémentation des files FIFO avec un tableau python](http://www.lecluse.fr/nsi/NSI_T/donnees/listes_piles_files/)." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "60b0d355b608b44ce0e57aa69cd0e507", "grade": false, "grade_id": "cell-07d3837e43377d91", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "class Arbrebin:\n", " \"\"\"Représente un objet arbre binaire\n", " - Propriétés : \n", " * racine : objet de type Noeud désignant la racine de l'arbre\n", " - Méthodes :\n", " * show() : représentation graphique de l'arbre à l'aide de graphviz\n", " \"\"\"\n", " \n", " def __init__(self, nd = None):\n", " # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel\n", " self.racine = nd\n", " \n", " def importe(self, tableau):\n", " \"\"\"Importe un arbre depuis un tableau\n", " [\"Noeud\", [S_A_G], [S_A_D]]\n", " [ ] désigne un arbre vide\"\"\"\n", " def importe_tableau(tableau):\n", " # Cas particuliers\n", " if tableau == []:\n", " return None\n", " if len(tableau) == 1:\n", " return Noeud(tableau[0])\n", "\n", " # tableau a une longueur >= 2\n", " nd = Noeud(tableau[0])\n", " nd.gauche = importe_tableau(tableau[1])\n", " nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None\n", " return nd\n", " \n", " self.racine = importe_tableau(tableau)\n", " \n", " def show(self):\n", " \"\"\"Renvoie un objet graphviz pour la visualisation graphique de l'arbre\"\"\"\n", " def representation(dot, noeud, aretes):\n", " # Ajoute la représentation du noeud à la représentation dot de l'arbre\n", " if noeud is not None:\n", " dot.node(str(id(noeud)), str(noeud.valeur))\n", " # Appel récursif de la fonction representation\n", " if noeud.gauche is not None:\n", " representation(dot, noeud.gauche, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.gauche))))\n", " if noeud.droit is not None:\n", " representation(dot, noeud.droit, aretes)\n", " aretes.append((str(id(noeud)) , str(id(noeud.droit))))\n", " \n", " dot = Digraph(comment=\"Arbre binaire\", format='svg')\n", " aretes = []\n", " representation(dot, self.racine, aretes)\n", " dot.edges(aretes)\n", " return dot\n", " \n", " def taille(self):\n", " \"\"\"Renvoie la taille de l'arbre\"\"\"\n", " def taille_arbre(nd):\n", " # condition d'arrêt\n", " if nd is None:\n", " return 0\n", " # Appel récursif\n", " return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)\n", " \n", " return taille_arbre(self.racine)\n", "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "2d67ad906e7184b66ad43aceca0a4bdb", "grade": true, "grade_id": "cell-64f5f1c3f8f99f2a", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "# Cellule de tests\n", "arbre = Arbrebin()\n", "arbre.importe(arbre_liste)\n", "\n", "assert arbre.parcours_largeur() == ['A', 'B', 'F', 'C', 'D', 'G', 'H', 'E', 'I', 'J', 'K']" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "7a146b62079eadaf9800063f4b6f65be", "grade": false, "grade_id": "cell-6bca387aa7cec5b8", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "## Arbres Binaires de Recherche\n", "\n", "Il est temps de passer aux arbres binaires de recherche. Un ABR est un arbre binaire particulier. Il est donc souhaitable que toutes les méthodes définies dans la classe **Arbrebin** soient aussi disponibles dans la classe **Abr** que nous allons créer. \n", "\n", "Faire un copier/coller de ces dernières serait fort maladroit. La structure d'objet nous offre un mécanisme particulièrement intéressant ici : la notion ***d'héritage***. En faisant hériter notre classe **Abr** de la classe **Arbrebin**, toutes les méthodes d'**Arbrebin** seront disponibles pour **Abr** et nous n'aurons juste qu'à nous soucier des méthodes spécifiques aux arbres binaires de recherche.\n", "\n", "### Insertion\n", "\n", "Afin de pouvoir commencer à manipuler nos ABR, nous allons implémenter la méthode `insere`. Complétez la classe ci-dessous" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "ae65767751e2fede330e27e9e60da3d6", "grade": false, "grade_id": "cell-1b06d0e4e14d718d", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "class Abr(Arbrebin):\n", " \"\"\"Arbre Binaire de Recherche\n", " Hérite de la classe Arbre binaire\"\"\"\n", " \n", " def __init__(self):\n", " \"\"\"A l'initialisation, notre arbre est vide\"\"\"\n", " self.racine = None\n", " \n", " def insere(self, valeur):\n", " \"\"\"Insère valeur dans note ABR\n", " paramètre : valeur à insérer\"\"\"\n", " def insere_noeud(nd, valeur):\n", " # insère la valeur dans nd\n", " # renvoie le noeud complété\n", " # YOUR CODE HERE\n", " raise NotImplementedError()\n", " \n", " self.racine = insere_noeud(self.racine, valeur)\n", " " ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "5f17f5d42903e54b6d8c4566547a2bcb", "grade": false, "grade_id": "cell-562086ca281b976f", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "Si votre méthode `insere` fonctionne, la cellule ci-dessous doit construire un ABR en utilisant l'arbre d'exemple.\n", "\n", "Une fois votre classe au point, changez l'ordre de parcours de l'arbre de départ pour observer l'impact\n", "sur l'ABR construit. Vous constarerez alors que l'ABR est loin d'être unique : tout dépend de l'ordre\n", "d'insertion des valeurs. Un de ces ABR sera plus efficace pour la recherche. Trouvez-vous lequel ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Vous pouvez modifier le contenu de cette cellule !\n", "# On crée un ABR vide\n", "mon_abr = Abr()\n", "# On insère les valeurs de notre arbre de départ dans un certain ordre\n", "for v in arbre.parcours_prefixe():\n", " mon_abr.insere(v)\n", "mon_abr.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "c030054232676b133b9b860bacd1f76d", "grade": true, "grade_id": "cell-43ca55462607b431", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "# Cellule de test\n", "mon_abr = Abr()\n", "for v in arbre.parcours_prefixe():\n", " mon_abr.insere(v)\n", "\n", "# les méthodes de Arbrebin sont disponibles pour Abr sans avoir eu a les recréer\n", "# c'est la magie de l'héritage\n", "\n", "assert mon_abr.hauteur() == 9" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "bc60a52d7068335440374275753a7536", "grade": false, "grade_id": "cell-07ee821eb6e5ada9", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### recherche\n", "Pour la suite de notre activité, nous changerons un peu et jouerons avec les termes d'une suite célèbre. Peut-être la reconnaîtrez-vous ! Commmençons par construire notre ABR. Que constatez-vous ? Cet arbre est-il intéressant pour rechercher une valeur ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "46b72bae09d7750513d10e589b06c8bb", "grade": false, "grade_id": "cell-e0784d64cded76de", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]\n", "suite_abr = Abr()\n", "for v in suite:\n", " suite_abr.insere(v)\n", "suite_abr.show()" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "6e6a5b98ad9175d61e17f44f87dc48c4", "grade": false, "grade_id": "cell-4d61113543cfde33", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "Pour résoudre ce problème, nos allons utiliser une technique surprenante : appeler l'aléatoire à la rescousse ! Vous allez constater qu'en mélangeant notre suite, la situation s'améliore très sensiblement ! " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "a5d8d3dbe9a1348a788d2a6db49833b7", "grade": false, "grade_id": "cell-d6e16c72829292c2", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "from random import shuffle\n", "suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]\n", "shuffle(suite)\n", "suite_abr = Abr()\n", "for v in suite:\n", " suite_abr.insere(v)\n", "suite_abr.show()" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "markdown", "checksum": "fb8e6a32104d4a83f4867462418e7b59", "grade": false, "grade_id": "cell-92fe05fdf9932307", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "Voilà qui est nettement mieux !!\n", "\n", "Vous allez maintenant pour terminer cette activité implémenter la méthode `recherche` qui prend une valeur en paramètre et renvoie un booleen selon que la valeur est dans l'arbre ou non." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "7e55be1d967863e4faf4f8b6c016e920", "grade": false, "grade_id": "cell-e5d5e4ca3e48d70c", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "class Abr(Arbrebin):\n", " \"\"\"Arbre Binaire de Recherche\n", " Hérite de la classe Arbre binaire\"\"\"\n", " \n", " def __init__(self):\n", " \"\"\"A l'initialisation, notre arbre est vide\"\"\"\n", " self.racine = None\n", " \n", "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "74439e3fba1408eca9d720124a56fb7f", "grade": true, "grade_id": "cell-0db26998ca78250a", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]\n", "shuffle(suite)\n", "suite_abr = Abr()\n", "for v in suite:\n", " suite_abr.insere(v)\n", "assert suite_abr.recherche(233)\n", "assert not suite_abr.recherche(317)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "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.8.2" } }, "nbformat": 4, "nbformat_minor": 4 }