{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

Implémentation des Arbres binaires avec des tuples

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

1. Représentation avec un seul tuple

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Considérons l'arbre binaire suivant:\n", "\n", "

\n", "\n", "

On représente l'arbre avec le tuple :

\n", "\n", "arbre = ('1', '2', '3', '4', '5', None, '6', None, None, '7', '8', None, None, '9', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Chaque noeud se repère par son indice $n$ dans la liste,\n", "* son fils gauche se trouvant alors à l’indice : $2n+ 1$ \n", "* son fils droit à l’indice : $2n+ 2$.\n", "\n", "➄ est à l’indice 4, son fils gauche se trouve alors à l’indice 9 et son fils droit à l’indice 10.\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# on utilisera ces 2 arbres pour les tests\n", "arbre1 = ('1', '2', '3', '4', '5', None, '6', None, None, '7', '8', None, None, '9', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None)\n", "arbre2=()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Exercice 1 : Écrire une fonction booléenne qui retourne vrai si l'arbre est vide et faux sinon

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def est_vide(arbre):\n", " pass\n", "\n", "assert est_vide(arbre1)==False\n", "assert est_vide(arbre2)== True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Exercice 2 : a) Compléter la fonction enfant qui renvoie les enfants d’un noeud.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def enfant(arbre:tuple,noeud:str)->tuple:\n", " if noeud in arbre:\n", " for i in range(len(arbre)): # on doit parcourir l'arbre pour trouver l'indice i de noeud \n", " if arbre[i] == noeud:\n", " return ......\n", " \n", "print(enfant(arbre1,\"6\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

b) complèter les fonctions qui renvoient le fils gauche d’un noeud et son homologue le fils droit s’ils existent

