Exercice 3 - Arbres binaires de recherche · Bac Numérique et Sciences Informatiques Amérique du Nord 2023 (jour 1)

Exercice 3 (4 points)

Cet exercice porte sur la programmation orientée objet et sur les arbres. Il contient deux parties indépendantes.

Lors de la création d'un jeu vidéo, un développeur décide d'utiliser la programmation orientée objet. Au cours de ce jeu, différents personnages vont s'affronter tour à tour. Pour cela, le développeur décide de créer une classe Personnage.

Un personnage est caractérisé par les données suivantes:

clan: chaine de caractères qui identifie le clan auquel le personnage appartient;

vie: nombre entier qui représente le nombre de points de vie du personnage. Un personnage n'est plus actif dès que le nombre de points de vie devient inférieur ou égal à zéro;

force: nombre entier qui représente le nombre de points de force.

Les personnages peuvent effectuer différentes actions: attaquer un ennemi, se défendre face à un ennemi, etc.

Partie A: programmation orientée objet

Partie B: arbres binaires de recherche

Dans cette partie:

les arbres binaires de recherche ne peuvent pas contenir plusieurs fois la même clé;

un arbre binaire de recherche limité à un nœud a une hauteur égale à 1;

la taille d'un arbre est le nombre de nœuds de cet arbre;

la valeur d'un nœud (aussi appelée clé) est:

strictement supérieure à celle des nœuds de son sous-arbre gauche,

strictement inférieure à celle des nœuds de son sous-arbre droit,

la racine d'un arbre binaire est le seul nœud n'ayant pas de parent.

On dispose de l'interface suivante pour manipuler les arbres binaires de recherche:

est_vide: arbre → booléen · renvoie vrai si l'arbre est vide, faux sinon

gauche: arbre → arbre · renvoie le sous-arbre gauche

droit: arbre → arbre · renvoie le sous-arbre droit

valeur_racine: arbre → valeur · renvoie la valeur de la racine de l'arbre

6.

On considère l'arbre binaire de recherche ci-dessous:

a)

Donner sans justification la hauteur et la taille de l'arbre.

b)

On insère dans l'arbre binaire de recherche ci-avant la clé dont la valeur est 46. Représenter l'arbre obtenu après cette insertion.

7.

On propose la fonction parcours ci-dessous, en langage Python:

def parcours(arbre):

if not est_vide(arbre):

parcours(gauche(arbre))

print(valeur_racine(arbre))

parcours(droit(arbre))

a)

Donner le nom de ce parcours.

b)

En considérant l'arbre donné en exemple (sans l'ajout de la valeur 46), indiquer l'ordre dans lequel les valeurs des nœuds seront affichées.

8.

Pour le jeu vidéo défini dans la partie A, on souhaite collecter l'équipement d'un personnage (vêtements, armes, nourriture,...) en utilisant un arbre binaire de recherche.

Chaque type de matériel est identifié par un nombre entier. D'autre part, un personnage peut disposer d'un même matériel en plusieurs exemplaires; il peut par exemple posséder 12 flèches, toutes de même type (et possédant donc la même référence).

Dans cette question, les clés sont des tableaux non dynamiques contenant deux informations:

un premier entier (la référence du matériel),

un deuxième entier (la quantité correspondante pour ce matériel).

Le placement dans l'arbre binaire de recherche se fait en fonction de la référence du matériel (premier élément du tableau).

L'arbre donné précédemment peut devenir par exemple:

Si cle vaut [28, 3], alors cle[0] vaut 28 et cle[1] vaut 3.

La fonction recherche_dichotomique prend en paramètre un arbre binaire de recherche et un entier (référence de matériel) et renvoie la quantité associée au matériel si celui-ci est présent dans l'arbre, -1 sinon.

Recopier et compléter la fonction recherche_dichotomique suivante: