Pour chaque question, une seule réponse est correcte.
1. Quelle est la hauteur d’un arbre binaire réduit à sa racine (sans fils) ?
Correction publiée après la séance.
2. Un arbre binaire de hauteur 3 peut contenir au maximum :
Correction publiée après la séance.
3. Quel parcours d’un ABR produit les valeurs dans l’ordre croissant ?
Correction publiée après la séance.
4. On cherche la valeur 42 dans un ABR équilibré contenant 1 000 nœuds. Le nombre maximal de comparaisons est environ :
Correction publiée après la séance.
5. On insère les valeurs 1, 2, 3, 4, 5 dans cet ordre dans un ABR vide. Quelle forme a l’arbre obtenu ?
Correction publiée après la séance.
On considère l’arbre binaire suivant :
| Parcours | Ordre de visite des nœuds |
|---|---|
| Préfixe (nœud, gauche, droit) | |
| Infixe (gauche, nœud, droit) | |
| Suffixe (gauche, droit, nœud) |
Appliquer la règle dans chaque sous-arbre : pour le préfixe, écrire la racine, puis tout le parcours du sous-arbre gauche, puis celui du sous-arbre droit, et ainsi de suite.
| Étape | File (avant traitement) | Nœud traité | Fils ajoutés à la file |
|---|---|---|---|
| 1 | [R] | ||
| 2 | |||
| 3 | |||
| … |
La file sort par l’avant : à chaque étape, retirer le premier nœud de la file, le traiter, puis ajouter ses fils, gauche puis droit, à la fin de la file. On s’arrête quand la file est vide.
Quelle est la taille de cet arbre ? Sa hauteur ?
La taille est le nombre de nœuds. Pour la hauteur, compter le plus long chemin de la racine à une feuille, avec la convention du cours.
Correction publiée après la séance.
On utilise la classe Arbre définie en cours (valeur, gauche, droit). Un arbre vide est représenté par None.
a) Compléter la fonction qui renvoie True si une valeur x est présente dans un arbre binaire quelconque (pas nécessairement un ABR) :
def contient(arbre, x):
if arbre is None:
return ...
if arbre.valeur == x:
return ...
return contient(..., x) or contient(..., x)
Un arbre vide ne contient rien. Sinon, x est présent s’il est à la racine, ou dans le sous-arbre gauche, ou dans le sous-arbre droit.
b) Compléter la fonction qui renvoie la liste des feuilles d’un arbre binaire :
def liste_feuilles(arbre):
if arbre is None:
return ...
if arbre.gauche is None and arbre.droit is None:
return ...
return liste_feuilles(...) + liste_feuilles(...)
Un arbre vide n’a aucune feuille. Une feuille, nœud sans fils, donne la liste qui contient sa seule valeur. Sinon, on réunit les feuilles des deux sous-arbres.
c) Compléter la fonction qui renvoie le parcours préfixe sous forme de liste :
def prefixe_liste(arbre):
if arbre is None:
return []
return [...] + prefixe_liste(...) + prefixe_liste(...)
Préfixe : la valeur de la racine d’abord, puis le parcours du sous-arbre gauche, puis celui du sous-arbre droit.
d) Pour la fonction contient complétée en a), identifier, sans exécuter le code, les cas de base (quelles conditions arrêtent la récursion ?) et les appels récursifs (comment le problème se réduit-il ?).
Les cas de base sont les return qui ne rappellent pas la fonction ; les appels récursifs portent sur des arbres plus petits que l’arbre de départ.
Correction publiée après la séance.
On insère les valeurs suivantes, dans cet ordre, dans un ABR initialement vide : 8, 3, 10, 1, 6, 14, 4, 7, 13.
Dessiner l’ABR obtenu après chaque insertion (ou au minimum après les insertions de 8, 3, 10, 1, 6, et l’arbre final).
Chaque nouvelle valeur part de la racine : on descend à gauche si elle est plus petite que le nœud, à droite sinon, jusqu’à une place libre, où elle devient une feuille.
Donner la taille et la hauteur de l’ABR final.
Mêmes définitions qu’à l’exercice 2 : compter les nœuds, puis le plus long chemin de la racine à une feuille.
Effectuer le parcours infixe de l’ABR et vérifier qu’on obtient les valeurs dans l’ordre croissant.
Infixe : sous-arbre gauche, nœud, sous-arbre droit. Dans un ABR, tout le sous-arbre gauche est plus petit que le nœud, et tout le sous-arbre droit plus grand.
On cherche la valeur 7 dans cet ABR. Lister les comparaisons effectuées et le chemin suivi.
Partir de la racine et comparer 7 à chaque nœud rencontré : s’il est plus petit, descendre à gauche ; plus grand, à droite ; égal, la recherche s’arrête.
Correction publiée après la séance.
On utilise la classe Arbre du cours. Écrire les fonctions suivantes :
somme(arbre) : renvoie la somme de toutes les valeurs (entières) de l’arbre. Renvoie 0 si l’arbre est vide.
Arbre vide : 0. Sinon, la somme est la valeur de la racine, plus la somme du sous-arbre gauche, plus celle du sous-arbre droit.
def somme(arbre):
if arbre is None:
return ...
return arbre.valeur + somme(...) + somme(...)
miroir(arbre) : renvoie un nouvel arbre qui est le miroir de l’arbre donné (les sous-arbres gauche et droit sont échangés à chaque nœud).
Le miroir d’un arbre vide est vide. Sinon, créer un nouvel arbre de même valeur, dont le fils gauche est le miroir du sous-arbre droit, et le fils droit le miroir du sous-arbre gauche.
def miroir(arbre):
if arbre is None:
return None
return Arbre(arbre.valeur, miroir(...), miroir(...))
meme_structure(a1, a2) : renvoie True si les deux arbres ont la même structure (même forme), indépendamment des valeurs.
Deux arbres vides ont la même structure ; si un seul des deux est vide, non. Sinon, les sous-arbres gauches doivent avoir la même structure, et les sous-arbres droits aussi.
def meme_structure(a1, a2):
if a1 is None and a2 is None:
return True
if a1 is None or a2 is None:
return ...
return meme_structure(a1.gauche, ...) and meme_structure(..., ...)
Correction publiée après la séance.
Un arbre d’expression est un arbre binaire où les feuilles contiennent des nombres et les nœuds internes contiennent des opérateurs (+, -, *, /).
Par exemple, l’expression \((3 + 4) \times (8 - 2)\) est représentée par :
Dessiner l’arbre d’expression correspondant à \((5 + 1) \times 2 - (9 / 3)\).
La racine porte l’opération effectuée en dernier, ici la soustraction : son fils gauche représente \((5 + 1) \times 2\), et son fils droit \(9 / 3\).
Écrire une fonction récursive evaluer(arbre) qui évalue un arbre d’expression et renvoie le résultat du calcul.
Indications :
Le nœud est une feuille quand arbre.gauche is None and arbre.droit is None. Pour un opérateur, calculer g = evaluer(arbre.gauche) et d = evaluer(arbre.droit), puis choisir l’opération selon arbre.valeur.
def evaluer(arbre):
if arbre.gauche is None and arbre.droit is None:
return arbre.valeur
g = evaluer(arbre.gauche)
d = evaluer(arbre.droit)
if arbre.valeur == "+":
return g + d
elif arbre.valeur == "-":
return ...
elif arbre.valeur == "*":
return ...
else:
return ...
Quel parcours correspond à la notation polonaise inversée (NPI) de l’expression ? Donner la NPI de l’arbre de la question 1.
En NPI, les deux opérandes s’écrivent avant l’opérateur : quel parcours visite le nœud après ses deux sous-arbres ?
Bonus. Écrire une fonction infixe_parenthesee(arbre) qui renvoie l’expression en notation infixe avec parenthèses. Par exemple, pour l’arbre ci-dessus : "((3+4)*(8-2))".
Une feuille donne str(arbre.valeur). Pour un opérateur, assembler "(", l’expression du sous-arbre gauche, l’opérateur, celle du sous-arbre droit, puis ")".
Correction publiée après la séance.