Exercice 2 · Bac Numérique et Sciences Informatiques Polynésie 2024 (jour 2)

Exercice 2 (6 points)

Cet exercice porte sur les arbres binaires de recherche, la POO et la récursivité.

Nous disposons d'une classe ABR pour les arbres binaires de recherche dont les clés sont des entiers:

class ABR():

def __init__(self):

# Initialise une instance d'ABR vide.

def cle(self):

# Renvoie la clé de la racine de l'instance d'ABR.

def sad(self):

# Renvoie le sous-arbre droit de l'instance d'ABR.

def sag(self):

# Renvoie le sous-arbre gauche de l'instance d'ABR.

def est_vide(self):

# Renvoie True si l'instance d'ABR est vide et False sinon.

def inserer(self, cle_a_inserer):

# Insère cle_a_inserer à sa place dans l'instance d'ABR.

Considérons ci-dessous trois arbres binaires de recherche:

Dans tout l'exercice, nous ferons référence à ces trois arbres binaires de recherche et utiliserons la classe ABR et ses méthodes.

Partie A

1.

Compléter le texte ci-dessous en choisissant les expressions appropriées:

Le nœud initial est appelé

.

Un nœud qui n'a pas de fils est appelé

.

Un arbre binaire est un arbre dans lequel chaque nœud a

deux fils.

Un arbre binaire de recherche est un arbre binaire dans lequel tout nœud est associé à une clé qui est:

supérieure à chaque clé de tous les nœuds de son

inférieure à chaque clé de tous les nœuds de son

.

2.

Donner dans l'ordre les clés obtenues lors du parcours préfixe de l'arbre no 1.

3.

Donner dans l'ordre, les clés obtenues lors du parcours suffixe, également appelé postfixe, de l'arbre no 2.

4.

Donner dans l'ordre, les clés obtenues lors du parcours infixe de l'arbre no 3.

5.

Recopier et compléter les instructions ci-dessous afin de définir puis de construire, en y insérant les clés dans un ordre correct, les trois instances de la classe ABR:

6.

Voici le code de la méthode hauteur de la classe ABR:

def hauteur(self):

if self.est_vide():

return -1

else:

return 1 + max(self.sag().hauteur(),

self.sad().hauteur())

Donner, en utilisant cette méthode, la hauteur des trois instances:

Hauteur de arbre_no1:

Hauteur de arbre_no2:

Hauteur de arbre_no3:

7.

Recopier et compléter le code de la méthode est_presente ci-dessous:

def est_presente(self, cle_a_rechercher):

if self.est_vide():

return...

elif cle_a_rechercher == self.cle():

return...

elif cle_a_rechercher < self.cle():

return...

else:

return...

8.

Expliquer quelle instruction, parmi les trois ci-dessous, nécessitera le moins d'appels récursifs avant de renvoyer son résultat:

Partie B

9.

On donne la méthode est_partiellement_equilibre(self) de la classe ABR:

def est_partiellement_equilibre(self):

if self.est_vide():

return True

return abs(self.sag().hauteur() - self.sad().hauteur()) <= 1

Expliquer ce qu'on appelle ici un arbre partiellement équilibré.

10.

Justifier que, parmi les trois arbres définis plus haut, deux sont partiellement équilibrés.

11.

Un arbre binaire est équilibré s'il est partiellement équilibré et si ses deux sous-arbres, droit et gauche, sont eux-mêmes équilibrés. Un arbre vide est considéré comme équilibré.

Justifier que, parmi les trois arbres définis plus haut, un seul est équilibré.

12.

Définir et coder la méthode récursive est_equilibre de la classe ABR qui renvoie True si l'instance de la classe ABR est l'implémentation d'un arbre équilibré et False sinon.

def est_equilibre(self):