15 - Récursivité sur les AB
Nous allons nous attarder sur le déroulement des fonctions récursives que vous avez réalisé dans l'activités précédentes.
Logiciel nécessaire pour l'activité : -
Prérequis :
- Données : Arbre et Arbre Binaire
- Algos : Parcours d'Arbres
- Algos : Algorithmes des Arbres Binaires
Evaluation ✎ :
Documents de cours : open document ou pdf
1 - Fonctions d'interface
Rappel :
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 :
- nvND(cle:Cle, data:Data) -> Noeud
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. - cle(noeud:Noeud) -> Cle
Renvoie la clé ou l'étiquette du noeud. - data(noeud:Noeud) -> Data
Renvoie les données associées au noeud.
Les fonctions liées à l'Arbre Binaire lui-même :
- nvAV() -> Arbre
On le note ainsi pour dire nouvelArbreVide() : on crée un nouvel ARBRE BINAIRE vide. - nvAB(r:Noeud, g:Arbre, d:Arbre) -> Arbre
Crée un nouvel ARBRE BINAIRE dont la racine est r et dont les sous-arbres sont g et d fournis. On peut ne pas transmettre d'Arbre pour g et d. Cela veut dire qu'ils seront des arbres vides.
PRECONDITION : la racine est un noeud NON VIDE. - estArbreVide(arbre:Arbre) -> bool
True si l'arbre est un arbre vide. - racine(arbre:Arbre) -> Noeud
Renvoie le noeud jouant le rôle de la racine pour cet arbre.
PRECONDITION : arbre est NON VIDE. - gauche(arbre:Arbre) -> Arbre
Renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre.
Attention, si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine().
PRECONDITION : arbre est NON VIDE. - droite(arbre:Arbre) -> Arbre
Renvoie le sous-arbre droit de arbre.
PRECONDITION : arbre est NON VIDE.
Dans toute l'activité, nous travaillerons avec cet Arbre Binaire :
1
2
3
4
5
6
7
8 | |
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 | |
1
2
3
4
5
6 | |
1
2
3
4
5
6 | |
2 - Chercher la hauteur de l'Arbre Binaire
Comment parvenir à retrouver le code de la fonction récursive qui permet de déterminer la hauteur de l'Arbre Binaire ?
En se demandant déjà quel est le cas de base.
Si l'Arbre Binaire est un arbre vide, on peut répondre : la hauteur est
- -1 si on prend une profondeur de 0 pour la racine.
Dans les autres cas, on peut pas répondre immédiatement il faut relancer des appels récursifs.
On peut juste répondre que la hauteur de l'arbre est la valeur maximale parmi
- 1 + la hauteur du sous-arbre gauche ou
- 1 + la hauteur du sous-arbre droite.
On dira alors que 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 | |
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)).
On doit donc faire deux appels recursifs pour obtenir la réponse :
Du côté gauche de G, hauteur(AV) renvoie -1, un cas de base.
Du côté droite de G, hauteur(ah) va renvoyer 1 + max(hauteur(AV), hauteur(AV)).
Les deux appels sur un arbre vide font répondre -1.
On peut maintenant dépiler : nous avons toutes nos réponses :
hauteur(ah) renvoie 1 + max(-1, -1).
hauteur(ah) renvoie 1 + -1.
hauteur(ah) renvoie 0.
On peut donc remonter d'un cran :
hauteur(ag) va renvoyer 1 + max(hauteur(AV), hauteur(ah)).
hauteur(ag) renvoie 1 + max(-1, 0).
hauteur(ag) renvoie 1 + 0.
hauteur(ag) renvoie 1.
Comment rédiger cela sans y passer 15 minutes ? Deux façons de faire :
- Noter les appels et réponses sur le schéma
- Noter les appels récursifs 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.
Exemple de rédaction de réponse 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 | |
...CORRECTION...
L'empilement provoque des appels à ces fonctions :
Il reste à dépiler en allant chercher les réponses au fur et à mesure :
On continue :
On peut alors maintenant avoir notre réponse :
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.
...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
La taille correspond au nombre de noeuds.
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 | |
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).
...CORRECTION...
1
2
3
4
5
6
7
8
9 | |
06° Réaliser l'empilement 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. 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...
4 - Recherche récursive
Voyons également comment trouver
- un noeud possèdant une valeur de clé-étiquette précise ?
- 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 | |
09° Réaliser l'empilement des appels récursifs de la fonction nb_f() sur l'arbre de racine A, qu'on notera aa. 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. Fournir ensuite la réponse finale que va renvoyer la fonction.
...CORRECTION...
11° Réaliser le Prédicat 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 : quel est le seul cas où un OU renvoie False ?
1
2
3 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9 | |
12° Réaliser l'empilement des appels récursifs de la fonction estPresent() 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 estPresent() sur l'arbre de racine A en rechant 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.
...CORRECTION...
5 - FAQ
Rien pour le moment
Activité publiée le 13 12 2020
Dernière modification : 13 12 2020
Auteur : ows. h.