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

Exercice 3 (8 points)

Cet exercice porte sur les types de données construits (listes et dictionnaires), sur les arbres binaires de recherche et sur les bases de données

Un ballon-sonde (utilisé en météorologie et en astronautique) est un ballon à gaz libre utilisé pour faire des mesures locales dans l'atmosphère. Chaque mesure réalisée est horodatée et géolocalisée par GPS.

À la fin de leur vol, les radiosondes redescendent vers la terre, se posent « n’importe où » et sont « abandonnées » à leur sort. C’est pourquoi vous pouvez en trouver. Diane Delstar est une radio amatrice appartenant à un club de passionnés. Le club récupère les ballons équipés de leur radiosonde et répertorie toutes les infos de leur atterrissage sur la terre ferme dans une base de données consultable sur un site web (source: https://sondehub.org). Le programme, écrit par Diane, lui permet de récupérer les données relevées par les sondes. La variable enregistrement fait référence à un dictionnaire qui contient un ensemble de données pour une sonde.

Exemple:

enregistrement = {

'num_serie': 623, 'altitude': 1150.0,

'datetime': '2024-06-27T23:36:01.000000Z',

'latitude': 38.38825, 'longitude': 27.09004

}

Lorsque les sondes atterrissent à la fin de leur voyage, elles sont récupérées par les membres du club. Les dernières positions des sondes sont ensuite enregistrées pour être affichées sur le site Web du club. Un arbre binaire de recherche sera exploité par Diane pour gérer la récupération des sondes:

Chaque sonde est associée à un arbre binaire de recherche (ou plus précisément à sa racine);

les arbres binaires de recherche sont des instances de la classe Sonde;

les instances de la classe Sonde possèdent les attributs num_serie, latitude, longitude et date qui décrivent la sonde ainsi que des attributs gauche et droite qui font références aux deux sous-arbres reliés à la racine;

l'arbre binaire de recherche vide est une instance de Sonde dont tous les attributs valent None;

la méthode est_vide renvoie un booléen qui permet de savoir si l'arbre représenté est vide;

si le sous-arbre gauche n'est pas vide, alors son attribut num_serie est strictement inférieur à l'attribut num_serie de la racine;

si le sous-arbre droit n'est pas vide, alors son attribut num_serie est strictement supérieur à l'attribut num_serie de la racine.

Les premières lignes de code de la classe Sonde sont les suivantes:

class Sonde:

def __init__(self, num_serie, latitude, longitude, date,

gauche, droit):

self.num_serie = num_serie

self.latitude = latitude

self.longitude = longitude

self.date = date

self.gauche = gauche

self.droit = droit

def est_vide(self):

return self.num_serie is None

7.

Écrire la ligne de code qui permet de créer une instance sonde623 de la classe Sonde à l'aide des paramètres suivants:

num: 623; lati: 38.38825; long: 27.09004; date: '2024-06-27'

8.

Ci-dessous, un extrait de la représentation graphique de l'arbre binaire de recherche. Les numéros de série ( num_serie) de chaque sonde y sont indiqués.

Recopier et compléter la représentation graphique, ci-dessus, en y ajoutant successivement et dans cet ordre les nœuds suivants:

sonde portant le nom sonde900 et le numéro de série 900;

sonde portant le nom sonde650 et le numéro de série 650;

sonde portant le nom sonde300 et le numéro de série 300.

9.

L'arbre peut être parcouru selon l'ordre de parcours préfixe, infixe, suffixe ou en largeur d'abord. Indiquer celui qui permet de lire les numéros des sondes dans l'ordre croissant des numéros de série.

10.

Compléter la méthode rechercher (lignes 1, 3, 4 et 7), ci-dessous, qui prend en paramètre un numéro de série ( numero) et qui renvoie l'instance de la classe Sonde correspondant au numéro de série ou None si la sonde n'a pas été référencée dans l'arbre.

1 def rechercher(..., numero):

2 if self.est_vide():

3 return...

4 if numero ==...:

5 return self

6 elif numero < self.num_serie:

7 return self.....rechercher(numero)

8 else:

9 return self.droit.rechercher(numero)

11.

Expliquer pourquoi la méthode rechercher est une méthode récursive.