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é
Les fonctions liées aux Noeuds :
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.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: on crée un nouvel ARBRE BINAIRE dont la racine est r et dont les sous-arbres sont g et d fournis.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.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.droite(arbre:Arbre) -> Arbre: renvoie le sous-arbre droit de arbre.
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à quels sont les cas d'arrêt.
Si l'Arbre Binaire est un arbre vide, on peut répondre : la hauteur est
- 0 si on prend pour une profondeur de 1 pour la racine.
- -1 si on prend une profondeur de 0 pour la racine.
Et dans les autres cas, on peut pas répondre immédiatement. On faut relancer des appels récursifs.
On peut juste répondre que la hauteur de l'arbre est soit
- 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 | |
Exemple graphique hyper détaillé avec la recherche de la hauteur de l'Arbre ag.
On cherche la hauteur à partir de la racine G. Ce n'est pas un arbre binaire vide. L'appel à la fonction va renvoyer :
hauteur(ag) va renvoyer 1 + max(hauteur(gauche(ag)), hauteur(droite(ag))), ou simplement
hauteur(ag) va renvoyer 1 + max(hauteur(arbre vide), hauteur(ah)).
On doit donc faire deux appels recursifs pour obtenir la réponse :
hauteur(arbre vide) renvoie -1, un cas de base, une réponse définitive.
hauteur(ah) va renvoyer 1 + max(hauteur(arbre vide), hauteur(arbre vide)).
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(arbre vide), 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 | |
...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), 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 | |
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 | |
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 ou 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 | |
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 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 ?
1
2
3 | |
...CORRECTION...
1
2
3
4
5
6
7
8 | |
12° Réaliser l'empilement des appels récursifs de la fonction estPresent sur l'arbre de racine A en rechant 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.
...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.