\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def fils_g(arbre,noeud):\n", " if noeud in arbre:\n", " for i in range(len(arbre)):\n", " pass\n", " \n", "def fils_d(arbre,noeud):\n", " if noeud in arbre:\n", " for i in range(len(arbre)):\n", " pass \n", "\n", "print(fils_g(arbre1,\"6\"))\n", "print(fils_d(arbre1,\"3\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Exercice 3 : a) Écrire une fonction qui retourne vrai si le noeud est la racine de l’arbre et faux sinon

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def est_racine(arbre,noeud):\n", " if noeud in arbre:\n", " pass\n", "print(est_racine(arbre1,\"1\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

b) Écrire une fonction qui retourne vrai si le noeud est une feuille et faux sinon.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def est_feuille(arbre,noeud):\n", " if noeud in arbre:\n", " for i in range(len(arbre)):\n", " pass\n", "print(est_feuille(arbre1,\"7\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

2. Représentation avec un tuple de tuples

\n", "\n", "\n", "* Chaque noeud est un tuple de 3 élements (valeur, fg , fd )\n", "\n", "* fg et fd sont eux-mêmes des tuples éventuellement vide s'il n'éxiste pas\n", "\n", "Ci-dessous voici l'implémentation de notre arbre :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sept=(\"7\",(),())\n", "huit=(\"8\",(),())\n", "neuf=(\"9\",(),())\n", "six=(\"6\",neuf,())\n", "cinq=(\"5\",sept,huit)\n", "quatre=(\"4\",(),())\n", "trois=(\"3\",(),six)\n", "deux=(\"2\",quatre,cinq)\n", "arbre3=(\"1\",deux,trois)\n", "print(arbre3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans cette situation on accède directement aux noeuds, ce qui permet d'écrire la fonction suivante:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def est_feuille(noeud):\n", " return noeud[1] == () and noeud[2] == ()\n", "\n", "print(est_feuille(trois))\n", "print(est_feuille(sept))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Exercice 4 : La hauteur de l'arbre:

\n", "\n", "l'algorithme récursif du calcul de la hauteur de l'arbre est :\n", "\n", "\n", "\n", "attention : dans certains énoncés, la hauteur de l'arbre vide est 0 et non -1 !\n", "\n", "

Écrire la fonction hauteur

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def hauteur(arbre):\n", " pass\n", "\n", "print(hauteur(arbre3))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Pour représenter un arbre on utilisera les modules networkx et matplotlib.

\n", "

Ci-dessous le programme qui permet d'afficher un arbre :

\n", "\n", " il nécessite d'avoir réussi la fonction hauteur " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import matplotlib.pyplot as plt\n", "\n", "def repr_graph(arbre, size=(8,8), null_node=False):\n", " \"\"\"\n", " size : tuple de 2 entiers. Si size est int -> (size, size)\n", " null_node : si True, trace les liaisons vers les sous-arbres vides\n", " \"\"\"\n", " def parkour(arbre, noeuds, branches, labels, positions, profondeur, pos_courante, pos_parent, null_node):\n", " if arbre !=():\n", " noeuds[0].append(pos_courante)\n", " positions[pos_courante] = (pos_courante, profondeur)\n", " profondeur -= 1\n", " labels[pos_courante] = str(arbre[0])\n", " branches[0].append((pos_courante, pos_parent))\n", " pos_gauche = pos_courante - 2**profondeur\n", " parkour(arbre[1], noeuds, branches, labels, positions, profondeur, pos_gauche, pos_courante, null_node)\n", " pos_droit = pos_courante + 2**profondeur\n", " parkour(arbre[2], noeuds, branches, labels, positions, profondeur, pos_droit, pos_courante, null_node)\n", " elif null_node:\n", " noeuds[1].append(pos_courante)\n", " positions[pos_courante] = (pos_courante, profondeur)\n", " branches[1].append((pos_courante, pos_parent))\n", " \n", " \n", " if arbre ==():\n", " return\n", " \n", " branches = [[]]\n", " profondeur = hauteur(arbre)\n", " pos_courante = 2**profondeur\n", " noeuds = [[pos_courante]]\n", " positions = {pos_courante: (pos_courante, profondeur)} \n", " labels = {pos_courante: str(arbre[0])}\n", " \n", " if null_node:\n", " branches.append([])\n", " noeuds.append([])\n", " \n", " profondeur -= 1\n", " parkour(arbre[1], noeuds, branches, labels, positions, profondeur, pos_courante - 2**profondeur, pos_courante, null_node)\n", " parkour(arbre[2], noeuds, branches, labels, positions, profondeur, pos_courante + 2**profondeur, pos_courante, null_node) \n", "\n", " mon_arbre = nx.Graph()\n", " \n", " if type(size) == int:\n", " size = (size, size) \n", " plt.figure(figsize=size)\n", " \n", " nx.draw_networkx_nodes(mon_arbre, positions, nodelist=noeuds[0], node_color=\"white\", node_size=550, edgecolors=\"blue\")\n", " nx.draw_networkx_edges(mon_arbre, positions, edgelist=branches[0], edge_color=\"black\", width=2)\n", " nx.draw_networkx_labels(mon_arbre, positions, labels)\n", "\n", " if null_node:\n", " nx.draw_networkx_nodes(mon_arbre, positions, nodelist=noeuds[1], node_color=\"white\", node_size=50, edgecolors=\"grey\")\n", " nx.draw_networkx_edges(mon_arbre, positions, edgelist=branches[1], edge_color=\"grey\", width=1)\n", "\n", " ax = plt.gca()\n", " ax.margins(0.1)\n", " plt.axis(\"off\")\n", " plt.show()\n", " plt.close()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "repr_graph(arbre3,(4,3),False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Exercice 5 :

\n", "\n", "Écrire les fonctions suivantes\n", "\n", "Tester ces fonctions avec arbre3 defini ci-dessus" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def taille(arbre):\n", " \"\"\"fonction qui prend en paramètre d'entrée un arbre et qui renvoie le nombre de ses noeuds\"\"\"\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def est_presente(arbre,etiquette):\n", " \"\"\"fonction qui prend en paramètre d'entrée un arbre et une etiquette \n", " et renvoie True si etiquette est dans l'arbre ou False sinon\"\"\"\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def nb_feuilles(arbre):\n", " \"\"\"fonction qui prend en paramètre d'entrée un arbre et renvoie le nombre de ses feuilles\"\"\"\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Exercice 6 : Définir l'arbre2 de la fiche de cours, l'afficher et tester les fonctions précédentes sur cet arbre

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.9.7" }, "vscode": { "interpreter": { "hash": "970a2a4939579a4c22872227820a264ec023ee5692739211cbaca24386397975" } } }, "nbformat": 4, "nbformat_minor": 2 }