{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implémenter la classe arbre binaire\n",
    "> Cours NSI Terminale - Thème 1.\n",
    "- toc: true \n",
    "- badges: true\n",
    "- comments: false\n",
    "- categories: [python, NSI, Terminale, Structure_donnees, POO, TP]\n",
    "- image: images/nsi1.png"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a481351352d92fb2e8971080f7725530",
     "grade": false,
     "grade_id": "cell-adf696006515d75e",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Validez cette cellule pour importer graphviz\n",
    "# Ce module permet de dessiner des arbres et des graphes\n",
    "from graphviz import Digraph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "29d54e09d95c4a2bcc6dfe41cc84b6ed",
     "grade": false,
     "grade_id": "cell-c9c5cedffbb0eb20",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "Dans ce TP nous allons implémenter une classe permettant de représenter un arbre binaire. \n",
    "\n",
    "On va pour cela créer un objet **Noeud** qui aura 3 propriétés (ou attributs) :\n",
    "- La propriété **valeur** contiendra la valeur associée au noeud. \n",
    "- Les propriétés **gauche** et **droit** seront les sous arbres gauche et droit. \n",
    "\n",
    "Les deux propriétés **gauche** et **droit** seront  des instances de la classe **Noeud**. Si il n'y a pas de sous arbre gauche ou droit, on indiquera la valeur **None** dans les propriétés correspondantes.\n",
    "\n",
    "\n",
    "Dans notre classe **Noeud**, nous créerons 3 méthodes :\n",
    "- La méthode **est_feuille()** renverra un bouléen selon que l'objet est une feuille ou non.\n",
    "- La méthode **cree_feuille_gauche()** prend en paramètre une valeur et crée une feuille à gauche dont la valeur est passée en paramètres.\n",
    "- La méthode **cree_feuille_droite()** est construite sur le même modèle que **cree_feuille_gauche()**.\n",
    "\n",
    "## Exemple d'utilisation de la classe Noeud\n",
    "\n",
    "En supposant la classe **Noeud** créée, voici comment on l'utilise pour créer cet arbre\n",
    "![exemple1](my_icons/exemple1.png)\n",
    "```python\n",
    "arbre = Noeud(\"A\")\n",
    "sous_arbre_gauche = arbre.cree_fils_gauche(\"B\")\n",
    "sous_arbre_gauche.cree_fils_gauche(\"D\")\n",
    "arbre.cree_fils_droit(\"C\")\n",
    "\n",
    "# Quelques vérifications possibles\n",
    "print(arbre.est_feuille())\n",
    "print(arbre.droit.est_feuille())\n",
    "print(arbre.gauche.valeur)\n",
    "# Affiche False True B\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "01e3f14977dffd5eec876121d3846169",
     "grade": false,
     "grade_id": "cell-b31cbad2840f3f42",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class Noeud():\n",
    "    \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",
    "    \n",
    "    def __repr__(self):\n",
    "        return str(self.valeur)\n",
    "    \n",
    "    # Codez ici les méthodes demandées\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testez ici les méthodes de votre classe\n",
    "a = Noeud(2)\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d3076cc5dbd33b7a22cc79471ed2b44c",
     "grade": true,
     "grade_id": "cell-eee2cb758a9af1f2",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Tester l'exemple de départ\n",
    "\n",
    "racine = Noeud(\"A\")\n",
    "sous_arbre_gauche = racine.cree_fils_gauche(\"B\")\n",
    "sous_arbre_gauche.cree_fils_gauche(\"D\")\n",
    "racine.cree_fils_droit(\"C\")\n",
    "\n",
    "assert not racine.est_feuille()\n",
    "assert racine.droit.est_feuille()\n",
    "assert racine.gauche.valeur == \"B\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f21b8facb30deab73fc0eef315e319aa",
     "grade": false,
     "grade_id": "cell-de66d8305c8373b0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Pour aller plus loin\n",
    "\n",
    "On peut compléter cette classe **Noeud** par une nouvelle classe décrivant un objet **Arbrebin**. Un arbre va contenir le **Noeud** racine ainsi que des méthodes permettant l'affichage de l'arbre ou appliquant des algorithmes sur cet arbre.\n",
    "\n",
    "Nous verrons un peu plus tard dans l'année quelques uns de ces algorithmes. Néanmoins, pour vous donner un aperçu, voici une première ébauche de la classe **Arbrebin** qui nous sera utile pour visualiser facilement les arbres sur lesquels nous travaillerons.\n",
    "\n",
    "Dans un premier temps, il n'est pas strictement nécessaire de comprendre les détails du fonctionnement de la méthode **show** car celle-ci fait appel à de la *récursivité* qui sera étudiée un peu plus tard."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "75e9e116841ced907048b5ae1f75cbe7",
     "grade": false,
     "grade_id": "cell-bbbe2da25e6200c1",
     "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, racine):\n",
    "        self.racine = racine\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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arbre = Arbrebin(racine)\n",
    "arbre.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "1c2a01b3a3f33ad3952eb1e4e9ecc713",
     "grade": false,
     "grade_id": "cell-818c401cf1271819",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "## A vous de jouer\n",
    "\n",
    "A présent, vous utiliserez la classe **Noeud** et **Arbrebin** et les méthodes que vous avez développées pour représenter l'arbre suivant dans la variable `expr`\n",
    "![expression](my_icons/expr.png)\n",
    "\n",
    "Les opérations seront représentées par des chaînes de caractères. Les feuilles seront des entiers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "64a0eb4c96db1882d9e6ee9464c396cf",
     "grade": false,
     "grade_id": "cell-506da61b6d6152d2",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()\n",
    "expr = Arbrebin(racine)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "674737bc3e96616285bd6bc1120f3bbe",
     "grade": true,
     "grade_id": "cell-012eb21015157518",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Validation de la réponse\n",
    "assert racine.valeur == \"+\"\n",
    "assert racine.droit.valeur == 1\n",
    "\n",
    "expr.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Afficher le sous arbre gauche :\n",
    "Arbrebin(racine.gauche).show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "190d270e75d3becf02b3bef0db88a3ac",
     "grade": false,
     "grade_id": "cell-8cad58a94eb47ea7",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Conclusion\n",
    "\n",
    "Nous en resterons la pour le moment. Nous reviendrons sur les arbres plusieurs fois au cours de l'année car cette structure permet de mettre en oeuvre des algorithmes intéressants. Nous complèterons donc notre classe arbre au fur à mesure de la progression de nos conaissance, en particulier lorsque nous étudierons la récursivité."
   ]
  },
  {
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}