2021, Métropole, sujet 1, exercice 1⚓︎
Thème : Arbres binaires de recherche
Dans cet exercice, les arbres binaires de recherche de peuvent pas comporter plusieurs fois la même clé. De plus, un arbre binaire de recherche limité à un nœud a une hauteur de 1.
On considère l'arbre binaire de recherche représenté ci-dessous (figure 1), où val
représente un entier :
Figure 1. Un ABR
Question 1a
Donner le nombre de feuilles de cet arbre et préciser leur valeur (étiquette)
Réponse
L'arbre de la figure 1 possède 4 feuilles dont les valeurs sont : \(12\), val, \(21\) et \(32\)
Question 1b
Donner le sous-arbre gauche du nœud \(23\).
Réponse
Il s'agit de l'arbre de racine 19 :
Question 1c
Donner la hauteur et la taille de l'arbre.
Réponse
L'arbre est de hauteur 4 (nombre de nœuds du chemin le plus long de la racine à une feuille) et de taille 9 (nombre de nœuds).
Question 1d
Donner les valeurs entières possibles de val pour cet arbre binaire de recherche.
Réponse
Puisque val se trouve dans le sous-arbre gauche de la racine dont la valeur est \(18\) alors les valeurs \(v\) possibles sont telles que \(v \lt 18\). Mais \(v\) est aussi dans le sous-arbre droit de l'arbre de racine \(15\) donc \(v\) vérifie aussi : \(v\gt 15\). Les valeurs entières possibles sont donc \(16\) et \(17\).
On suppose, pour la suite de cet exercice, que val est égal à \(16\).
On rappelle qu'un parcours infixe depuis un nœud consiste, dans l'ordre, à faire un parcours infixe sur le sous-arbre gauche, afficher le nœud puis faire un parcours infixe sur le sous-arbre droit.
Dans le cas d'un parcours suffixe, on fait un parcours suffixe sur le sous-arbre gauche puis un parcours suffixe sur le sous-arbre droit, avant d'afficher le nœud.
Question 2a
Donner les valeurs d'affichage des nœuds dans le cas du parcours infixe de l'arbre.
Réponse
Les valeurs dans un parcours infixe : \(12, 13, 15, 16, 18, 19, 21, 23, 32\).
Question 2b
Donner les valeurs d'affichage des nœuds dans le cas du parcours suffixe de l'arbre.
Réponse
Les valeurs dans un parcours suffixe : \(12, 13, 16, 15, 21, 19, 32, 23, 18\).
Remarque
Jusque là les questions sont simples : des questions de cours classiques.
On considère la classe Noeud
définie de la façon suivante en Python :
classe Noeud
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 |
|
Remarque
On retrouve ici une maladresse classique dans les implémentations par classe :
- on amalgame arbre et nœud mais en gardant le nœud comme référence, du coup :
- un nœud peut être absent (
None
) ce qui oblige à prendre en compte ce cas particulier au lieu de manipuler des arbres vides
Question 3a
Représenter l'arbre construit suite à l'exécution de l'instruction suivante :
racine = Noeud(18)
racine.insere_tout([12, 13, 15, 16, 19, 21, 32, 23])
Réponse
Question 3b
Écrire les deux instructions permettant de construire l'arbre de la Figure 1. On rappelle que le nombre val est égal à \(16\).
Réponse
fig_1 = Noeud(18)
fig_1.insere_tout([15, 23, 13, 16, 19, 32, 12, 21])
Question 3c
On considère l'arbre tel qu'il est représenté sur lla figure 1. Déterminer l'ordre d'exécution des blocs (repérés de 1 à 3) suite à l'application de la méthode insere(19)
au nœud racine de cet arbre.
Réponse
L'appel fig_1.insere(19)
provoque l'exécution des blocs dans cet ordre : bloc 3, bloc 2, bloc 1
Question 4
Écrire une méthode recherche(self, v)
qui prend en argument un entier v
et renvoie la valeur True
si cet entier est une étiquette de l'arbre, False
sinon.
Réponse
def recherche(self, v):
if self.v == v:
return True
elif self.v < v:
if self.gauche is None:
return False
else:
return self.gauche.recherche(v)
else:
if self.droit is None:
return False
else:
return self.droit.recherche(v)
Remarque
On retrouve ici l'inconvénient de devoir composer avec la valeur None
. Voici une implémentation et une méthode recherche
plus légères. Le nom de la classe a été changé car finalement cela correspond plus à un ABR qu'à un nœud (un nœud vide on ne sait pas bien ce que c'est).
De plus les arbres sont des structures récursives et il est dommage de ne pas les exploiter pour écrire des méthodes récursives (la méthode insere
par exemple).
class ABR:
def __init__(self, v=None):
self.valeur = v
if v is not None:
self.gauche = ABR()
self.droit = ABR()
def est_vide(self):
return self.valeur is None
def insere(self, v):
if self.est_vide():
self.valeur = v
self.gauche = ABR()
self.droit = ABR()
elif v < self.valeur:
self.gauche.insere(v)
else:
self.droit.insere(v)
def insere_tout(self, vals):
for v in vals:
self.insere(v)
def recherche(self, v):
if self.est_vide():
return False
elif v < self.valeur:
self.gauche.recherche(v)
else:
self.droit.recherche(v)