Exercice 3 - Arbres binaires de recherche · Bac Numérique et Sciences Informatiques Centres étrangers (Afrique) 2023 (jour 2)

EXERCICE 3 (4 points)

Cet exercice porte sur la programmation en Python, la manipulation des chaînes de caractères, les arbres binaires de recherche et le parcours de liste.

1. On rappelle ici quelques notions sur la manipulation des chaînes de caractères en Python.

Une chaîne de caractères se comporte comme un tableau de caractères que l'on ne peut pas modifier.

Par exemple, on a le comportement suivant:

>>> une_chaine = 'Bonjour'

>>> une_chaine[3]

'j'

>>> une_chaine[3] = 'z'

TypeError: 'str' object does not support item assignment

On peut aussi utiliser l'opérateur de concaténation +.

>>> une_chaine = 'a' + 'b'

>>> une_chaine

'ab'

>>> une_chaine = une_chaine + 'c'

>>> une_chaine

'abc'

On définit la fonction bonjour par le code suivant:

1 def bonjour(nom)

2 return 'Bonjour ' + nom + ' !'

2. Construction d'arbres binaires de recherche

On rappelle qu'un arbre binaire de recherche est un arbre binaire pour lequel chaque nœud possède une étiquette dont la valeur est supérieure ou égale à toutes les étiquettes des nœuds de son fils gauche et strictement inférieure à celles des nœuds de son fils droit.

Sa taille est son nombre de nœuds; sa hauteur est le nombre de niveaux qu'il contient.

On rappelle aussi que l'on peut comparer des chaînes de caractères en utilisant l'ordre alphabétique. On a par exemple:

>>> 'ab' < 'aa'

False

>>> 'abc' < 'acb'

True

On considère la liste de mots: animaux = ['python', 'chameau', 'pingouin', 'renard', 'gnou']

a.

Dessiner un arbre binaire de recherche contenant tous les mots de la liste animaux et de hauteur minimale.

b.

Dessiner un arbre binaire de recherche contenant tous ces mots et de hauteur maximale.

3. Algorithmes récursifs sur les ABR

On considère l'implémentation objet suivante d'un arbre binaire de recherche:

On dispose d'une classe Abr contenant notamment les méthodes et attributs suivants:

Si un_abr est une instance d' Abr alors un_abr.est_vide() renvoie True si l'arbre est vide et False sinon.

Si un_abr est une instance d' Abr et si un_abr.est_vide() renvoie False, alors un_abr.valeur contient une chaîne de caractères représentant la valeur de la racine de l'arbre.

Si un_abr est une instance d' Abr et si un_abr.est_vide() renvoie False, alors un_abr.sous_arbre_gauche et un_abr.sous_arbre_droit contiennent chacun une instance d' Abr.

On considère que la variable liste_mots_francais est une liste de 336531 mots en français et que la variable abr_mots_francais est une instance d' Abr contenant les mots de la liste.

On considère la fonction suivante:

def mystere(un_abr):

if un_abr.est_vide():

return 0

else:

return 1 + mystere(un_abr.sous_arbre_gauche) \

+ mystere(un_abr.sous_arbre_droit)

Remarque: on rappelle que le caractère \ en fin de ligne indique que l'instruction se poursuit sur la ligne suivante.

a.

Donner le résultat de mystere(abr_mots_francais), en justifiant le résultat.

b.

On veut calculer la hauteur de abr_mots_francais.

Donner le code d'une fonction hauteur(un_abr) permettant de faire ce calcul, en vous inspirant du code précédent.