"""Module implémentant un Arbre Binaire (AB) sous forme d'objets"""# Déclaration de la classe ABclassAB:"""Implémentation d'un Arbre Binaire sous forme objet simple"""def__init__(self,valeur=None,gauche=None,droite=None):assertvaleuror(valeur==Noneandgauche==Noneanddroite==None)self.v=valeurself.g=gaucheself.d=droiteifvaleurandgaucheisNone:self.g=AB()ifvaleuranddroiteisNone:self.d=AB()defrelier_a_gauche(self:'AB NON VIDE',sous_arbre:'AB'):"""Méthode qui définit sous_arbre comme le sous-arbre gauche de l'arbre actif"""self.g=sous_arbredefrelier_a_droite(self:'AB NON VIDE',sous_arbre:'AB'):"""Méthode qui définit sous_arbre comme le sous-arbre droite de l'arbre actif"""self.d=sous_arbredefdefinir_donnees_racine(self:'AB',element:'Element NON VIDE'):"""Méthode qui place l'élément NON VIDE en tant que racine de l'arbre"""self.v=elementdefvider(self:'AB'):"""Méthode qui transforme l'arbre en AB VIDE"""self.v=Noneself.g=Noneself.d=None# Fonctions d'interface (accessibles de l'extérieur)defcontenu(noeud:'Noeud')->'Element':"""Renvoie le contenu associé au noeud fourni"""returnnoeud.vdefnv_ABV()->'AB VIDE':"""Renvoie un nouvel Arbre Binaire Vide"""returnAB()defnv_AB(valeur:'Element',g:'AB|None'=None,d:'AB|None'=None)->'AB NON VIDE':"""Renvoie un nouvel Arbre Binaire dont la racine porte valeur et qui mène aux sous-arbres g et d"""returnAB(valeur,g,d)defest_ABV(arbre:'AB')->bool:"""Prédicat qui renvoie True si l'arbre est vide"""returnarbre.visNoneandarbre.gisNoneandarbre.disNonedefracine(arbre:'AB NON VIDE')->'Noeud':"""Renvoie le noeud-racine de l'Arbre Binaire NON VIDE"""returnarbre# dans cette implémentation, un AB non vide est un pointeur vers sa racinedefgauche(arbre:'AB NON VIDE')->'AB':"""Renvoie le sous-arbre gauche de l'Arbre Binaire NON VIDE"""returnarbre.gdefdroite(arbre:'AB NON VIDE')->'AB':"""Renvoie le sous-arbre droite de l'Arbre Binaire NON VIDE"""returnarbre.d# Programme de test du moduleif__name__=="__main__":ad=nv_AB("D")af=nv_AB("F",g=ad)ae=nv_AB("E",d=af)ah=nv_AB("H")ag=nv_AB("G",d=ah)ab=nv_AB("B")ac=nv_AB("C",g=ag,d=ab)aa=nv_AB("A",g=ac,d=ae)
Dans toute l'activité, nous travaillerons avec cet Arbre Binaire :
Nous ne reviendrons plus sur les trois façons de parcourir un Arbre Binaire en profondeur. Voici simplement les trois exemples pour lequel l'exploration se résume à un simple affichage de la clé ou de l'étiquette des noeuds :
1
2
3
4
5
6
defparcours_prefixe(arbre:'AB')->None:"""Exploration (et affichage) en profondeur en préfixe RGD"""ifnotest_ABV(arbre):print(contenu(racine(arbre)))parcours_prefixe(gauche(arbre))parcours_prefixe(droite(arbre))
1
2
3
4
5
6
defparcours_suffixe(arbre:'AB')->None:"""Exploration (et affichage) en profondeur en suffixe GDR"""ifnotest_ABV(arbre):parcours_suffixe(gauche(arbre))parcours_suffixe(droite(arbre))print(contenu(racine(arbre)))
1
2
3
4
5
6
defparcours_infixe(arbre:'AB')->None:"""Exploration (et affichage) en profondeur en infixe GRD"""ifnotest_ABV(arbre):parcours_infixe(gauche(arbre))print(contenu(racine(arbre)))parcours_infixe(droite(arbre))
Le jour de l'examen, comment parvenir à retrouver la fonction récursive hauteur() ?
Définir le cas de base : quand peut-on répondre définitivement ?
Si l'Arbre Binaire est un arbre VIDE, on peut répondre : la hauteur est -1 si on prend comme convention une profondeur de 0 pour la racine.
Définir le cas récursif
On peut pas répondre immédiatement il faut relancer des appels récursifs. Lesquels ?
Le cas récursif doit répondre 1 + la plus grande de deux hauteurs à gauche et à droite.
Version Python
1
2
3
4
5
6
7
defhauteur(arbre:'AB',profondeur_vide=-1)->int:"""Renvoie la hauteur de l'Arbre Binaire"""ifest_ABV(arbre):returnprofondeur_videelse:return1+max(hauteur(gauche(arbre)),hauteur(droite(arbre)))
Exemple détaillé avec la recherche de la hauteur de l'Arbre ag, l'Arbre dont la racine est G.
On notera AV l'arbre vide.
hauteur(ag) va renvoyer 1 + max(hauteur(gauche(ag)), hauteur(droite(ag))), ce qui devient
hauteur(ag) va renvoyer 1 + max(hauteur(AV), hauteur(ah)).
Comment rédiger cela sans y passer 15 minutes ? Deux façons de faire :
Réponse textuelle : noter les appels récursifs au fur et à mesure, en laissant un peu de place. De cette façon, on pourra noter les résultats en dessous au fur et à mesure des réponses définitives lors d'un dépilement. C'est une méthode TOP -> DOWN.
Réponse textuelle : idem mais en commençant par fournir les réponses des fonctions les plus basses. C'est une méthode BOTTOM -> UP. Nous allons voir que moins long mais que cela s'écarte de la façon dont la machine traite les appels.
Réponse graphique : encore plus court, mais difficile à comprendre tant qu'on a pas compris la notion d'appels récursifs.
Commençons avec un exemple de rédaction de réponse complète si on vous demande des justifications :
On écrit les appels dans l'ordre d'apparition :
Ensuite, on rajoute les réponses lorsqu'elles arrivent lors du dépilement.
Il suffit alors de compléter votre rédaction au fur et à mesure des réponses qu'on parvient à obtenir.
Au final, on aura alors quelque chose qui ressemble à cela :
01° Réaliser l'empilement des appels récursifs de la fonction hauteur() sur l'arbre de racine A, qu'on notera aa. Fournir ensuite la réponse finale que va renvoyer la fonction.
1
2
3
4
5
6
7
defhauteur(arbre:'AB',profondeur_vide=-1)->int:"""Renvoie la hauteur de l'Arbre Binaire"""ifest_ABV(arbre):returnprofondeur_videelse:return1+max(hauteur(gauche(arbre)),hauteur(droite(arbre)))
...CORRECTION...
L'empilement provoque des appels à ces fonctions :
Il reste à dépiler en allant chercher les réponses au fur et à mesure :
02° Réaliser l'empilement des appels récursifs de la fonction hauteur() sur l'arbre aa. Fournir ensuite la réponse finale que va renvoyer la fonction.
Pour cette question :
Appliquer d'abord la méthode BOTTOM -> UP
Appliquer ensuite la méthode consistant à noter clairement les réponses sur l'arbre lui-même
...CORRECTION...
03° En utilisant uniquement les fonctions d'interface (et sans regarder le code déjà fourni), retrouver le code de la fonction récursive hauteur().
Pour cela, demandez-vous quel est (ou sont) le (ou les) cas de base qui permettent de répondre immédiatement. Réflechir ensuite à la réponse qu'on peut fournir dans le cas récursif.
3 - Recherche recursive de la taille de l'Arbre Binaire
04° Fournir le code d'une fonction taille() où le seul cas de base est l'arbre vide : on doit renvoyer 0 puisqu'il ne contient pas de noeud.
...CORRECTION...
1
2
3
4
5
6
7
deftaille(arbre:'AB')->int:"""Renvoie la taille de l'Arbre Binaire"""ifest_ABV(arbre):return0else:return1+taille(gauche(arbre))+taille(droite(arbre))
05° Fournir le code d'une fonction taille() qui possède deux cas de base : l'arbre vide (on renvoie 0) et la feuille (on renvoie 1).
Pour un humain, est-ce une meilleure ou une moins bonne version que la précédente ?
Pour la machine, est-ce une meilleure ou une moins bonne version que la précédente ?
...CORRECTION...
1
2
3
4
5
6
7
8
9
deftaille(arbre:'AB')->int:"""Renvoie la taille de l'Arbre Binaire"""ifest_ABV(arbre):return0elifest_ABV(gauche(arbre))andest_ABV(droite(arbre)):return1else:return1+taille(gauche(arbre))+taille(droite(arbre))
Bien mieux pour un humain qui rédige car on atteint plus vite un cas de base (la feuille) qu'on parvient à détecter visuellement et facilement.
Par contre, pour la machine c'est moins bien : on tombe plus souvent sur des noeuds qui ne sont pas des feuillles. Et donc :
Avec cette version à deux cas de base, on effectue 3 vérifications avant de passer la main;
Avec la version précédente, on effectue uniquement 1 vérification (suis-le vide ?)
La version à un seul cas de base va donc être plus rapide.
06° Réaliser l'empilement (en TOP -> DOWN) des appels récursifs de la fonction taille() sur l'arbre de racine A, qu'on notera aa. Fournir ensuite la réponse finale que va renvoyer la fonction. On prendra l'algorithme à deux cas de base pour limiter les appels récursifs : sur le cas d'une feuille, on peut répondre immédiatement.
...CORRECTION...
07° Réaliser l'empilement des appels récursifs de la fonction taille() sur l'arbre aa (en BOTTOM -> UP sinon, ça va être long). Fournir ensuite la réponse finale que va renvoyer la fonction. On prendra l'algorithme à deux cas de base pour limiter les appels récursifs : sur le cas d'une feuille, on peut répondre immédiatement.
Finaliser la réponse en notant les réponses sur l'arbre.
un noeud n'ayant que des sous-arbres vides (une feuille donc) ?
08° Que doit renvoyer la fonction récursive nb_f() qui compte les feuilles sur le cas de base "Arbre Vide" ? Sur le cas de base "Feuille" ? Comment tester qu'un arbre est en réalité constitué uniquement d'une feuille ?
Fournir alors le code de la fonction récursive nb_f().
...CORRECTION...
Si l'arbre est vide : on renvoie 0.
Si l'arbre est constitué uniquement une feuille : on renvoie 1.
L'arbre est constitué d'une feuille si les sous-arbres gauche et droite sont des arbres vides.
Sinon, c'est le cas récursif : on renvoie la somme de l'appel de cette fonction à gauche et de l'appel à droite.
1
2
3
4
5
6
7
8
9
defnb_f(arbre:'AB')->int:"""Renvoie le nombre de feuilles de l'Arbre Binaire"""ifest_ABV(arbre):return0elifest_ABV(gauche(arbre))andest_ABV(droite(arbre)):return1else:returnnb_f(gauche(arbre))+nb_f(droite(arbre))
09° Réaliser l'empilement des appels récursifs de la fonction nb_f() sur l'arbre de racine A, qu'on notera aa (en TOP -> DOWN). Fournir ensuite la réponse finale que va renvoyer la fonction.
...CORRECTION...
10° Réaliser l'empilement des appels récursifs de la fonction nb_f() sur l'arbre aa (en BOTTOM -> UP). Fournir ensuite la réponse finale que va renvoyer la fonction. Placer les valeurs sur l'arbre.
...CORRECTION...
11° Réaliser le prédicat est_present(). La fonction doit renvoyer True si la clé fournie apparaît bien dans l'Arbre Binaire.
Cas de base 1 : si l'arbre est vide, on renvoie False car elle ne peut être là.
Cas de base 2 : la clé de la racine a la bonne valeur, 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 : quel est le seul cas où un OU renvoie False ?
1
2
3
defest_present(arbre:'AB',c:'Cle')->bool:"""Prédicat : True si c est la clé d'un des noeuds"""pass
...CORRECTION...
1
2
3
4
5
6
7
8
9
defest_present(arbre:'AB',c:'Cle')->bool:"""Prédicat : True si c est la clé d'un des noeuds"""ifest_ABV(arbre):returnFalseelifcontenu(racine(arbre))==c:returnTrueelse:returnest_present(gauche(arbre),c)orest_present(droite(arbre),c)
12° Réaliser l'empilement des appels récursifs de la fonction est_present() sur l'arbre de racine A en recherchant la clé "B". Fournir ensuite la réponse finale que va renvoyer la fonction. N'oubliez pas que le OU et le ET sont paresseux en Python : si la lecture du premier terme permet de répondre, on n'évalue pas le deuxième terme.
...CORRECTION...
13° Réaliser l'empilement des appels récursifs de la fonction est_present() sur l'arbre de racine A en recherchant la clé "C". Fournir ensuite la réponse finale que va renvoyer la fonction. N'oubliez pas que le OU et le ET sont paresseux en Python.
