TD-ImplementationArbreBinaire.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TD - Implémentation des arbres en POO\n",
    "\n",
    "On va dans ce TD créer une classe arbre binaire qui va nous permettre d'implémenter cette structure de données avec toutes ses caractéristiques.\n",
    "\n",
    "On se souvient du cours sur les arbres https://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_arbre.html dans lequel on définit le noeud racine, les sous-arbres gauche et droit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ArbreBinaire:\n",
    "    def __init__(self, valeur):       #un arbre est un noeud contenant une valeur et deux enfants gauche et droit\n",
    "        self.valeur = valeur          #le noeud contient la valeur passée en paramètre\n",
    "        self.enfant_gauche = None     #l'enfant gauche est vide au départ\n",
    "        self.enfant_droit = None      #l'enfant droit est vide au départ\n",
    "\n",
    "    def insert_gauche(self, valeur):  #on insere valeur à la racine du sous-arbre de gauche\n",
    "        if self.enfant_gauche == None:\n",
    "            self.enfant_gauche = ArbreBinaire(valeur)\n",
    "        else:\n",
    "            new_node = ArbreBinaire(valeur)\n",
    "            new_node.enfant_gauche = self.enfant_gauche\n",
    "            self.enfant_gauche = new_node\n",
    "\n",
    "    def insert_droit(self, valeur):    #on insere valeur à la racine du sous-arbre de droite\n",
    "        if self.enfant_droit == None:\n",
    "            self.enfant_droit = ArbreBinaire(valeur)\n",
    "        else:\n",
    "            new_node = ArbreBinaire(valeur)\n",
    "            new_node.enfant_droit = self.enfant_droit\n",
    "            self.enfant_droit = new_node\n",
    "            \n",
    "    def get_valeur(self):              #on renvoit la valeur du noeud racine\n",
    "        return self.valeur\n",
    "\n",
    "    def get_gauche(self):              #on renvoit le sous arbre gauche\n",
    "        return self.enfant_gauche\n",
    "\n",
    "    def get_droit(self):               #on renvoit le sous arbre droit\n",
    "        return self.enfant_droit\n",
    "    \n",
    "    def __str__(self):                 #affichage d'un arbre avec print()\n",
    "        if self!= None: #on écrit (enfantgauche)valeur(enfantdroit)\n",
    "            return \"(\"+self.enfant_gauche.__str__()+\")\"+str(self.valeur)+\"(\"+self.enfant_droit.__str__()+\")\"\n",
    "        else:\n",
    "            return \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est important de comprendre comment la structure de donnée est implémentée : un arbre est défini par une valeur et deux sous arbres gauches et droits qui sont tous les deux initialiés à <code>None</code> au démarrage.\n",
    "\n",
    "Lors de l'insertion d'une valeur à gauche ou à droite, on crée un nouvel arbre que l'on insère à la racine du sous-arbre de gauche (dans le cas de <code>insert_gauche()</code>) ou droite (dans le cas de <code>insert_droit()</code>)\n",
    "\n",
    "## Exercice 1\n",
    "Sur papier, dessinez ce qui se passe étape par étape quand vous éxécutez le code suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((None)1(None))2(None))3(None)\n"
     ]
    }
   ],
   "source": [
    "arbre=ArbreBinaire(3)\n",
    "arbre.insert_gauche(1)\n",
    "arbre.insert_gauche(2) #on insère 2 à gauche, la valeur 1 se décale à gauche du 2\n",
    "print(arbre)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 2\n",
    "Écrire le code permettant de créer l'arbre suivant\n",
    "<img src=\"nsi_term_algo_arbre_1.png\">\n",
    "\n",
    "Voila le début du code ci-dessous pour vous aider à démarrer..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((None)C(None))B(None))A(None)\n"
     ]
    }
   ],
   "source": [
    "arbre=ArbreBinaire(\"A\")\n",
    "arbre.insert_gauche(\"B\")\n",
    "arbreg=arbre.get_gauche()\n",
    "arbreg.insert_gauche(\"C\") #les deux lignes précédentes peuvent-être abbrégées en arbre.get_gauche().insert_gauche(\"C\")\n",
    "# à suivre...\n",
    "print(arbre)"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}