Exercice 3 - Partie 1 · Bac Numérique et Sciences Informatiques Métropole 2023 (sujet 2)

EXERCICE 3 (6 points)

Cet exercice porte sur les arbres binaires, les files et la programmation orientée objet.

Cet exercice comporte deux parties indépendantes.

PARTIE 1

Une entreprise stocke les identifiants de ses clients dans un arbre binaire de recherche.

On rappelle qu’un arbre binaire est composé de nœuds, chacun des nœuds possédant éventuellement un sous-arbre gauche et éventuellement un sous-arbre droit.

La taille d’un arbre est le nombre de nœuds qu’il contient. Sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l’une des feuilles. On convient que la hauteur d’un arbre ne contenant qu’un nœud vaut 1 et celle de l’arbre vide vaut 0.

Dans cet arbre binaire de recherche, chaque nœud contient une valeur, ici une chaine de caractères, qui est, avec l’ordre lexicographique (celui du dictionnaire):

strictement supérieure à toutes les valeurs des nœuds du sous-arbre gauche;

strictement inférieure à toutes les valeurs des nœuds du sous-arbre droit.

Ainsi les valeurs de cet arbre sont toutes distinctes.

On considère l’arbre binaire de recherche suivant:

1.

Donner la taille et la hauteur de l'arbre binaire de recherche de la figure 1.

2.

Recopier cet arbre après l'ajout des identifiants suivants: 'davidbg' et 'papicoeur' dans cet ordre.

3.

On décide de parcourir cet arbre pour obtenir la liste des identifiants dans l'ordre lexicographique.

Recopier la lettre correspondant au parcours à utiliser parmi les propositions suivantes:

4.

Pour traiter informatiquement les arbres binaires, nous allons utiliser une classe ABR.

Un arbre binaire de recherche, nommé abr dispose des méthodes suivantes:

abr.est_vide(): renvoie True si abr est vide et False sinon.

abr.racine(): renvoie l'élément situé à la racine de abr si abr n'est pas vide et None sinon.

abr.sg(): renvoie le sous-arbre gauche de abr s'il existe et None sinon.

abr.sd(): renvoie le sous-arbre droit de abr s'il existe et None sinon.

On a commencé à écrire une méthode récursive present de la classe ABR, où le paramètre identifiant est une chaîne de caractères et qui retourne True si identifiant est dans l'arbre et False sinon.

1 def present(self, identifiant):

2 if self.est_vide():

3 return False

4 elif self.racine() == identifiant:

5 return...

6 elif self.racine() < identifiant:

7 return self.sd()....

8 else:

9 return...

Recopier et compléter les lignes 5, 7 et 9 de cette méthode.