I. exemple d'utilisation d'un arbre binaire
" ] }, { "cell_type": "markdown", "metadata": { "id": "s4X4qSodXe6i" }, "source": [ "On donne ci-dessous le tableau caractérisant un arbre. SAG signifie sous-arbre gauche, et SAD sous arbre-droit. " ] }, { "cell_type": "markdown", "metadata": { "id": "GBhWFn8YXe6j" }, "source": [ "| Nœud | Etiquette | Nœud du SAG | Nœud du SAD | \n", "| :--: | :--: | :--: | :--: |\n", "| 1 | * |2 | 3 | \n", "| 2 | + |4 | 5 | \n", "| 3 | - |6 | 7 | \n", "| 4 | 3 | | | \n", "| 5 | / |8 | 9 | \n", "| 6 | 8 | | | \n", "| 7 | * |10 | 11 | \n", "| 8 | 4 | | | \n", "| 9 | 2 | | | \n", "| 10 | 2 | | | \n", "| 11 | 3 | | | " ] }, { "cell_type": "markdown", "metadata": { "id": "b3PYJwSzXe6j" }, "source": [ "1. Représenter à la main sur votre cahier cet arbre \n", "\n", "\n", "\n", "
Réponse :
\n", "\n", " \n", "\n", "\n", "\n", "\n", " \n", "\n", " \n", "
\n", "Réponse :
\n", "\n", " \n", "\n", "$$\\left ( 3+\\left ( \\frac{4}{2} \\right ) \\right )*\\left ( 8-\\left ( 2*3 \\right ) \\right )$$\n", " \n", "
\n", "2. Une première possibilité d'implémentation avec une seule classe
" ] }, { "cell_type": "markdown", "metadata": { "id": "5CuUH_5_Xe6l" }, "source": [ "### a. Observez bien l'implémentation proposée suivante. Quelle est sa particularité?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Arbre :\n", " def __init__(self, val = None) :\n", " self.val = val\n", " self.fils_g = None\n", " self.fils_d = None\n", " \n", " def ajout_g(self, val) :\n", " self.fils_g = Arbre(val) # on ajoute un Noeud à gauche\n", "\n", " def ajout_d(self, val) :\n", " self.fils_d = Arbre(val) # on ajoute un Noeud à droite" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Réponse :
\n", "\n", " \n", "\n", "**La structure d'arbre est naturellement récursive**. Chaque noeud possède un sous-arbre gauche et un sous-arbre droit qui est lui-même un arbre. C'est ce que nous utilisons ici. \n", "Un arbre vide, par abus est implémenté par la valeur None, bien que None ne soit pas de type arbre binaire.\n", " \n", "
\n", "Réponse :
\n", "\n", "\n", "\n", "\n", "
\n", "Visualisation
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from visu_tree import Arbre\n", "arbre1.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si on ne veut que le sous-arbre gauche de A :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "arbre1.fils_g.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et si on ne veut que le sous-arbre gauche de B ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# A vous\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
A vous
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Créez un arbre, et visualisez-le, ainsi que certains sous-arbres." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# A vous\n" ] }, { "cell_type": "markdown", "metadata": { "id": "7PhjlUVQEZc_" }, "source": [ " \n", "
3. Une deuxième possibilité d'implémentation avec une seule classe
\n" ] }, { "cell_type": "markdown", "metadata": { "id": "VPH2t0JiEZc_" }, "source": [ "### a. Un arbre est constitué d'un nœud, d'un sous-arbre gauche et d'un sous-arbre droit." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "Lz-qWkjjT2o1" }, "outputs": [], "source": [ "class Noeud:\n", " \n", " def __init__(self, valeur, gauche = None, droit = None):\n", " self.valeur = valeur\n", " self.gauche = gauche\n", " self.droit = droit\n", " \n", " def __str__(self):\n", " return str(self.valeur) # juste la racine\n", "\n", " def estFeuille(self):\n", " if not self.gauche and not self.droit:\n", " return True\n", " else:\n", " return False" ] }, { "cell_type": "markdown", "metadata": { "id": "ZGYYRnMzXQNA" }, "source": [ "Quelles instructions faut-il écrire pour implémenter le même arbre que dans le 1.? \n", "Compléter ci-dessous" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# A vous\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Visualisation
" ] }, { "cell_type": "markdown", "metadata": { "id": "9QWq9OgTX1Ii" }, "source": [ "Testons donc ci-dessous :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from visu_arbre_3 import repr_graph\n", "repr_graph(arbre_A,(3, 3), False) # sans les feuilles fantômes. (3, 3) correspond à la taille de la représentation\n", "repr_graph(arbre_A,(3, 3), True) # avec les feuilles fantômes" ] }, { "cell_type": "markdown", "metadata": { "id": "fxKmLr-0YAcI" }, "source": [ "Autre possibilité, en imbriquant les instructions :" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "Abk7O10gYDX-" }, "outputs": [], "source": [ "arbre_A = Noeud('A', Noeud('B', Noeud('D', None, Noeud('G') ), Noeud('E')), Noeud('C', Noeud('F'), None))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 194 }, "id": "c_cldzqVYof-", "outputId": "8f4031d0-b436-449b-bd3a-7515a9aa3e02" }, "outputs": [], "source": [ "repr_graph(arbre_A,(3, 3), False) # sans les feuilles fantômes" ] }, { "cell_type": "markdown", "metadata": { "id": "lU1C96X0YwgQ" }, "source": [ "### b. La taille d'un arbre \n", "En procédant de manière analogue à celle du 1.b., écrire ci-dessous une fonction qui renvoie la taille d'un arbre" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# A vous\n", "def taille(arbre):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(taille(arbre_A))" ] }, { "cell_type": "markdown", "metadata": { "id": "GDT63o2_aI_v" }, "source": [ "### c. Hauteur d'un arbre \n", "En procédant de manière analogue à celle du 1.c., écrire ci-dessous une fonction qui renvoie la hauteur d'un arbre" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# A vous\n", "def hauteur(arbre):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(hauteur(arbre_A))" ] }, { "cell_type": "markdown", "metadata": { "id": "vELD5shEXe7B" }, "source": [ "
![\"Creative](\"https://s2.qwant.com/thumbr/700x0/f/9/436dcce5e02185c0b2e1b0e7a969aa81d7b0438d0a7f2eaee89abb9661b70b/cc-by-nc-sa.svg_.png?u=http%3A%2F%2Fopensiddur.org%2Fwp-content%2Fuploads%2F2011%2F03%2Fcc-by-nc-sa.svg_.png&q=0&b=1&p=0&a=1\")
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. \n" ] } ], "metadata": { "colab": { "collapsed_sections": [], "name": "implementation_arbres_binaires_correction_MC.ipynb", "provenance": [] }, "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.6" } }, "nbformat": 4, "nbformat_minor": 2 }