{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "#
Arbres Binaires de Recherche (ABR) 2 : Implémentation
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Représentation en python\n", "* Un ABR est un arbre binaire. On le représente donc à l'aide des classes et méthodes précédemment définies.On supposera que les conditions d'ordre sur les valeurs des noeuds sont vérifiées dans les arbres qui seront créés.\n", "* Rappel : Un arbre binaire de recherche est un arbre binaire dont les noeuds contiennent des valeurs qui peuvent être comparées entre elles et tel que que pour tout noeud de l'arbre, toutes les valeurs situées dans le sous-arbre gauche (ou droit) sont plus petite (ou plus grande) que la valeur située dans le noeud.\n", "* En particulier, le parcours infixe d'un ABR affiche les valeurs contenues dans l'arbre par ordre croissant." ] }, { "cell_type": "code", "execution_count": 2, "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", " def __str__(self):\n", " '''Renvoie la valeur du noeud (str)'''\n", " return str(self.valeur)\n", " \n", " def ajoute(self,x):\n", " '''ajoute un noeud en modifiant\n", " les liens des noeuds entre eux'''\n", " if self.valeur is None:\n", " self.valeur=x\n", " else:\n", " if x > self.valeur:\n", " if self.droite is None:\n", " self.droite=Noeud(None,x,None)\n", " else: \n", " self.droite.ajoute(x)\n", " else:\n", " if self.gauche is None:\n", " self.gauche=Noeud(None,x,None)\n", " else: \n", " self.gauche.ajoute(x)\n", " \n", " \n", "class ABR:\n", " '''Classe définissant un Arbre Binaire de Recherche'''\n", " def __init__(self, racine=None):\n", " self.racine=racine\n", " \n", " def est_vide(self):\n", " '''renvoie True si et seulement si l'arbre est vide'''\n", " return self.racine is None\n", " \n", " def hauteur(self):\n", " '''renvoie la hauteur de l'arbre'''\n", " if self.racine is None:\n", " return 0\n", " else:\n", " return max(ABR(self.racine.gauche).hauteur(),ABR(self.racine.droite).hauteur())+1\n", "\n", " def taille(self):\n", " '''renvoie la taille de l'arbre'''\n", " if self.racine is None:\n", " return 0\n", " else:\n", " return ABR(self.racine.gauche).taille() + ABR(self.racine.droite).taille()+1\n", " \n", " def parcours_infixe(self):\n", " '''Affiche les noeuds de l'arbre \n", " parcouru en profondeur préfixe'''\n", " \n", " if self.racine is None:\n", " return # on sort de la fonction\n", " \n", " ABR(self.racine.gauche).parcours_infixe()\n", " print(self.racine, end=' ')\n", " ABR(self.racine.droite).parcours_infixe()\n", " \n", " #Ex 2 : recherche\n", " def recherche(self, x):\n", " '''Renvoie True si x appartient à l'arbre\n", " False sinon'''\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " pass\n", " \n", " \n", " def ajouter(self,x):\n", " '''ajoute le noeud de valeur x\n", " dans l'arbre binaire de recherche'''\n", " if self.racine is None:\n", " self.racine=Noeud(None,x,None)\n", " else:\n", " self.racine.ajoute(x)\n", " \n", " #Ex 4 :\n", " def minimum(self):\n", " '''Renvoie la valeur minimale\n", " contenue dans l'arbre'''\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " pass\n", " \n", " #Ex 4 :\n", " def maximum(self):\n", " '''Renvoie la valeur maximale\n", " contenue dans l'arbre'''\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " pass\n", " \n", " \n", " #Ex 6:\n", " def recherche_detail(self, x):\n", " '''Renvoie True si x appartient à l'arbre\n", " False sinon.\n", " Affiche aussi les sommets visités lors de la recherche'''\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 1:\n", "\n", "\n", "Construire l'ABR ci-contre, vérifier sa taille, sa hauteur et le résultat de son parcours infixe à l'aide des méthodes contenues dans le code précédent." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "#Réponse\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": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "4\n" ] } ], "source": [ "print(abr.hauteur())" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10\n" ] } ], "source": [ "print(abr.taille())" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "9 12 14 17 23 50 54 67 72 76 " ] } ], "source": [ "abr.parcours_infixe()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Recherche\n", "Pour chercher une valeur dans un ABR, il suffit de la comparer à la valeur à la racine puis, si elle est différente, de se diriger vers un seul des deux sous-arbres. On élimine ainsi complètement la recherche dans l'autre sous-arbre." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 2 :\n", "Dans le code de la classe, compléter la méthode `recherche(self, x)` qui renvoie `True` si la valeur x est contenue dans l'arbre et `False` sinon.\n", "\n", "Principe :\n", "* Si l'arbre est vide, on renvoie `False`\n", "* Sinon :\n", " * Si la valeur de la racine est x, on renvoie True\n", " * Si x est inférieur à la valeur de la racine, on cherche de façon récursive dans le sous-arbre gauche.\n", " * Si x est supérieur à la valeur de la racine, on cherche de façon récursive dans le sous-arbre droit." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "#test recherche dans un ABR\n", "assert(abr.recherche(50)==True)\n", "assert(abr.recherche(8)==False)\n", "assert(abr.recherche(54)==True)\n", "assert(abr.recherche(67)==True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Ajout\n", "* Pour pouvoir construire un ABR, nous allons utiliser la méthode `ajouter(self,x)` qui ajoute l'élément x dans l'arbre. Ainsi , nous allons construire un ABR par ajout successifs avec cette méthode à partir d'un arbre éventuellement vide.\n", "* En principe, ajouter un nouvel élément dans un ABR n'est pas plus compliqué que de le chercher : \n", " * S'il est plus petit, on va à gauche.\n", " * S'il est plus grand, on va à droite.\n", " * Quand on arrive à un arbre vide, on ajoute un nouveau noeud.\n", "* En pratique, c'est un peu plus compliqué, car l'ajout dans un arbre vide pose problème. Dans le code des classes, la classe `Noeud`est également modifiée pour pouvoir redéfinir le lien entre les noeuds lors d'un ajout." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 3 :\n", "Construire l'ABR représenté ci-dessous en utilisant la méthode `ajouter`.\n", "\n", "" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "#Réponse\n", "abr=ABR()\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10\n", "4\n", "17\n", "9 12 14 17 23 50 54 67 72 76 " ] } ], "source": [ "#test ajouter dans un ABR\n", "print(abr.taille()) #10\n", "print(abr.hauteur()) #4\n", "print(abr.racine.gauche) #17\n", "abr.parcours_infixe() #9 12 14 17 23 50 54 67 72 76 " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Exercices" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 4:\n", "Dans la classe `ABR`:\n", "1. Ecrire la méthode `minimum(self)` qui renvoie la valeur minimale contenue dans un ABR.\n", "2. Ecrire la méthode `maximum(self)` qui renvoie la valeur maximale contenue dans un ABR.\n", "\n", "Dans les deux cas, si l'arbre est vide, la méthode renvoie `None`.On pourra écrire de façon récursive ou pas..." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "#tests minimum et maximum sur l'arbre de l'exercice 3\n", "assert(ABR().minimum()==None)\n", "assert(abr.minimum()==9)\n", "assert(ABR().maximum()==None)\n", "assert(abr.maximum()==76)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 5 :\n", "On considère l'arbre binaire de recherche ci-dessous permettant de faciliter une recherche alphabétique :\n", "\n", "\n", "1. Construire cet arbre.\n", "2. Vérifier :\n", " * Que son parcours infixe affiche bien les lettres dans l'ordre alphabétique.\n", " * Sa taille\n", " * Sa hauteur" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z \n", "26\n", "5\n" ] } ], "source": [ "#1.\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "#2.\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Exercice 6:\n", "Dans la classe `ABR` , Ecrire la méthode `recherche_detail(self,x)` qui en plus de renvoyer `True` ou `False`(selon si x est dans l'arbre ou pas) affiche aussi la valeur de chaque noeud visité.\n" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "M\n", "F\n", "I\n", "H\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Tests recherche détail\n", "alphabet.recherche_detail('H')" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "M\n", "T\n", "P\n", "R\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "alphabet.recherche_detail('R')" ] } ], "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 }