CH10 ABR - ELEVE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CH 10 Arbres binaires de recherche - ELEVE\n",
    "<img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/220px-Binary_search_tree.svg.png\">\n",
    "\n",
    "On rappelle qu'un arbre binaire de recherche est un arbre pour lequel on a toujours la règle suivante :\n",
    "\n",
    "**les valeurs du fils gauche <= valeur de la racine <= valeurs du fils droit**\n",
    "\n",
    "## 1  a) L'arbre ci-dessus est-il un ABR ?\n",
    "\n",
    ". . . . . . . . . . . . . . . . \n",
    "\n",
    "##  b) A quel endroit doit-on ajouter la valeur 9 ?\n",
    "\n",
    ". . . . . . . . . . . \n",
    "\n",
    "## c) Quel est l'affichage résultant d'un parcours infixe de cet arbre ?\n",
    "\n",
    ". . . . . . . . . . . . . . .\n",
    "\n",
    "\n",
    "## 2 Implémentation d'un ABR.\n",
    "\n",
    "La classe ABR **hérite** de la classe ArbreBinaire. Cela signifie qu'elle reprend les méthodes et attributs de cette classe, mais elle se permet d'en ajouter ou d'en modifier.\n",
    "\n",
    "Ici il faudra surtout apporter une méthode `ajoute()` qui permet d'ajouter une valeur en respectant les règles des ABR, et une méthode `recherche()` qui exploite avec efficacité la structure des ABR."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# RAPPEL : IMPLEMENTATION D'UN ARBRE BINAIRE\n",
    "class Noeud:\n",
    "    def __init__(self, valeur, gauche, droit):\n",
    "        self.r = valeur\n",
    "        self.g = gauche\n",
    "        self.d = droit\n",
    "class ArbreBinaire:\n",
    "    def __init__(self, c):\n",
    "        self.n = c\n",
    "    def creeVide():\n",
    "        return ArbreBinaire(None)\n",
    "    def creeNGD(valeur, gauche, droit):\n",
    "        return ArbreBinaire(Noeud(valeur, gauche, droit))\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",
    "    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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# LA CLASSE ABR hérite de la classe Arbre binaire, c'est à dire qu'elle reprend attributs et méthodes \n",
    "# mais elle peut en ajouter ou modifier certains\n",
    "class ABR(ArbreBinaire):\n",
    "    def __init__(self,c):\n",
    "        ArbreBinaire.__init__(self,c)\n",
    "    def creeNGD(valeur, gauche, droit):\n",
    "        return ABR(Noeud(valeur, gauche, droit))\n",
    "    # METHODE A AJOUTER =================================================================\n",
    "    # def cherche(self,x):\n",
    "       \n",
    "    # METHODE A AJOUTER ================================================================\n",
    "    # def ajoute(self,x):\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# implémentation de l'ABR dessiné ci-dessus\n",
    "A=ABR.creeNGD(8,\n",
    "              ABR.creeNGD(3,ABR.creeNGD(1,ABR(None),ABR(None)),\n",
    "                          ABR.creeNGD(6,ABR.creeNGD(4,ABR(None),ABR(None)),ABR.creeNGD(7,ABR(None),ABR(None)))),\n",
    "              ABR.creeNGD(10,ABR(None),ABR.creeNGD(14,ABR.creeNGD(13,ABR(None),ABR(None)),ABR(None))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                                                     14\n",
      "                                                                               13\n",
      "                           10\n",
      " 8\n",
      "                                                                               7\n",
      "                                                     6\n",
      "                                                                               4\n",
      "                           3\n",
      "                                                     1\n"
     ]
    }
   ],
   "source": [
    "# cellule pour afficher l'arbre A\n",
    "A.affiche()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.a) Rédiger la méthode cherche(self,v) -> bool\n",
    "\n",
    "Travail à faire directement dans la cellule définissant la classe ABR. On ajoutera un jeu de tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "# jeu de tests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. b) Rédiger la méthode ajoute(self,v)\n",
    "\n",
    "Travail à faire directement dans la cellule définissant la classe ABR. \n",
    "On testera en ajoutant des valeurs et en affchant à chaque fois le résultat"
   ]
  },
  {
   "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}