{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1> Implémentation Arbre binaire avec un dictionnaire </h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   \n",
    "   \n",
    "   ### On utilisera des dictionnaires\n",
    "   \n",
    "  \n",
    "   <img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/Arbre_binaire_ordonne.svg/1024px-Arbre_binaire_ordonne.svg.png\" width=\"200\" height=\"200\" />\n",
    "   \n",
    "**implémentons cet arbre à l'aide de dictionnaires**\n",
    "\n",
    "**Un noeud de l'arbre se représente par un dictionnaire dont les clés sont 'rac', 'g' et 'd'**\n",
    "* La valeur de 'rac' est la valeur du noeud\n",
    "* Les valeurs de 'g' et 'd' sont des dictionnaires pouvant contenir les arbres gauche et droit de la racine\n",
    "\n",
    "L'arbre ci-dessus se représenta ainsi:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'rac': 1, 'g': {'rac': 2, 'g': {'rac': 4, 'g': {}, 'd': {}}, 'd': {'rac': 5, 'g': {'rac': 7, 'g': {}, 'd': {}}, 'd': {'rac': 8, 'g': {}, 'd': {}}}}, 'd': {'rac': 3, 'g': {}, 'd': {'rac': 6, 'g': {'rac': 9, 'g': {}, 'd': {}}, 'd': {}}}}\n"
     ]
    }
   ],
   "source": [
    "n9={'rac':9,'g':{},'d':{}} \n",
    "n8={'rac':8,'g':{},'d':{}}\n",
    "n7={'rac':7,'g':{},'d':{}}\n",
    "n6={'rac':6,'g':n9,'d':{}}\n",
    "n5={'rac':5,'g':n7,'d':n8}\n",
    "n4={'rac':4,'g':{},'d':{}}\n",
    "n3={'rac':3,'g':{},'d':n6}\n",
    "n2={'rac':2,'g':n4,'d':n5}\n",
    "arbre1={'rac':1,'g':n2,'d':n3}\n",
    "\n",
    "print(arbre1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Exercice 1: </h3>\n",
    "\n",
    "<h4> Ecrire les fonctions est_vide et est_feuille. Faire des tests avec arbre1</h4>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_vide(arbre):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_feuille(noeud):\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#tests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Exercice 2</h3>\n",
    "\n",
    "l'algorithme récursif du calcul de la hauteur de l'arbre est :\n",
    "\n",
    "<ul>\n",
    "    <li> Si l'arbre et vide</li>\n",
    "    <ul><li> renvoyer -1</li></ul>\n",
    "    <li> Sinon</li>\n",
    "    <ul>\n",
    "        <li> h1 = 1 + hauteur(fils_gauche)</li>\n",
    "        <li> h2 = 1 + hauteur(fils_droit)</li>\n",
    "        <li> renvoyer max(h1,h2)</li></ul>\n",
    "    </ul>\n",
    "\n",
    "<h4>Écrire la fonction hauteur</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hauteur(arbre): # à compléter\n",
    "    pass\n",
    "\n",
    "hauteur(arbre1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ci-dessous le programme qui permet d'afficher l'arbre :\n",
    "\n",
    "<i> il nécessite d'avoir réussi la fonction hauteur </i>"
   ]
  },
  {
   "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['rac'])\n",
    "            branches[0].append((pos_courante, pos_parent))\n",
    "            pos_gauche = pos_courante - 2**profondeur\n",
    "            parkour(arbre['g'], noeuds, branches, labels, positions, profondeur, pos_gauche, pos_courante, null_node)\n",
    "            pos_droit = pos_courante + 2**profondeur\n",
    "            parkour(arbre['d'], 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['rac'])}\n",
    "    \n",
    "    if null_node:\n",
    "        branches.append([])\n",
    "        noeuds.append([])\n",
    "        \n",
    "    profondeur -= 1\n",
    "    parkour(arbre['g'], noeuds, branches, labels, positions, profondeur, pos_courante - 2**profondeur, pos_courante, null_node)\n",
    "    parkour(arbre['d'], 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(arbre1,(4,3),False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>Exercice 3: </h3>\n",
    "\n",
    "Écrire la fonction qui renvoie la taille de l'arbre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Nombre de noeud interne d'un arbre </h3>\n",
    "\n",
    "Pour déterminer le nombre de noeud interne d'un arbre, il faut compter le nombre de noeud qui ont au moins un enfant\n",
    "\n",
    "Pour ce faire:\n",
    "* Si le noeud est vide ou si c'est une feuille on renvoie 0\n",
    "* Sinon on renvoie 1 + la somme des nombres de noeuds de ses enfants gauche et droit \n",
    "\n",
    "Cette procédure est récursive...\n",
    "\n",
    "<h3> Exercice 4 </h3>\n",
    "\n",
    "Écrire une fonction qui renvoie le nombre de noeud interne d'un arbre passé en paramètre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nb_noeuds_interne(arbre):\n",
    "    pass\n",
    "    \n",
    "print(nb_noeuds_interne(arbre1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Exercice 5 </h3>\n",
    "\n",
    "<p>Implémenter l'arbre2 de la fiche de cours, l'afficher puis tester les fonctions précédentes sur cet arbre </p>"
   ]
  },
  {
   "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}