Algo Arbre Binaire Algo

Identification

Infoforall

14 - Algorithmes des arbres binaires


L'Arbre est une structure récursive.

Nous allons nous limiter à l'Arbre Binaire de façon à réaliser un nombre de fonctions récursives permettant de l'explorer.

On rappelle qu'un Arbre Binaire est soit :

  1. Un Arbre Vide
  2. L'ensemble d'un Noeud menant à deux sous-arbres binaires (qui peuvent donc être vides !)

Logiciel nécessaire pour l'activité : -

Prérequis :

  • Données : Arbre et Arbre Binaire
  • Algos : Parcours d'Arbres

Evaluation ✎ :

Documents de cours : -

1 - Implémentation d'un Arbre Binaire

L'activité d'aujourd'hui ne traite pas de la façon dont on réalise l'implémentation de notre type abstrait Arbre Binaire.

1er partie de la définition de l'arbre binaire

Un arbre binaire est :

  • soit un arbre vide
  • soit l'ensemble d'un noeud et de ses deux sous-arbres binaires qu'on peut positionner clairement à gauche et à droite.
    • Le noeud possède un fils gauche qu'on peut identifier comme tel (potentiellement un arbre vide donc)
    • Le noeud possède fils droit qu'on peut identifier comme tel (potentiellement un arbre vide donc)

    La notion de distinction entre fils gauche et fils droit est fondamentale ici par rapport à l'arbre (arborescence) de la partie précédente.

    Implémentation sous forme d'objet d'un Arbre Binaire en Python

    Nous allons créer des Noeuds en utilisant la programmation orientée objet.

    Chaque Noeud possèdera 2 attributs :

    1. Sa clé, ce qui permet de l'identifier
    2. Son contenu, ce qu'on lui demande de stocker

    Un Arbre Binaire sera lui également un objet qui comporte trois attributs :

    1. La référence de son Noeud-racine
    2. La référence de son sous-arbre gauche
    3. La référence de son sous-arbre droite

    Nous allons représenter nos Arbres Binaires comme une structure qui est vide ou composée de noeuds reliés entre eux.

    Ces noeuds possèdent un identifiant et comportent trois informations :

    • Un attribut e (pour etiquette) qui contient l'informatique basique qu'on veut associer à ce noeud
    • Un attribut g (pour gauche) qui contient la référence du noeud-fils gauche ou qui fait référence à VIDE.
    • Un attribut d (pour droite) qui contient la référence du noeud-fils droit ou qui fait référence à VIDE.
    • 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
      # Déclaration des classes (hors interface) class Cle: '''Juste pour faciliter la documentation''' class Data: '''Juste pour faciliter la documentation''' class Arbre: '''Juste pour faciliter la documentation : un AB ou None''' class Noeud: '''Implémentation d'un noeud sous forme d'objet''' def __init__(self, cle, data=None): '''Méthode-initialisateur ou méthode-constructeur :: param cle(voir type_cle) :: la clé associée au noeud :: param data(divers) :: les données associée au noeud :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Initialisation des attributs utilisés self.cle = cle # La clé associée au noeud self.data = data # Les données à stockées class AB: '''Implémentation d'un Arbre Binaire sous forme d'objet''' def __init__(self, racine, type_cle=str, gauche=None, droite=None): '''Méthode-initialisateur ou méthode-constructeur :: param racine(Noeud) :: la racine de l'Arbre :: param type_cle(type) :: le type attendu des clés des noeuds de cet arbre :: param gauche(AB|None) :: le sous-arbre binaire gauche (qui peut être Vide/None) :: param droite(AB|None) :: le sous-arbre binaire droite (qui peut être Vide/None) :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur racine, gauche et droite assert isinstance(racine, Noeud) assert type(racine.cle) == type_cle assert gauche is None or isinstance(gauche, AB) assert droite is None or isinstance(droite, AB) # Initialisation des attributs utilisés self.racine = racine # Référence du noeud-racine self.gauche = gauche # Référence du sous-arbre gauche self.droite = droite # Référence du sous-arbre droite def ajout_a_gauche(self, sous_arbre:Arbre): '''Méthode d'ajout d'un sous-arbre gauche :: param self(AB) :: l'arbre non vide à modifier :: param sous_arbre(AB|None) :: le sous-arbre binaire à ajouter à gauche :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur les sous-arbres à rajouter assert sous_arbre is None or isinstance(sous_arbre, AB) # Modification du sous-arbre gauche self.gauche = sous_arbre def ajout_a_droite(self, sous_arbre:Arbre): '''Méthode d'ajout d'un sous-arbre droite :: param self(AB) :: l'arbre non vide à modifier :: param sous_arbre(AB|None) :: le sous-arbre binaire à ajouter à droite :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur les sous-arbres à rajouter assert sous_arbre is None or isinstance(sous_arbre, AB) # Modification du sous-arbre gauche self.droite = sous_arbre

    01° Quelles sont les préconditions de la méthode constructeur AB qui sont clairement imposées via des assertions plutôt qu'avec juste de la documentation ?

    ...CORRECTION...

    02° Répondre aux deux questions ci-dessous :

    1. Ligne 32 : comment se nomment les variables qu'on trouve sur cette ligne : des paramètres ou des attributs ?
    2. Ligne 50 : comment se nomme le racine de self.racine ?

    ...CORRECTION...

    03° Répondre aux deux questions ci-dessous :

    1. Ligne 54 : comment se nomme ajout_a_gauche(self, sous_arbre:Arbre) ?
    2. Ligne 54 : d'après le prototype ajout_a_gauche(self, sous_arbre:Arbre), quel doit-être le type du paramètre sous_arbre ?
    3. Qu'est-ce qui impose que cette précondition sur sous_arbre soit respectée ?
    4. Ligne 66 : que fait cette ligne qui est finalement la seule vraie ligne de code de cette fonction ?

    ...CORRECTION...

    04° A quoi sert la méthode ajout_a_droite ?

    ...CORRECTION...

    2 - Fonctions d'interface

    Maintenant que nous savons comment nous avons implémenté notre Arbre Binaire, nous allons pouvoir étudier et réaliser les fonctions d'interface.

    2e partie de la définition du type abstrait de données ARBRE BINAIRE : son interface

    Description de l'interface du type abstrait Arbre présenté

    Je le décris ici sous forme d'un type immutable, mais on pourait faire la même chose en non-mutable.

    Les fonctions liées aux Noeuds :

    1. nvND(cle:Cle, data:Data) -> Noeud : on crée un nouveau noeud et son élément attaché. Ce n'est pas une fonction d'interface de l'arbre mais on a besoin au moins de pouvoir créer un Noeud.
    2. cle(noeud:Noeud) -> Cle : renvoie la clé ou l'étiquette du noeud.
    3. data(noeud:Noeud) -> Data : renvoie les données associées au noeud.

    Les fonctions liées à l'Arbre Binaire lui-même :

    1. nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
    2. nvAB(r:Noeud, g:Arbre, d:Arbre) -> Arbre : on crée un nouvel ARBRE BINAIRE dont la racine est r et dont les sous-arbres sont g et d fournis.
    3. estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
    4. racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre.
    5. gauche(arbre:Arbre) -> Arbre : renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine.
    6. droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre.

    05° Créer un fichier nommé arbre_binaire_ifa.py dans un répertoire qu'on nommera algoAB.

    📁 algoAB

    📄 arbre_binaire_ifa.py

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
    '''Module implémentant un Arbre Binaire (AB) Classes non accessibles implémentant l'Arbre Binaire (hors interface) --------------------------------------------------------------------- CLASSE Noeud Attributs (accessibles en lecture directement) + cle : la valeur de la clé / étiquette associé à ce noeud + data : les données qu'on veut y stocker CLASSE AB Attributs (accessibles en lecture directement) + racine : la référence du noeud-racine de l'arbre + gauche : la référence du sous-arbre gauche + droite : la référence du sous-arbre droit Méthodes : + ajout_a_gauche(sous_arbre:Arbre) + ajout_a_droite(sous_arbre:Arbre) CLASSES créée uniquement pour faciliter la documentation des pre et post conditions + Cle : pour dire qu'on veut ou renvoie une clé + Data : pour dire qu'on veut ou renvoie les données associées + Arbre : pour dire qu'on veut ou renvoie un AB ou None (Arbre Vide) Fonctions d'Interface permettant de gérer l'Arbre Binaire (interface) --------------------------------------------------------- + nvAV() -> Arbre + nvAB(racine:Noeud, g:Arbre=None, d:Arbre=None) -> AB + estArbreVide(arbre:Arbre) -> bool + racine(arbre:Arbre) -> Noeud + gauche(arbre:Arbre) -> Arbre + droite(arbre:Arbre) -> Arbre + nvND(cle:Cle, data:Data) -> Noeud + data(noeud:Noeud) -> Data + cle(noeud:Noeud) -> Cle ''' # Importation # Déclaration des fausses classes (pour la documentation) class Cle: pass class Data: pass class Arbre: pass # AB ou Arbre vide # Déclaration des classes (hors interface) class Noeud: '''Implémentation d'un noeud sous forme d'objet''' def __init__(self, cle, data=None): '''Méthode-initialisateur ou méthode-constructeur :: param cle(voir type_cle) :: la clé associée au noeud :: param data(divers) :: les données associée au noeud :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Initialisation des attributs utilisés self.cle = cle # La clé associée au noeud self.data = data # Les données à stockées class AB: '''Implémentation d'un Arbre Binaire sous forme d'objet''' def __init__(self, racine, type_cle=str, gauche=None, droite=None): '''Méthode-initialisateur ou méthode-constructeur :: param racine(Noeud) :: la racine de l'Arbre :: param type_cle(type) :: le type attendu des clés des noeuds de cet arbre :: param gauche(AB|None) :: le sous-arbre binaire gauche (qui peut être Vide/None) :: param droite(AB|None) :: le sous-arbre binaire droite (qui peut être Vide/None) :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur racine, gauche et droite assert isinstance(racine, Noeud) assert type(racine.cle) == type_cle assert gauche is None or isinstance(gauche, AB) assert droite is None or isinstance(droite, AB) # Initialisation des attributs utilisés self.racine = racine # Référence du noeud-racine self.gauche = gauche # Référence du sous-arbre gauche self.droite = droite # Référence du sous-arbre droite def ajout_a_gauche(self, sous_arbre:Arbre): '''Méthode d'ajout d'un sous-arbre gauche :: param self(AB) :: l'arbre non vide à modifier :: param sous_arbre(AB|None) :: le sous-arbre binaire à ajouter à gauche :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur les sous-arbres à rajouter assert sous_arbre is None or isinstance(sous_arbre, AB) # Modification du sous-arbre gauche self.gauche = sous_arbre def ajout_a_droite(self, sous_arbre:Arbre): '''Méthode d'ajout d'un sous-arbre droite :: param self(AB) :: l'arbre non vide à modifier :: param sous_arbre(AB|None) :: le sous-arbre binaire à ajouter à droite :: return(None) :: - :: effet de bord .. modifie self par effet de bord ''' # Précondition sur les sous-arbres à rajouter assert sous_arbre is None or isinstance(sous_arbre, AB) # Modification du sous-arbre gauche self.droite = sous_arbre # Fonctions d'interface accessibles de l'extérieur def nvND(cle:Cle, data:Data=None) -> Noeud: return Noeud(cle, data) def cle(noeud:Noeud) -> Cle: '''Renvoie la clé du noeud''' if isinstance(noeud, Noeud): return noeud.cle elif DEBUG: print("L'argument envoyé n'est pas un Noeud") def data(noeud:Noeud) -> Data: '''Renvoie les données associées au noeud''' if isinstance(noeud, Noeud): return noeud.data elif DEBUG: print("L'argument envoyé n'est pas un Noeud") def nvAV() -> Arbre: return None def nvAB(racine:Noeud, g:Arbre=nvAV(), d:Arbre=nvAV()) -> AB: return AB(racine, gauche=g, droite=d) def estArbreVide(arbre:Arbre) -> bool: '''True si l'arbre est vide''' return arbre == None def racine(arbre:Arbre) -> Noeud: '''Renvoie la référence du noeud Racine de l'Arbre Binaire (arbre peut être vide)''' if isinstance(arbre, AB): return arbre.racine elif DEBUG and not estArbreVide(arbre): print("L'argument envoyé n'est pas un Arbre") def gauche(arbre:Arbre) -> Arbre: '''Renvoie le sous-arbre gauche de l'arbre (arbre peut être vide)''' if isinstance(arbre, AB): return arbre.gauche elif DEBUG and not estArbreVide(arbre): print("L'argument envoyé n'est pas un Arbre") def droite(arbre:Arbre) -> Arbre: '''Renvoie le sous-arbre droit de l'arbre (arbre peut être vide)''' if isinstance(arbre, AB): return arbre.droite elif DEBUG and not estArbreVide(arbre): print("L'argument envoyé n'est pas un Arbre") # Programme de test du module DEBUG = False if __name__ == "__main__": DEBUG = True # Pour voir les messages d'erreur ad = nvAB(nvND("D")) af = nvAB(nvND("F"), g=ad) ae = nvAB(nvND("E"), d=af) ah = nvAB(nvND("H")) ag = nvAB(nvND("G"), d=ah) ab = nvAB(nvND("B")) ac = nvAB(nvND("C"), g=ag, d=ab) aa = nvAB(nvND("A"), g=ac, d=ae)

    06° Lire chaque fonction d'interface et expliquer briévement ce qu'elle réalise en analysant son code.

    ...CORRECTION...

    07° Pourquoi ne pas avoir mis d'assertion mais de simples tests dans les fonctions d'interface, fonctions qui sont censées pouvoir être appelées par un utilisateur extérieur ?

    ...CORRECTION...

    08° Dessiner l'Arbre Binaire créé par le programme de tests (les lignes 172 à 179).

    ...CORRECTION...

    Arbre question 18

    09° Modifier le programme pour qu'il réalise plutôt la réalisation de cet arbre ci :

    Arbre question 10

    ...CORRECTION...

    3 - Utilisation du module

    Nous allons maintenant réaliser différentes fonctions nous permettant de déterminer les caractéristiques de l'arbre, en utilisant uniquement les fonctions d'interface et sans nous soucier de l'implémentation.

    Le mieux est donc de placer notre implémentation et les fonctions d'interface dans un module et de créer nos propres fonctions en utilisant uniquement les fonctions d'interface.

    10° Créer un fichier nommé mes_algos.py dans le répertoire algoAB.

    📁 algoAB

    📄 arbre_binaire_ifa.py

    📄 mes_algos.py

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
    # Importation from arbre_binaire_ifa import nvAB from arbre_binaire_ifa import estArbreVide from arbre_binaire_ifa import racine from arbre_binaire_ifa import gauche from arbre_binaire_ifa import droite from arbre_binaire_ifa import nvND from arbre_binaire_ifa import cle from arbre_binaire_ifa import data # Déclaration des fausses classes (pour la documentation) class Cle: pass class Data: pass class Arbre: pass # Déclarations des fonctions def parcours_prefixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en préfixe RGD''' pass def hauteur(arbre:Arbre, profondeur_vide=-1) -> int: '''Renvoie la hauteur de l'Arbre Binaire''' pass def nb_feuilles(arbre:Arbre) -> int: '''Renvoie le nombre de feuilles de l'Arbre Binaire''' pass def taille(arbre:Arbre) -> int: '''Renvoie la taille de l'Arbre Binaire''' pass def estPresent(arbre:Arbre, c:Cle) -> bool: '''Fonction booléenne : True si c est la clé d'un des noeuds''' pass # Programme principal if __name__ == "__main__": ad = nvAB(nvND("D")) af = nvAB(nvND("F"), g=ad) ae = nvAB(nvND("E"), d=af) ah = nvAB(nvND("H")) ag = nvAB(nvND("G"), d=ah) ab = nvAB(nvND("B")) ac = nvAB(nvND("C"), g=ag, d=ab) aa = nvAB(nvND("A"), g=ac, d=ae)

    11° Pourquoi peut-on directement utiliser la fonction nvAB alors que la fonction n'est pas dans ce fichier Python ? Que trouve-t-on directement derrière le import ?

    ...CORRECTION...

    12° Comment lancer l'appel à nvAB si les premières lignes proposent simplement une importation du type import arbre_binaire_ifa ?

    ...CORRECTION...

    4 - Parcours et autres algorithmes

    Parcours Préfixe (sous forme d'une simple exploration qui ne renvoie rien)

    La fonction visiter sera un simple affichage dans la console : on affichera la clé du noeud.

    Préfixe car on commence par visiter le noeud actuel avant de faire autre chose.

    On affiche donc le noeud racine lui-même avant ses descendants.

    Description des ENTREES / SORTIE

    ENTREE : Un Arbre Binaire (possiblement Vide)

    SORTIE : Rien (sur l'exemple, il s'agit d'une fonction d'affichage sur l'interface utilisateur)

    Description de l'algorithme récursif parcours_prefixe(arbre: Arbre)

      SI NON estArbreVide(arbre)

        visiter(racine(arbre))

        parcours_prefixe(gauche(arbre))

        parcours_prefixe(droite(arbre))

      Fin SI

      Renvoyer VIDE

    13° Réaliser la fonction correspondante. Lancer les appels sur l'Arbre Binaire du programme.

    Arbre question 18

    Vous devriez obtenir la réponse suivante :

    A C G H B E F D

    ...CORRECTION...

    1 2 3 4 5 6
    def parcours_prefixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en préfixe RGD''' if not estArbreVide(arbre): print(cle(racine(arbre))) parcours_prefixe(gauche(arbre)) parcours_prefixe(droite(arbre))

    14° Réaliser la fonction parcours_postfixe. Ne regardez votre ancienne fonction, tentez de retrouver seul la solution : le jour de l'examen, vous partirez de rien.

    Arbre question 18

    Vous devriez obtenir la réponse suivante :

    H G B C D F E A

    ...CORRECTION...

    1 2 3 4 5 6
    def parcours_postfixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en postfixe GDR''' if not estArbreVide(arbre): parcours_postfixe(gauche(arbre)) parcours_postfixe(droite(arbre)) print(cle(racine(arbre)))

    15° Réaliser la fonction parcours_infixe. Ne regardez votre ancienne fonction, tentez de retrouver seul la solution : le jour de l'examen, vous partirez de rien.

    Arbre question 18

    Vous devriez obtenir la réponse suivante :

    G H C B A E D F

    ...CORRECTION...

    1 2 3 4 5 6
    def parcours_infixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en infixe GRD''' if not estArbreVide(arbre): parcours_infixe(gauche(arbre)) print(cle(racine(arbre))) parcours_infixe(droite(arbre))

    16° Réaliser la fonction hauteur. Elle doit renvoyer la hauteur de l'arbre.

    Comme vous le voyez, cette fonction possède un paramètre qui permet de choisir la profondeur d'un arbre vide. Par défaut, elle est reglé à -1 ici. La racine aura donc une profondeur de 0.

    • Condition d'arrêt : l'arbre est vide.
    • Cas de base : on renvoie la hauteur définie pour l'arbre vide
    • Cas récursif :
    • On renvoie la somme de 1 et du maximum entre hauteur du sous-arbre gauche et hauteur du sous-arbre droite.

    On rappellera que pour trouver le maximum entre deux valeurs, on peut comparer mais on peut également utiliser la fonction max qui renvoie le plus grand des arguments qu'on lui fournit : si a est plus grand que b, max(a, b) renvoie alors a.

    ...CORRECTION...

    1 2 3 4 5 6
    def hauteur(arbre:Arbre, profondeur_vide=-1) -> int: '''Renvoie la hauteur de l'Arbre Binaire''' if estArbreVide(arbre): return profondeur_vide else: return 1 + max(hauteur(gauche(arbre)), hauteur(droite(arbre)))

    17° Réaliser la fonction nb_feuilles. Elle doit renvoyer le nombre de feuilles de l'arbre.

    • Condition d'arrêt 1 : l'arbre est vide.
    • Cas de base : on renvoie 0
    • Condition d'arrêt 2 : les deux sous-arbres de l'arbre sont vides (c'est une feuille !).
    • Cas de base : on renvoie 1
    • Cas récursif :
    • On renvoie la somme de l'appel récursif sur le sous-arbre-gauche et de l'appel récursif sur le sous-arbre droite.

    ...CORRECTION...

    1 2 3 4 5 6 7 8
    def nb_feuilles(arbre:Arbre) -> int: '''Renvoie le nombre de feuilles de l'Arbre Binaire''' if estArbreVide(arbre): return 0 elif estArbreVide(gauche(arbre)) and estArbreVide(droite(arbre)): return 1 else: return nb_feuilles(gauche(arbre)) + nb_feuilles(droite(arbre))

    18° Variante : votre fonction doit en plus afficher la clé de la feuille lorsqu'il en trouve une.

    Sur l'Arbre Binaire de l'exemple, cela donne :

    H B D 3

    19° Réaliser la fonction taille. Elle doit renvoyer le nombre de noeuds de l'Arbre Binaire.

    • Condition d'arrêt 1 : l'arbre est vide.
    • Cas de base : on renvoie 0
    • Condition d'arrêt 2 : les deux sous-arbres de l'arbre sont vides (c'est une feuille !).
    • Cas de base : on renvoie 1
    • Cas récursif :
    • On renvoie la somme de 1 et de l'appel récursif sur le sous-arbre-gauche et de l'appel récursif sur le sous-arbre droite.

    ...CORRECTION...

    1 2 3 4 5 6 7 8
    def taille(arbre:Arbre) -> int: '''Renvoie la taille de l'Arbre Binaire''' if estArbreVide(arbre): return 0 elif estArbreVide(gauche(arbre)) and estArbreVide(droite(arbre)): return 1 else: return 1 + taille(gauche(arbre)) + taille(droite(arbre))

    20° Réaliser la fonction booléenne estPresent. Elle doit renvoyer True si la clé fournie apparaît bien dans l'Arbre Binaire.

    • Condition d'arrêt 1 : l'arbre est vide.
    • Cas de base : on renvoie False
    • Condition d'arrêt 2 : la clé de la racine a la bonne valeur.
    • Cas de base : on renvoie True
    • Cas récursif :
    • On renvoie le résultat de la recherche sur l'arbre gauche OU de la recherche dans l'arbre droite.

    Question subsidiaire : que renvoie un OU s'il l'un des termes est VRAI ?

    ...CORRECTION...

    1 2 3 4 5 6 7 8
    def estPresent(arbre:Arbre, c:Cle) -> bool: '''Fonction booléenne : True si c est la clé d'un des noeuds''' if estArbreVide(arbre): return False elif cle(arbre) == c: return True else: return estPresent(gauche(arbre), c) or estPresent(droite(arbre), c)

    Vous devriez être bien content maintenant et vous rendre compte du parcours personnel réalisé depuis le début de première.

    21° Encoder votre maison sous forme d'un Arbre Binaire.

    Vous pourrez facilement trouver le nombre de pièces (la taille), le nombre de pièces n'ayant qu'une entrée (les feuilles)...

    N'oubliez pas que vous pouvez rajouter des données aux Noeuds à l'aide du paramètre data ! Vous pourriez ainsi peupler vos pièces de meubles ou de gens en plaçant par exemple un dictionnaire dans ces données.

    Il est temps de plonger dans le grand bain :

    22° Effacer les fonctions que vous venez de réaliser aujourd'hui et tenter de le recoder en definissant vous même la récursivité.

    Pas facile, mais indispensable pour l'évaluation. C'est l'objectif de la prochaine activité.

    5 - FAQ

    Rien pour le moment

    La prochaine activité vous permettra d'analyser plus finement les versions récursives de vos fonctions.

    Activité publiée le 10 12 2020
    Dernière modification : 10 12 2020
    Auteur : ows. h.