\n",
"
⌛ Avant de commencer\n",
"\n",
"#### Vous devez travailler sur https://notebook.basthon.fr/\n",
" \n",
"Vous devez charger ce module : `module_tree_2021.py` dans le document (icone ouvrir fichier puis choisir Installer le module)\n",
"\n",
"\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "0UE_Kb95NwfI"
},
"source": [
"Voici un labyrinthe que nous avons déjà étudié :\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "VfdVzH1_wiFp"
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "4_e9QUrWe-6T"
},
"source": [
"🖐 Nous vous redonnons la représentation de ce labyrinthe avec un arbre.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "9BTmsVf00a9_"
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "lW4y9c6-_95s"
},
"source": [
"
I. Implémentation d'arbres avec 2 classes\n",
"\n",
"Les arbres seront ici implémentés avec une classe `Node` et une classe `Arbre`. \n",
"Vous n'avez pas besoin de connaître cette implémentation. \n",
"\n",
"👉 Voici les fonctions de l'interface dont vous aurez besoin :\n",
"\n",
"Notre arbre sera modélisé avec un dictionnaire.\n",
"\n",
"```\n",
"#################### Un arbre ###################\n",
"\n",
"arbre = Arbre(etiquette) :\n",
" Crée un objet arbre, dont la racine porte l'étiquette passée en paramètre\n",
" Attributs :\n",
" arbre.noeuds : dictionnaire dont les clés sont les etiquettes \n",
" des sommets et les valeurs les objets noeuds associés\n",
" arbre.etiquette_racine : etiquette de la racine de l'arbre\n",
"\n",
"############### Primitives d'accès ###############\n",
"\n",
"arbre.empty():\n",
" return True si Arbre est un arbre vide, False sinon\n",
"\n",
"arbre.filsD(etiquette) :\n",
" renvoie True si le noeud dont l'etiquette est donnée en paramètre a un fils droit, False sinon.\n",
" \n",
"arbre.filsG(etiquette) :\n",
" renvoie True si le noeud dont l'etiquette est donnée en paramètre a un fils gauche, False sinon.\n",
"\n",
"arbre.racine() :\n",
" renvoie l'objet noeud de la racine\n",
" Les objets Noeuds disposent de 3 attributs :\n",
" fg et fd : objets Noeud fils gauche et droit\n",
" val : etiquette du noeud fils\n",
" \n",
"arbre.est_feuille(etiquette) :\n",
" Renvoie True si le noeud etiquette est une feuille\n",
"\n",
"############### Primitives d'ajouts ###############\n",
"\n",
"arbre.addG(etiquette_parent, etiquette_fils) -> None :\n",
" :param etiquette_parent: est une etiquette d'un noeud de l'arbre\n",
" :param etiquette_fils: est l'etiquette du fils gauche à ajouter \n",
"\n",
" addG ajoute un fils gauche au noeud parent\n",
" \n",
"\n",
"\n",
"arbre.addD(etiquette_parent, etiquette_fils) -> None :\n",
" :param etiquette_parent: est une etiquette d'un noeud de l'arbre\n",
" :param etiquette_fils: est l'etiquette du fils droit à ajouter \n",
"\n",
" addD ajoute un fils droit au noeud parent\n",
"\n",
"\n",
"############### Primitives d'extraction de sous arbres ###############\n",
"\n",
"arbre.sad(etiquette = None):\n",
" si le paramètre cle est absent, la méthode renvoie le SAD de la racine\n",
" si une etiquette et mentionnée, la méthode renvoie le SAD du noeud portant cette etiquette\n",
"\n",
"arbre.sag(etiquette = None):\n",
" si le paramètre cle est absent, la méthode renvoie le SAG de la racine\n",
" si une etiquette et mentionnée, la méthode renvoie le SAG du noeud portant cette etiquette\n",
"\n",
"############### Primitive de représentation ###############\n",
"\n",
"print(arbre) : permet d'afficher l'arbre en mode texte\n",
"\n",
"arbre.show(etiquette = None, verts = None):\n",
" Dessin de l'arbre.\n",
" Si etiquette est None, la fonction dessinne l'arbre complet\n",
" Sinon elle dessine le sous arbre dont la racine est etiquette\n",
" Le paramètre verts peut être ajouté : c'est une liste d'étiquettes. \n",
" Tous les noeuds de cette liste seront représentés en vert.\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "YsLfbBBc_Gg5"
},
"outputs": [],
"source": [
"from module_tree_2021 import Node, Arbre \n",
"from module_tree_2021 import addNodes, make_it"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ce n'est pas nécessaire ici, mais vous pouvez exécuter la cellule suivante."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "ll7IWFW7AmEg",
"outputId": "5f00433b-d53f-41a0-eae4-78b77b1cbe05"
},
"outputs": [],
"source": [
"help(Arbre)\n",
"help(Node)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "PWWLYvZCpKK6"
},
"source": [
"
II. Création de l'arbre\n",
"\n",
"Le module **module_tree_2021** contient une fonction `addNodes`. \n",
"\n",
"Cette fonction doit créer l'arbre du labyrinthe que nous étudions, mais elle est incomplète... (😢 quelques nœuds ont été oubliés ... )\n",
"\n",
"Ci dessous, on crée un Arbre dont la racine porte l'étiquette \"04\" et on ajoute les nœuds avec addNodes\n",
"\n",
"Regardez le dessin de l'arbre obtenu et comparez avec le votre (fait à la main) pour déterminer les nœuds manquants.\n",
"\n",
"Ensuite, ajoutez les instructions qui permettent d'ajouter ces nœuds (voir les primitives d'ajout disponibles) .\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"id": "f8yf0rEGTk2s",
"outputId": "8636a34c-467b-4558-abe7-eb6f0501ee39"
},
"outputs": [],
"source": [
"arbre = Arbre(\"04\")\n",
"addNodes(arbre)\n",
"### après avoir vu l'arbre construit ci-dessous, ajoutez les instructions ci-dessous ###\n",
"\n",
"# puis refaire le dessin\n",
"arbre.show()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 322
},
"id": "mO1VPAC7G1tw",
"outputId": "8d643a49-f304-4a62-ce12-108c4502d1e6"
},
"outputs": [],
"source": [
"# test de votre arbre\n",
"from module_tree_2021 import test_arbre\n",
"test_arbre(arbre)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "qY9YC8aHKwCw"
},
"source": [
"En principe `arbre` contient maintenant (et jusqu'à la fin du TP) l'arbre correct. Si toutefois une fausse manipulation le détruisait, vous pouvez le reconstruire avec la cellule ci-dessous :"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "6z4WU5dOK9M9",
"outputId": "79f9b080-d014-4b45-9719-02a135547c43"
},
"outputs": [],
"source": [
"from module_tree_2021 import make_it\n",
"arbre = make_it()\n",
"test_arbre(arbre)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"id": "GpvHvxNPYSC5",
"outputId": "4b1da0ab-d3e7-414b-f774-7a4e887495a9"
},
"outputs": [],
"source": [
"arbre.show()"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "TWYXhD5k4RJe"
},
"source": [
"
III. Les parcours en profondeur\n",
"\n",
"Que fait le code ci-dessous ?\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "rYQiia7jvE1Y",
"outputId": "9d33ab84-fec4-4032-8613-8f2364dc0fa1"
},
"outputs": [],
"source": [
"def mystere(arbre):\n",
"\n",
" print(arbre.etiquette_racine, end = \" -> \")\n",
"\n",
" if arbre.racine().fg is not None : \n",
" mystere(arbre.sag())\n",
"\n",
" if arbre.racine().fd is not None : \n",
" mystere(arbre.sad())\n",
"\n",
"mystere(arbre)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "omn6is7tCBeg"
},
"source": [
"
Réponse :
\n",
" \n",
" \n",
"\n",
"Ce code affiche les nœuds avec un **parcours préfixe** de l'arbre. \n",
" \n",
"
\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "OcNa4bQULe15"
},
"source": [
"
💻 **A vous de jouer 1**\n",
"\n",
"Complétez le code pour qu'il renvoie la liste des sommets visités (au lieu d'afficher), en utilisant la même structure que dans la fonction `mystere`ci-dessus.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "tiefOoD6A6jm"
},
"outputs": [],
"source": [
"def parcours_prefixe(arbre):\n",
" visites = [arbre.etiquette_racine]\n",
" if arbre.racine().fg is not None : \n",
" ...\n",
" ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"id": "d0NsjosOA-pA",
"outputId": "5cdd600a-2ac7-42e2-ed04-3399b8d4cb49"
},
"outputs": [],
"source": [
"prefixe = parcours_prefixe(arbre)\n",
"print(prefixe)\n",
"# l'appel de show avec une liste permet d'afficher en vert les noeuds présents dans la liste\n",
"# vérifions que nous avons tout visité :\n",
"arbre.show(verts = prefixe)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "7TBFwHJ-MtEz"
},
"source": [
"
💻 **A vous de jouer 2**\n",
"\n",
"Faire de même pour un parcours suffixe en utilisant la même structure que dans la fonction `mystere`ci-dessus.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "dPNQDLKSC59Y"
},
"outputs": [],
"source": [
"def parcours_suffixe(arbre):\n",
" ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 220
},
"id": "dOaJM9_5DEl4",
"outputId": "19275777-1397-4901-f4f1-c8887e73ab7d"
},
"outputs": [],
"source": [
"suffixe = parcours_suffixe( arbre)\n",
"print(suffixe)\n",
"# vérifiez si tous les noeuds ont été visités :\n",
"arbre.show(verts = suffixe)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "xmlLTzLuM_oH"
},
"source": [
"
💻 **A vous de jouer 3**\n",
"\n",
"Faire de même pour un parcours infixe en utilisant la même structure que dans la fonction `mystere`ci-dessus.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "t_rOmkjscP6Q"
},
"outputs": [],
"source": [
"def parcours_infixe(arbre):\n",
" ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"id": "D17OZ21ScP6c",
"outputId": "f0d9af5c-546d-48f5-a16b-03e9ebb40954"
},
"outputs": [],
"source": [
"infixe = parcours_infixe( arbre)\n",
"print(infixe)\n",
"# vérifiez si tous les noeuds ont été visités :\n",
"arbre.show(verts = infixe)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "InRsnetpY_hs"
},
"source": [
"
💡 Une autre écriture plus concise\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "oTqnXJR6YJVt"
},
"outputs": [],
"source": [
"def prefixe(arbre) :\n",
" if arbre.empty():\n",
" return []\n",
" else :\n",
" return [arbre.etiquette_racine] + prefixe(arbre.sag()) + prefixe(arbre.sad()) "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "PiwpQortYWvg",
"outputId": "5aa644c2-4350-4f83-c783-ccb36a7e3d15"
},
"outputs": [],
"source": [
"print(prefixe(arbre))"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "sWjGkmWCZIkE"
},
"source": [
"
💻 **A vous de jouer 4**\n",
"\n",
"Faire de même pour un parcours suffixe et un parcours infixe\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "P68KvaFEZPEj",
"outputId": "603db5e2-fb28-4e82-c26d-a3fb2df3234d"
},
"outputs": [],
"source": [
"def suffixe(arbre) :\n",
" ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(suffixe(arbre))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "18Lm1qQBZYhi",
"outputId": "eddad2a8-586b-4b2e-afdc-9da8c3d748a6"
},
"outputs": [],
"source": [
"def infixe(arbre) :\n",
" ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(infixe(arbre))"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "NXjXpYg0NasL"
},
"source": [
" 💻 **A vous de jouer 5**\n",
"\n",
"Ecrire une fonction récursive `getFeuilles(arbre)` qui renvoie la liste des culs de sac du labyrinthe (la sortie est comptée comme un cul de sac) "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"id": "6vfOBgngpwzP",
"outputId": "d988f17e-57b0-4165-a78f-a8d79265d4d6"
},
"outputs": [],
"source": [
"def getFeuilles(arbre):\n",
" ...\n",
"\n",
"feuilles = getFeuilles( arbre)\n",
"print(feuilles)\n",
"# vérifiez si les feuilles sont vertes :\n",
"arbre.show(verts = feuilles)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "UrHwTvOZVX5-"
},
"source": [
"\n",
"\n",
"\n",
"---\n",
"\n",
"**Auteurs** Jean-Louis Thirot - Lycée Bertrand d'Argentré - Vitré (35) et Mireille Coilhac (Melun)\n",
"\n",
"Publié sous licence CC BY-NC-SA\n",
"\n",
"\n",
"---\n",
"![\"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. "
]
}
],
"metadata": {
"colab": {
"collapsed_sections": [],
"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
}