{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "#
ARBRES BINAIRES : Implémentation
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Interface\n", "* Dans cette feuille, nous allons implémenter la structure d'arbre binaire en python à l'aide la programmtion objet.\n", "* Voici les opérations de base qui seront définies :\n", " * Créer un arbre vide\n", " * Indiquer si un arbre est vide\n", " * Calculer sa taille\n", " * Calculer sa hauteur\n", " \n", "* Même s'il est possible que des noeuds aient la même valeur, on supposera ici, des raisons de simplification, que les valeurs de tous les noeuds d'un arbre considéré sont distinctes deux à deux." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Classes\n", "* Il y a de nombreuses façons de représenter un arbre binaire en python. \n", "* Une façon traditionnelle consiste à représenter chaque noeud par un objet d'une classe appelée `Noeud`. Un objet de cette classe contient trois attributs initialisés par le constructeur :\n", " * `gauche` pour le sous-arbre gauche.\n", " * `valeur` pour la valeur contenue dans le noeud.\n", " * `droite` pour le sous-arbre droit.\n", "\n", "* L'arbre vide est représenté par la valeur `None`.\n", "* Comme pour les listes chaînées, on encapsule un arbre binaire dans une classe `AB`. Chaque objet de cette classe contient un unique attribut , `racine` qui est l'arbre qu'il représente.Le constructeur de cette classe initialise cet attribut avec la valeur `None` par défaut (arbre vide).\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "class Noeud:\n", " '''Classe définissant un noeud d'arbre binaire'''\n", " def __init__(self,gauche,valeur,droite):\n", " self.gauche=gauche\n", " self.valeur=valeur\n", " self.droite=droite\n", " \n", " #Ex1\n", " def __str__(self):\n", " '''Renvoie la valeur du noeud (str)'''\n", " pass\n", " \n", "\n", "class AB:\n", " '''Classe définissant un Arbre Binaire'''\n", " def __init__(self, racine=None):\n", " self.racine=racine\n", " \n", " #Ex3\n", " def est_vide(self):\n", " '''renvoie True si et seulement si l'arbre est vide'''\n", " pass\n", " \n", " #Ex4\n", " def hauteur(self):\n", " '''renvoie la hauteur de l'arbre'''\n", " pass\n", " \n", " #Ex5\n", " def taille(self):\n", " '''renvoie la taille de l'arbre'''\n", " pass\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 1 : \n", "Ecrire la méthode `__str__(self)` de la classe `Noeud` qui affiche la valeur contenue dans un noeud." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "42\n" ] } ], "source": [ "#Afficher la valeur d'un noeud\n", "n1=Noeud(None,42,None)\n", "print(n1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 2 :\n", "Trouver deux façons de construire l'arbre ci-contre( on ne demande pas de le dessiner):\n", "" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "2\n", "3\n" ] } ], "source": [ "#méthode 1 :\n", "\n", "\n", "\n", "\n", "\n", "print(T1.racine)\n", "print(T1.racine.gauche)\n", "print(T1.racine.droite)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "2\n", "3\n" ] } ], "source": [ "#méthode 2 : \n", "\n", "print(T1.racine)\n", "print(T1.racine.gauche)\n", "print(T1.racine.droite)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Méthodes\n", "Dans cette partie , nous allons ajouter quelques fonctionnalités sur les arbres binaires. Ces méthodes sont à ajouter dans le code de définition de la classe `AB`. De par leur définition , les arbres binaires se prêtent bien à la programmation récursive." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 3 : Arbre vide\n", "Ecrire la méthode `est_vide(self)` qui renvoie `True` si l'arbre est vide , `False` sinon." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "#tests arbre vide\n", "T1=AB(Noeud(Noeud(None,2,None),1,Noeud(None,3,None)))\n", "T2=AB()\n", "assert(T1.est_vide()==False)\n", "assert(T2.est_vide()==True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 4 : Calculer la hauteur\n", "Ecrire la méthode `hauteur(self)` qui renvoie la hauteur de l'arbre. \n", "\n", "Aide : \n", "* La hauteur d'un arbre vide est $0$\n", "* Sinon, la hauteur d'un arbre est égale au maximum de la hauteur du sous-arbre gauche et du sous-arbre droit, auquel on ajoute 1." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "#tests hauteur\n", "T1=AB(Noeud(Noeud(None,2,None),1,Noeud(None,3,None)))\n", "T2=AB(Noeud(None,1,None))\n", "T3=AB()\n", "\n", "assert(T1.hauteur()==2)\n", "assert(T2.hauteur()==1)\n", "assert(T3.hauteur()==0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 5 : Calculer la taille\n", "Ecrire la méthode `taille(self)` qui renvoie la taille de l'arbre.\n", "\n", "Aide : \n", "* La taille d'un arbre vide est $0$\n", "* Sinon, la taille d'un arbre est égale à la somme de la hauteur du sous-arbre gauche et du sous-arbre droit, à laquelle on ajoute 1." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "#tests hauteur\n", "T1=AB(Noeud(Noeud(None,2,None),1,Noeud(None,3,None)))\n", "T2=AB(Noeud(None,1,None))\n", "T3=AB()\n", "\n", "assert(T1.taille()==3)\n", "assert(T2.taille()==1)\n", "assert(T3.taille()==0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Parcours\n", "\n", "Dans les exercices suivants, on utilisera l'arbre ci-contre, défini par le programme ci-dessous pour tester les fonctions de parcours en profondeur, qui seront définies récursivement.\n", "\n", "##### Exercice 6 : \n", "Ecrire la liste des sommets visités de cet arbre lors d'un parcours en profondeur :\n", "1. préfixe : \n", "2. postfixe : \n", "3. infixe : " ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "#construction de l'arbre donné en exemple.\n", "A=Noeud(None,'A',None)\n", "E=Noeud(None,'E',None)\n", "U=Noeud(None,'U',None)\n", "I=Noeud(None,'I',None)\n", "O=Noeud(None,'O',None)\n", "Y=Noeud(None,'Y',None)\n", "\n", "A.gauche=E\n", "A.droite=U\n", "E.gauche=I\n", "E.droite=O\n", "U.gauche=Y\n", "\n", "arbre=AB(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 7 : parcours en profondeur préfixe\n", "Ecrire la fonction `profondeur_prefixe(A)` qui affiche les noeuds de l'arbre `A` parcouru en profondeur préfixe.\n", "Aide :\n", "* Si l'arbre est vide, alors on s'arrête\n", "* Sinon :\n", " * On affiche la racine de l'arbre.\n", " * On parcourt en profondeur préfixe le sous-arbre gauche de l'arbre.\n", " * On parcourt en profondeur préfixe le sous-arbre droit de l'arbre.\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "def profondeur_prefixe(A):\n", " '''Affiche les noeuds de l'arbre A\n", " parcouru en profondeur préfixe'''\n", " \n", " pass" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A E I O U Y " ] } ], "source": [ "profondeur_prefixe(arbre) # A E I O U Y" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 8 : parcours en profondeur postfixe\n", "Ecrire la fonction `profondeur_postfixe(A)` qui affiche les noeuds de l'arbre `A` parcouru en profondeur postfixe.\n", "Aide :\n", "* Si l'arbre est vide, alors on s'arrête\n", "* Sinon :\n", " * On parcourt en profondeur postfixe le sous-arbre gauche de l'arbre.\n", " * On parcourt en profondeur postfixe le sous-arbre droit de l'arbre.\n", " * On affiche la racine de l'arbre.\n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def profondeur_postfixe(A):\n", " '''Affiche les noeuds de l'arbre A\n", " parcouru en profondeur préfixe'''\n", " \n", " pass\n" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I O E Y U A " ] } ], "source": [ "profondeur_postfixe(arbre) # I O E Y U A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 9 : parcours en profondeur infixe\n", "Ecrire la fonction `profondeur_infixe(A)` qui affiche les noeuds de l'arbre `A` parcouru en profondeur infixe.\n", "Aide :\n", "* Si l'arbre est vide, alors on s'arrête\n", "* Sinon :\n", " * On parcourt en profondeur préfixe le sous-arbre gauche de l'arbre.\n", " * On affiche la racine de l'arbre.\n", " * On parcourt en profondeur préfixe le sous-arbre droit de l'arbre.\n" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "def profondeur_infixe(A):\n", " '''Affiche les noeuds de l'arbre A\n", " parcouru en profondeur préfixe'''\n", " \n", " pass" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I E O A Y U " ] } ], "source": [ "profondeur_infixe(arbre) # I E O A Y U" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. Exercices" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "##### Exercice 10 : Affichage d'un arbre\n", "\n", "Il est difficile de visualiser un arbre défini avec les classes et méthodes précédentes. Le but de cet exercice est d'écrire une fonction qui affiche la représentation d'un arbre à l'aide parenthèses ouvrantes et fermantes.\n", "L'arbre ci-contre sera représenté ainsi : `((2)1(3))`\n", "\n", "PARTIE A :\n", "\n", "1. Ecrire la représentation de l'arbre suivant.\n", "\n", "\n", "\n", "2. Dessiner l'arbre dont la représentation est : `((B(C))A(D))`\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "3. D'une manière générale, décrire comment retrouver l'arbre à partir de cette écriture aec les parenthèses.\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "PARTIE B : \n", "\n", "\n", "\n", "Ecriture de la fonction `affiche(arbre)` qui prend en paramètre un arbre et qui affiche sa représentation.Les tests seront effectués sur l'arbre ci-contre :\n", "\n", "\n", "1. Donner le résultat de la foncction `affiche` sur cet arbre : `(((I)E(O))A((Y)U))`\n", "2. Voici le descriptif de cette fonction :\n", " * Si l'arbre est vide alors on sort de la fonction.\n", " * On ouvre une parenthèse.\n", " * On affiche le sous-arbre gauche.\n", " * On affiche la valeur de la racine.\n", " * On affiche le sous-arbre droite.\n", " * On ferme une parenthèse.\n", " \n", "Ecrire ci-dessous la fonction.\n" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(((I)E(O))A((Y)U))" ] } ], "source": [ "def affiche(arbre):\n", " pass\n", "\n", "affiche(arbre)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 11 : Arbre binaire parfait\n", "\n", "Un arbre binaire parfait est un arbre binaire dont chaque noeud(sauf les feuilles) possède exactement deux enfants.Toutes les feuilles sont à la même profondeur.\n", "Voici un arbre binaire parfait de hauteur 5 :\n", "\n", "\n", "\n", "Ecrire la fonction `parfait(h)` qui prend en paramètre la hauteur de l'arbre souhaité et qui renvoie un arbre parfait de hauteur `h`.\n", "\n", "Aide : \n", "* Si `h` vaut $0$, on construit l'arbre vide.\n", "* Sinon, Il suffit de construire l'arbre dont la racine est `h`, et dont les sous-arbres gauche et droite sont des arbres parfaits de hauteur `h-1`.\n", "* On pourra supposer que la valeur des noeuds est `h` (récursivement)" ] }, { "cell_type": "code", "execution_count": 68, "metadata": {}, "outputs": [], "source": [ "def parfait(h):\n", " '''Construit un arbre binaire parfait de hauteur h\n", " h : entier >= 0\n", " return : un arbre binaire '''\n", " \n", " pass" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "((1)2(1))" ] } ], "source": [ "#tests arbre parfait\n", "A2=parfait(2)\n", "affiche(A2) # ((1)2(1))" ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "((((1)2(1))3((1)2(1)))4(((1)2(1))3((1)2(1))))" ] } ], "source": [ "A4=parfait(4)\n", "affiche(A4) #((((1)2(1))3((1)2(1)))4(((1)2(1))3((1)2(1))))" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [], "source": [ "A0=parfait(0)\n", "affiche(A0) #rien !" ] } ], "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.5" } }, "nbformat": 4, "nbformat_minor": 4 }