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

Implémentation d'un arbre binaire avec une classe

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

On va utiliser la POO pour créer une classe AB (pour Arbre Binaire), en utilisant le caractère récursif d'un arbre: une racine, et éventuellement un sous-arbre gauche et un sous-arbre droit.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class AB:\n", " def __init__(self, racine=None):\n", " self.racine = racine\n", " if self.racine is not None:\n", " self.gauche = AB() \n", " self.droit = AB()\n", " \n", " def est_vide(self):\n", " pass\n", " \n", " def afficher_fils_gauche(self):\n", " pass\n", " \n", " def afficher_fils_droit(self):\n", " pass\n", " \n", " def est_feuille(self):\n", " pass\n", " \n", " def hauteur(self):\n", " pass\n", " \n", " def taille(self):\n", " pass\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

On peut alors créer l'arbre ci-dessous avec le code :

" ] }, { "attachments": { "Capture.JPG": { "image/jpeg": "/9j/4AAQSkZJRgABAQEAYABgAAD/4QLaRXhpZgAATU0AKgAAAAgABAE7AAIAAAAFAAABSodpAAQAAAABAAABUJydAAEAAAAKAAACyOocAAcAAAEMAAAAPgAAAAAc6gAAAAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAREVMTAAAAAWQAwACAAAAFAAAAp6QBAACAAAAFAAAArKSkQACAAAAAzg0AACSkgACAAAAAzg0AADqHAAHAAABDAAAAZIAAAAAHOoAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADIwMjQ6MTI6MjEgMTY6Mzg6MjQAMjAyNDoxMjoyMSAxNjozODoyNAAAAEQARQBMAEwAAAD/4QQXaHR0cDovL25zLmFkb2JlLmNvbS94YXAvMS4wLwA8P3hwYWNrZXQgYmVnaW49J++7vycgaWQ9J1c1TTBNcENlaGlIenJlU3pOVGN6a2M5ZCc/Pg0KPHg6eG1wbWV0YSB4bWxuczp4PSJhZG9iZTpuczptZXRhLyI+PHJkZjpSREYgeG1sbnM6cmRmPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5LzAyLzIyLXJkZi1zeW50YXgtbnMjIj48cmRmOkRlc2NyaXB0aW9uIHJkZjphYm91dD0idXVpZDpmYWY1YmRkNS1iYTNkLTExZGEtYWQzMS1kMzNkNzUxODJmMWIiIHhtbG5zOmRjPSJodHRwOi8vcHVybC5vcmcvZGMvZWxlbWVudHMvMS4xLyIvPjxyZGY6RGVzY3JpcHRpb24gcmRmOmFib3V0PSJ1dWlkOmZhZjViZGQ1LWJhM2QtMTFkYS1hZDMxLWQzM2Q3NTE4MmYxYiIgeG1sbnM6eG1wPSJodHRwOi8vbnMuYWRvYmUuY29tL3hhcC8xLjAvIj48eG1wOkNyZWF0ZURhdGU+MjAyNC0xMi0yMVQxNjozODoyNC44Mzk8L3htcDpDcmVhdGVEYXRlPjwvcmRmOkRlc2NyaXB0aW9uPjxyZGY6RGVzY3JpcHRpb24gcmRmOmFib3V0PSJ1dWlkOmZhZjViZGQ1LWJhM2QtMTFkYS1hZDMxLWQzM2Q3NTE4MmYxYiIgeG1sbnM6ZGM9Imh0dHA6Ly9wdXJsLm9yZy9kYy9lbGVtZW50cy8xLjEvIj48ZGM6Y3JlYXRvcj48cmRmOlNlcSB4bWxuczpyZGY9Imh0dHA6Ly93d3cudzMub3JnLzE5OTkvMDIvMjItcmRmLXN5bnRheC1ucyMiPjxyZGY6bGk+REVMTDwvcmRmOmxpPjwvcmRmOlNlcT4NCgkJCTwvZGM6Y3JlYXRvcj48L3JkZjpEZXNjcmlwdGlvbj48L3JkZjpSREY+PC94OnhtcG1ldGE+DQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgPD94cGFja2V0IGVuZD0ndyc/Pv/bAEMABwUFBgUEBwYFBggHBwgKEQsKCQkKFQ8QDBEYFRoZGBUYFxseJyEbHSUdFxgiLiIlKCkrLCsaIC8zLyoyJyorKv/bAEMBBwgICgkKFAsLFCocGBwqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKv/AABEIAQoBPAMBIgACEQEDEQH/xAAfAAABBQEBAQEBAQAAAAAAAAAAAQIDBAUGBwgJCgv/xAC1EAACAQMDAgQDBQUEBAAAAX0BAgMABBEFEiExQQYTUWEHInEUMoGRoQgjQrHBFVLR8CQzYnKCCQoWFxgZGiUmJygpKjQ1Njc4OTpDREVGR0hJSlNUVVZXWFlaY2RlZmdoaWpzdHV2d3h5eoOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4eLj5OXm5+jp6vHy8/T19vf4+fr/xAAfAQADAQEBAQEBAQEBAAAAAAAAAQIDBAUGBwgJCgv/xAC1EQACAQIEBAMEBwUEBAABAncAAQIDEQQFITEGEkFRB2FxEyIygQgUQpGhscEJIzNS8BVictEKFiQ04SXxFxgZGiYnKCkqNTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqCg4SFhoeIiYqSk5SVlpeYmZqio6Slpqeoqaqys7S1tre4ubrCw8TFxsfIycrS09TV1tfY2dri4+Tl5ufo6ery8/T19vf4+fr/2gAMAwEAAhEDEQA/APpGiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKK5bxb4y/sK4t9J0ezOqa9ej/AEayQ4Cj/npIf4VH647ckAHU0VwEfw+1XXh9o8deJL25d+TYafIYLaP/AGeOW+pwakPwc8IxjdZW95ZTdp7e9kDg+vJI/SgDu6K86uIvF/w/U3cV5N4p0GPmaG4H+mW6d2V/48d8/kOTXcaPrFjr2kwalpU6z2twu5HH6gjsQeCKALtFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQBXv72HTtNub65O2G2iaaQ+iqCT+grjfhlpklzp9x4u1Zd2q66xmLHnyYM/u419sAH8vStT4j+Z/wrXXvKzu+xvnHpjn9M1o+F/L/AOEQ0fyMeX9gg2Y9PLXFAEuv63ZeG/D97rOqSeXaWULSyHuQOw9STgAdyRXkPws1fxZd/GPVYvFeoXR+2aMuorpjzMYrLzJVKIqE4BVCATjOSan+LXjXQbf4iaD4Z8W3xsdCtUXVrzMLyfa3DEQw4QE7Qyljng4ArE0D4peELv8AaMvtWg1UtZalpcGn2sv2aUeZOZEwmCuR9SAPegD6Crz3SYR4M+KkujW/yaT4hie7tYh92G5T/WKo7Arz+Qr0KuE8d/8AI8eBvL/139oS4x12bBu/TFAHd0UUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFAFe/sotS025sbkZhuYmhkHqrAg/oa434ZanJBps/hLVW26roLmBlPHmwZ/dyL7YIH5etb3i7xdpPgrQZNV1uYpGp2RRIN0k8h6Ii92P/1zgV53p3gfxf4s1F/Hesak/h7XmQLpenRKClrACSEn4y7Nnn0z0/hAB668MUjZkjRj6soNcbY+B7i1+MWo+LmktTY3WmJZxwKD5iurKdxGMY49c1Vj+Imo6EPs/jvw7e2UicG+sYzPbSe+Ryv05NSH4yeDXGLO9ubyY9IbeylLn25UD9aAO7rz7Sph4z+K0usW58zSfDsT2ltKOVluX/1jKe4C8fke9R3M/i74gxtZ2tnceFdClGJrm5wLydO6on8GfU/meRWf4O1S5+Geq2/gPxaUFhO7DQ9ZCBEusnPky9llGev8X16gHqtFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABXP8AjLxnpfgjQzqOrOzu7eXbWsQ3S3Up6Ii9yf0qPxt4303wPo63V8JLm7uG8qysIBumu5T0RB9SMnt9cA894N8Eale64PGvxEKXGvyL/odipzDpUZ/gQdC/q35epAI/CPgzVNc16Pxv8R0VtVAzpmkg7odKQ9PZpTxlu34DHpNFFABRgDoKKKACsrxJ4b0vxboNxo+uWwuLS4GCOjI3ZlPZh2NatFAHmfhnxJqngjXrfwV4+uTcRznZomuycLeL2hlPaUcDn731wT6ZWT4m8M6X4v0C40fXbYT2sw+jRsOjqezDsa4rwx4m1Twb4gg8E+P7gz+d8ui644wt8o6RSHtMOB/tfXBYA9LooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooJwMngVwl54+vtY1GbTfh9pa6tJC2yfUZ32WkLem7q59h+GaAO7orhB4f+I1yPMuPG1lYuefJtdLSRB7bn5pkl18RvDY867gsPFNmvLi1UwXIHqF+6foMk0Ad9XL+OfHVh4J02JpYpL7U7xvK0/TLfma7k7ADsORlu3ucA4erfGTQ4NAhm0SObU9bvJDb2miqu24aburr/Co7t09M1P4G8BXVhqUvivxrcJqXiu8XDSDmKwjP/LGEdgM4J78+pJAI/BPgW+XWG8Y+PpI77xPcLiKJeYdMiP/ACyiHTPPLd+eeSW9BoooAKKKKACiiigAooooAKyPE/hjS/GGgT6PrluJraYZBHDxMOjoezDsf6Vr0UAea+FvE+q+EfEEPgj4gXHnSS/Lo2tvwmoIOkbntMOBz9764LelVj+KfC2l+MfD8+ka3B5tvLyrKcPE46Oh7MOx/DoSK4vw14u1DwdrCeDfiRdqX2k6Vrsp2xX8S/wyMeFlUdcnn64LAHplFcE/j/VPEFxJB8PtDOpRRsVbU7xjDagj+73f8MU77H8Um/eHVPDaP18kQSlPpnrQB3dFcA3jnxB4Zdf+E90BYrMnB1TS2MsKe7IfmUe5/Ku4s7221Gziu7GeO4t5l3RyxtuVh6g0AT0UUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQBwnj27u9a1jT/BGkztbvqSGfUJ0PzQ2qnBA92Py/p3rsNK0qy0TS4NP0u3S3tYF2pGg6e59SepPeuP8ND7V8YvGdzLy9pDZ20Wf4UaMsR+JGa7ugDzHUdE+MV3d3VzY+LNDsIxK5trJbLerJk7Q7spIOMZxmtv4W+NLvxx4Pa91W0S01Oyu5LG9jj+55seMlevBDDuec1D4+sPiReTZ+H+r6TY2/wBmw6XkRMplyeVbawHG0DPeqPwOuNMbwBJZafaXNne2N9NBqkV3KJZftYI8xmcABs8c4HTHagA8e6GnhzWrf4iaJap9tsf3eoxqgzc2zEBj/vDjn069K9CtbmK8tIbq2cSQzIskbjoykZB/I1Bq9rHfaJfWk4Bjnt5I3B9CpB/nXN/Ci5ku/hZockpJZYWjGfRJGUfoooA7CiiigAooooAKKKKACiiigAooooAK818UWMfxJ8cp4XnjV9E0NkutRbHMk5B2RA9uCcke47CvSq4P4TDz9B1XVJOZ9R1a5mkY9fvYA+gx+tAHYvGNL0d00uzQi2gPkWseEDED5UHYZ6V5foPxD8fSfFLR/Dni/wAPaZo9rqkE06RxymadQiEjLq+3qB2r1uvLPE//ACcv4J/7Bt5/6A1AHqMkaSxtHKqujgqysMhgeoIrzq3gPw38c21nbEr4Z1+Uxxwk/LZXZ6BfRX9P8OfR64n4vW4l+GeoTqds1m8VxC/dHWReR+BI/GgDtqKitJvtNlBORjzY1fHpkZqWgAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKAOBeQeG/jYZLj5LTxNZqiSHgfaIeAv4p09zXfVieLPDFr4s0N7C5doJVYS21zH9+CVfuuP89K5TS/iUPD+qp4Y+I7x6fqyx7or0cwXkecCTI+6TjnOBwenSgClL8Q/iPaK1pP8LLie+BKpNb6ght39Gzg7R7E/jWz8KfCGqeFtB1C58SPE2ta3qEuo3qwnKRO+PkB746/U45xmuxtdRsr2ETWV5b3ERGQ8Uqsp/EGsXXvH3hzw7GftupRS3HRLS2YSzOewCjpn3wKAE+IGur4f8Eahcg5uJozb2qD7zyuNqgDv1z9AateD9Gbw94N0vS5MeZbW6rLj++eW/8AHia5rRdG1fxf4it/E3i21NjaWZ3aXpLnLI3/AD1l/wBr0Hb2xz39ABRRRQAUUUUAFFFFABRRRQAUUUUAFcD8OnGka34l8Kz/ACy2l+95bg/x28uCpHrg9fc131ch408MX93eWniPwu6Ra9pwIRXOEu4j1hf9cH1PbqADrZXMcLuqFyqkhV6t7V4Bq3izxPqPxW0DxYnw28TJb6VazwPAbY7nMikAg4xxmvVvDfxC0jXZPsV239laxGds2m3p2SK3+znG4fTn2FdXQBn6FqU2saFaahc6fcabLcJua0uhiSI56MPWuT+K85vNBsvDFqc3mvXkduqjqsasHd/oMDP1rW8T/EDQPCqiK8u1uL+RhHBp9sQ88rnooUdMn1rP8JeH9UvNcl8X+LkWPU5o/Ks7JTlbGH0z/fPc/X1wADtERY41RBhVAAHoKdRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFAFfUdQttK0y51DUJVhtbWJpppG6IijJP5CvO/hvof/CTpqnjnxTYxyz+IyBa2tzGHFvYr/qkwePm++fXg0fEOR/Gni7TPh1ZO32WQLqGvSIcbLVGGyLPYyMB74APSvSo40hiSOJFSNFCqqjAUDoAKAOPufhJ4GupjJJoESsTnEU0sY/JWArX0XwZ4c8POH0bR7W2lHAlCbpB/wNsn9a26KACiiigAooooAKKKKACiiigAooooAKKKKACiiuI+LGv3WkeCzp+jHOs67MumaeoPIkl4L+wVdxz2OKAOZ8N+H9M+Kfi/xF4t160W80pX/snSFZiAYoifMlUgg/M5OD1wCK6L/hUHhoDYkuqJD/zwW/fZj0xXT+GdAtfC3hfTtD08YgsYFiU4xvIHLH3JyT7mtSgDz7xB8IfDt14Nu9N8P2EOn6iAJrO+BLSxTodyNvOWAyMH2JrY+HfixvGHg+G8u4/I1O2drTUrYjBhuY+HUjtnqPYiuprzDWf+LefFq215P3eg+K2Sy1EfwwXgH7mX2DDKk/UmgD0+iiigAooooAKKKKACiiigAooooAKKKKACiiigAopHdY42eRgiKMszHAA9TXG3vxW8L2121rZXFxq1wv3o9Nt2nx/wIfKfwNAHZ1l+JvEFl4V8M3+uao+22soTIwzyx6BR7kkAe5rmV+Lnh+J1Gq2mr6SjHAkvrB0X8xmsPVb61+KvxG07QtMnjvPDWg7NS1OaNt0dxOf9RBnvjlmH4HkUAbnwr8P3thol14h8Qp/xP/Ecv269yOYVI/dQj0CJgY7EkV3VFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRVPVNX0/RLJrvVr2GzgXjfM4UE+g9T7CuRPxd8PSsf7MtdX1OMHHm2dg7L+uKAO6rzPSv+K3+Nt/q7fvNJ8Ixtp9n3V72QZmce6rhPyNN8S/GzQNO8K6lPYtcxaxHCRa2V1avG7yt8qdRjAJBPPQGuo+HfhceEPAun6XI3mXezzrybOTLO/zSNnvycA+gFAHTUUUUAFY/izw3Z+L/Ct/oWpD9xeRFN4GTG3VXHurAH8K2KKAOI+FviS81jw9PpOvnHiDQJvsGoqTy5X7kvuHUZz3Oa7evMfHit4F8c6b8QbUEafPt03X1UceSxxFOfdGwCeuCBW7f/FXwlZXRtodQbUbgdY9Phaf/wAeUbf1oA7GiuHi+LvhfzVj1Br7TN5wrXtm6KfxANdjZX9pqVol1p9zDdW8gyssLh1P4igCeiiigAooooAKKKKACiiigApskiRRtJKyoiAszMcAAdSTTq4v4rXk8HgdrGzfZPq1zFp6MO3mNz+agj8aAMe2trr4sX0l5fSzW3g+CUpbWsbFG1FlOC7nrsyOB/IjNdhf33hzwB4Zku7s2ukaXbAZ2JtGewCgZZj7ZJrT06wt9K0y2sLNNlvbRLFGvooGBXjPxj8Q2Nt8WPB+na5bz32nWccmoDT7eLzHvLgkpCgToTuHfsTQB2Phr4veFvGOtxaJaQ6hFcXaO0C3tkyJcKqljg8jGATzima54Gl8P3cviT4dotjqC/Pc6dGMQXyjqpQcBsdCP0zmjw78UotV8WQeHfEvhzUPDeqXCNLYpfBWS4AByFcfxYzx9RntXoNAGT4Y8RWnirw/b6rYZVJRh4m+9E44ZD7g/wCPetauC8NJ/YXxa8RaJD8trqFvHq0UfZGJ2SEfVufwFd7QAUUUUAFFFFABRRRQAUUUUAFFFFABWJ4t8TW/hPw/JqE6NPKWEVtbp96eVvuoP89Aa264LUk/t7416dYzfNa6HYNfbD0M7ttXP0GCPcUAGheBGvrhfEPxBZNS1ZxvS2k5t7FeuxU6EjuTnn8zsJ8Q/BS6immReJ9HFzny1hW7j69NvXGe2K3dQsYNU0y6sLsFre6heGUA4JVlKnntwa878afDT4faX8MdYV/D+m2MFrZSSJdJComjcKdpEh+YnOOpOenOaAO+1bRdN12ya01ixgvIG/glQHHuD1B9xzXBqbz4Varbwy3Mt54PvJRErTNufTJD0G7vGf0+v3tn4RzahcfCPw3Lq5drprJctJ95kydhP1TbXQ6/o8Gv+H77SroAx3cLRkkfdJHDfUHB/CgDQBz0orkvhhqk2rfDvTZLwk3NurWsuTk5jYqM++AK62gApskiRRtJKyoiAszMcAAdSTTq4r4rXk8XgsadZv5c+sXcOnIw7eYefzUEfjQBjx2tz8XLqWe/eW28GwyFIbZCVbUip5dz1CZHA/qM100OueBvCRbSYtX0HR3gwHtTdwwspxkblJBzg55re06wt9L022sLJBHb20SxRqOygYFYWqfDnwbrGozajq/hzTrq7mO6WeaEFmwMZJ+gFAF+x8QeG/Evm2em6tper4TdLBb3Mc+FzjLKCePrXJ6z4NuvCdxJ4h+HimCRPnvNHBPkXaDrtX+F8dMfh6HnvgLo2ny3firxbpdlDZ2Opag1tp0USbVW2iOAQP8AaJ591r2SgDM8O6/Z+JtAttW05iYbhc7T95GHBU+4PFadcD4TQaD8TvE3h+H5bS6SPVbeMdELfLJj6tj8q76gAooooAKKKKACiiigArhPi1mDwzpupkExaXrFreS4HRQxX+bCu7qnrGl22t6Nd6ZfLut7qJonx1AI6j3HUfSgC2rB1DKQykZBB6ivIfiVBbaH8bvAXi3ViseloZ7Ge4k4SGRkfyix6AEuTnttJrovA3iCfSrgeCvFLiLVbFdlnM/C30A+4ynuwAwR149Qcdjquk6frmmy6frFnDe2cwxJDOgZW/A9/egDyv4kalY+IPij8O9L0K6hvdRtdTN7N9ncP5NuoUvuI6Bgp+uK9grn/DfgTwx4QeV/Dei2thJMMSSRqS7D03HJx7ZxR4v8X2fhPTBJIDcX852WdjHzJcSHgAAc4z1P9cCgDDsW/tD48ancRcppuix2kpHZ3k8wD8s13lct4C8OXWhaNNc6wwk1jVJjd3zjs7dEHso4+uccV1NABRRRQAUUUUAFFFFABRRRQAUUUUAFcHAwsPjxdJNwNT0ZGhY/xNG+Cv1wCa7yuQ8f6DfX9rZa34fUHWtFlM9sn/PZCMPF/wACH+HegDryQoJJwBySe1ePXUknxu8WNYWzMvgLRbgfaplOBq1wvPlqe8a9z3/EEd5pWs6R8RPCF3DDI6R3UD2t5bhts1uWUqyn0PJwcVxtv+zv4VtIFhtdW8RQRL91I9R2qO/QLQB6qiJFGscaqiKAqqowAB0AFNuJ47W2luJ2CRRIXdj/AAqBkmqHhzQbfwx4ftdHsp7meC2DBJLqXzJG3MWOW78n8sVyHjXWJfE9+fA3hmXfcXHGq3cfK2cGfmUn+83TH4d+AC18IYZF+HlvcyqUN7cT3IU9g0hx+gz+NdxUFjZQabp9vY2aeXb20SxRqOyqMD+VT0AFcJ8WD9m0bRNUf/U6ZrlrdTHsEBIJ/NhXd1Q13R7bxBoN5pV6P3F3EY2I6r6MPcHB/CgC+DkZHSuG+MfiN/DXwr1e4tiftl3GLK1VfvGSX5ePcAs3/AaPAniOe3c+D/E7CHXNOXZEznC3sI+7IhPU4HI68Z9cbXibwbpviy60ebVpLgppF4t7DDG4Eckq/dLgg5A54BHU0AHgbw4nhLwJo+hoAGs7VUlI6NIfmc/ixY/jW/RXP+L/ABdZ+E9K86YG4vZz5dnZR8yXEh4AAHOMkZP9cCgDD01vt3x21i4h5TT9His5SOgd38wD8hXeVy3gHw5daFos1xrDCTWNUmN3fOOzt0Qeyjj65xXU0AFFFFABRRRQAUUUUAFFFFAGP4k8K6T4rsBa6xb79h3QzIdskLeqt1B/T1rmk0D4g6EPK0PxJY6var9yPWoWEij0Mict9TXe0UAcGbX4o6iPLn1Hw9pEZ4MtpDJNIPcB/lrT8OeArDQr9tVvLi41fWZBh9QvW3OB6IOiD6c9s4rqaKACiiigAooooAKKKKACiiigAooooAKKKKACiiigDkdf+H9pqWqHWdFvbjQtZxzeWfSX/ronR/0z3zVIR/FKxHlpP4b1RB0mmSWKQ+5C/L+Vd3RQBwL+HPHviAeV4h8SWmlWjf6yDRIm3uPTzH5X8M11Ph7w1pXhbTRZaLarBGTudicvK395mPJP+RWrRQAUUUUAFFFFAHn3xjg09/Bys9p5+tzTpa6MY2KSi6kOE2sOcDliOmF+lFrpPxM0G1ihtdc0nxBGiAE6jC8Umcc4ZOv1Y0mmf8Vr8WLvVm+fSPCu+xsv7st64/fyf8AXCD3LYr0KgDg2X4o6iPKaTw/o6HrNGJJpB9Afl/OtHw54BstF1FtX1K7n1rWnGGv7w5KD0jXog/XtnFdXRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABXL/ELxJceG/Ccj6Wok1e/kWx0yL+/cScKfovLH2U11Fee6V/xWvxXu9Yb59I8Lb7Cx/uy3jAefIP8AcXEY9y1AHU+EfDcHhLwnYaLbMZBbR4klPWaQnLufdmJP41s0UUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRXFfELVL6RtO8K6FMYdR1yRkadetvbqMyP9ccD8cc0AN1Px9cXerTaN4G0z+27+E7bi4Z9lrbH0Z/4j7D88jFRjQPiNejzLvxnY6a558my0xZUHtufBrpNL0vSfBvhr7PaIlpYWUTSSSN6AZZ2Pc8ZJrzaH4reN9V0ebxVoPgeK48LRF3Qy3my7niQkNIqdB0PGD04zQBsavD8VdG0e7/s290vxBI0LrGzQfZ5kYjhgB8pwecd+laPwpvdFXwZa6LpDSx3Wmpsvbe6TZOsxOXd1P8AeYsc++Paum8P67ZeJvD1lrWlOXtL2ESxkjBAPUH0IOQfcVy3xB0Oaz2+M/DqCPWNKXfMq8C7tx9+N/XjkH2+mADuqKp6RqdvrWj2mpWZzBdwrKmeoBGcH3HSrlABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAVwloPtfx51CSbk2WixxxA9t8m4kfyru64HXpB4b+Luj61N8ljq9q2lzSH7qSht8ZP16fgaAOl8Y6XPrfgbXNKs+Li90+e3iycfM8bKP1NeVeCviz4Z0X4P2uk6nOYNd0y1NhJo7RN58k65RUCY53HH0zzjFe3E4FeLan8XdE1MSf8Ix4N1S48ZSoYraK40oJLBIRgM8nZV+vbt1ABpfs3SzN8G7WGfI+z3lxEoPYb9xH5sa9VkRZY2jkUMjAqynoQe1cv8ADXwk3gj4e6XoczrJcwxl7l1OQ0rsWbB7gE4B9AK0/FWvQ+GfC99q1wwH2eImNT/G54VfxJAoA534Psw+H0dqWLJaXdxBGT3USEj+ddzXMfDnRZtA8AaZZ3YIuWjM84bqHkJcg+4zj8K6egAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKy/Efh+y8UaDcaVqSkwzDh1+9Gw6Mp9Qa1KKAPO9O8Y3/guSPRfiIsgiU7LXXI0LQ3C9hJjlX/yfU9xZaxpuowibT9QtbqMjIeGZXH6GrE8EVzA8NzEk0TjDRyKGVh6EHrXKXfwp8EXsxkm8P26sTnELvEPyRgKANDXPHPhzw7Cz6lqtuJB0gicSSsfQIuT/AErmrHTdW+IGuWus+JLOTTdBsX82w0ub/WTv2llHbHZf6ZJ6bRvA/hnQJRLpOi2sEq/dlKb3H0ZskfnW9QAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAf//Z" } }, "cell_type": "markdown", "metadata": {}, "source": [ "![Capture.JPG](attachment:Capture.JPG)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = AB(4)\n", "a.gauche = AB(3)\n", "a.droit = AB(1)\n", "a.droit.gauche = AB(2)\n", "a.droit.droit = AB(7)\n", "a.gauche.gauche = AB(6)\n", "a.droit.droit.gauche = AB(9)\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 1** : Complèter la classe AB par les méthodes puis les tester : \n", "
\n", "
  • est_vide qui renvoie un boleen si l'arbre est vide
    • \n", "
  • afficher_ils_gauche (et afficher_fils droit) qui renvoie la racine de l'arbre gauche (et droit )
    • \n", "
  • est_feuille qui renvoie vrai si le noeud est une feuille ou faux sinon
    • \n", "
    " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# jeux de tests\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice2** : Completer la classe avec la methode hauteur (on choisira -1 pour la hauteur un arbre vide)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# tests\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# tests de l'arbre vide\n", "b=AB()\n", "b.est_vide()\n", "b.hauteur()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

    Réprésentation d'un arbre

    " ] }, { "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=(4,3), 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 not(arbre.est_vide()):\n", " noeuds[0].append(pos_courante)\n", " positions[pos_courante] = (pos_courante, profondeur)\n", " profondeur -= 1\n", " labels[pos_courante] = str(arbre.racine)\n", " branches[0].append((pos_courante, pos_parent))\n", " pos_gauche = pos_courante - 2**profondeur\n", " parkour(arbre.gauche,noeuds, branches, labels, positions, profondeur, pos_gauche, pos_courante, null_node)\n", " pos_droit = pos_courante + 2**profondeur\n", " parkour(arbre.droit, 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 ==None:\n", " return\n", " \n", " branches = [[]]\n", " profondeur = arbre.hauteur()\n", " pos_courante = 2**profondeur\n", " noeuds = [[pos_courante]]\n", " positions = {pos_courante: (pos_courante, profondeur)} \n", " labels = {pos_courante: str(arbre.racine)}\n", " \n", " if null_node:\n", " branches.append([])\n", " noeuds.append([])\n", " \n", " profondeur -= 1\n", " parkour(arbre.gauche, noeuds, branches, labels, positions, profondeur, pos_courante - 2**profondeur, pos_courante, null_node)\n", " parkour(arbre.droit, 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(a,(4,3),False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 3** : Completer avec la methode taille" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# tests" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 4** : Completer avec la methode nombre de feuilles :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#tests" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 5** : Ecrire une fonction booléenne récursive qui recherche si une valeur v est présente dans un arbre A" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def recherche(arbre,v):\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 6**: a) Ecrire une fonction ajout_gauche(arbre,x) qui ajoute un noeud x à gauche de l'arbre à l'endroit où si c'est possible
    \n", "b) idem pour une fonction ajout_droit(arbre,x)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def ajout_gauche(arbre,x):\n", " if arbre.gauche.est_vide():\n", " arbre.gauche=AB(x)\n", " else:\n", " ajout_gauche(arbre.gauche,x)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = AB(4)\n", "a.gauche = AB(3)\n", "a.droit = AB(1)\n", "a.droit.gauche = AB(2)\n", "a.droit.droit = AB(7)\n", "a.gauche.gauche = AB(6)\n", "a.droit.droit.gauche = AB(9)\n", "repr_graph(a,(4,3),False)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ajout_gauche(a.droit.gauche,5)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "repr_graph(a,(4,3),False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 7** : Reconstruire l'arbre a en utilisant uniquement ces deux fonctions." ] }, { "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 }