CH6 TP parcours en profondeur d'un arbre.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CH6 Parcours en profondeur d'un arbre binaire : infixe, préfixe et postfixe\n",
    "\n",
    "![expression](https://media.geeksforgeeks.org/wp-content/uploads/expression-tree.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Noeud:\n",
    "    def __init__(self, valeur, gauche, droit):\n",
    "        self.r = valeur\n",
    "        self.g = gauche\n",
    "        self.d = droit\n",
    "\n",
    "class ArbreBinaire:\n",
    "    def __init__(self, c):  # si le noeud = None cela signifie un arbre vide\n",
    "        self.n = c\n",
    "    def creeVide(): # c'est une methode de classe\n",
    "        return ArbreBinaire(None)\n",
    "    def creeNGD(valeur, gauche, droit):\n",
    "        return ArbreBinaire(Noeud(valeur, gauche, droit))   # c'est une méthode de classe\n",
    "    def estVide(self):\n",
    "        return self.n is None\n",
    "    def racine(self):\n",
    "        assert not(self.n is None), 'Arbre vide'\n",
    "        return self.n.r\n",
    "    def filsGauche(self):\n",
    "        assert not(self.n is None), 'Arbre vide'\n",
    "        return self.n.g\n",
    "    def filsDroit(self):\n",
    "        assert not(self.n is None), 'Arbre vide'\n",
    "        return self.n.d \n",
    "    # affichage\n",
    "    def affiche_r(self,p):# affichage parcours postfixe , p est la profondeur\n",
    "        if not self.estVide(): # recursivité\n",
    "            self.filsDroit().affiche_r(p+1)\n",
    "            print('                          '*p,self.racine())\n",
    "            self.filsGauche().affiche_r(p+1)    \n",
    "    def affiche(self):\n",
    "        self.affiche_r(0)\n",
    "vide = ArbreBinaire(None)   \n",
    "def creeFeuille(x): #fonction pratique pour créer une feuille qui est un arbre binaire sans fils\n",
    "    return ArbreBinaire.creeNGD(x, vide, vide)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 1\n",
    "\n",
    "Créer l'arbre binaire correspondant à cette expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Exercice 2 : Par 3 fonctions, donner l'écriture infixe, préfixe et postfixe de cette expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}