Exercice 1 - Arbre binaire de recherche · Bac Numérique et Sciences Informatiques Centres étrangers (Afrique) 2026 (jour 1)

Exercice 1 (6 points)

Cet exercice porte sur les algorithmes de tri et d'un parcours d'arbre binaire de recherche et sur la programation orientée objet

Contexte

Un club d’athlétisme organise une compétition inter-scolaire regroupant quatre disciplines:

le 100 mètres;

le saut en longueur;

le lancer du poids;

le 1500 mètres.

Chaque athlète réalise une performance dans chacune de ces épreuves. Pour établir le classement final, un score global est calculé à partir de ses résultats selon des règles de conversion simples. L’objectif du programme est de modéliser ces athlètes et d’implémenter différentes méthodes de tri pour les classer du premier au dernier.

Le score d’un athlète est la somme des points obtenus dans chaque épreuve. Ces points s’obtiennent selon les règles suivantes:

points du 100 m: $(20 - t) * 10$ avec $t$ le temps en secondes;

points du saut en longueur: $d * 20$ avec $d$ la distance en mètres;

points du lancer de poids: $d * 10$ avec $d$ la distance en mètres;

points du 1500 m: $(500 - t) * 1$ avec $t$ le temps en secondes.

Partie B: Arbre binaire de recherche

Une nouvelle approche est adoptée, fondée sur la programmation orientée objet et la mise en œuvre d'un arbre binaire de recherche, afin de modéliser les athlètes et de produire leur classement automatique en fonction de leur score.

Une fois créés, les athlètes sont insérés dans un arbre binaire de recherche. Chaque athlète y constitue un nœud, positionné selon son score de manière à assurer la propriété suivante: pour chaque athlète, tous les athlètes de son sous-arbre gauche ont un score strictement plus petit et tous les athlètes de son sous-arbre droit un score plus grand ou égal.

9.

Dessiner l'arbre obtenu après l'insertion, dans l'ordre, des six athlètes suivants:

Ordre · Nom · Score

1 · Martin · 354

2 · Lena · 351

3 · Rayan · 350

4 · Yanis · 355

5 · Ninon · 351

6 · Ana · 356

La classe Noeud qui assure l'organisation structurée des athlètes dans un arbre binaire de recherche:

class Noeud:

def __init__(self, athlete):

self.valeur = athlete

self.gauche = None

self.droite = None

def inserer(self, athlete):

if athlete.score < self.valeur.score:

if self.gauche ==...:

self.gauche = Noeud(athlete)

else:

...

else:

if self.droite ==...:

self.droite = Noeud(athlete)

else:

... 10.

On ajoute la méthode ci-dessous à la classe Noeud, qui permet de classer les athlètes de manière décroissante:

def classer(self, classement=None):

if classement is None:

classement = []

if self.droite is not None:

self.droite.classer(classement)

classement.append(self.valeur.nom)

if self.gauche is not None:

self.gauche.classer(classement)

return classement 11.

12.