Exercice 1 · Bac Numérique et Sciences Informatiques Métropole 1 remplacement 2022

EXERCICE 1 (4 points)

Cet exercice porte sur le thème « Algorithmique », les arbres binaires de recherche et leurs parcours.

Rappel

Un arbre binaire de recherche (ABR) est un arbre binaire étiqueté avec des clés tel que:

Les clés du sous arbre gauche sont inférieures ou égales à celle de la racine;

Les clés du sous arbre droit sont strictement supérieures à celle de la racine;

Les deux sous arbres sont eux-mêmes des arbres binaires de recherche.

Partie A: Préambule

1)

Recopier sur votre copie le ou les numéro(s) correspondant aux arbres binaires de recherche parmi les arbres suivants:

Partie B: Analyse

On considère la structure de données abstraites ABR (Arbre Binaire de Recherche) que l'on munit des opérations suivantes:

Structure de données: ABR

Utilise: Booleen, Element

Opérations:

• creer_arbre: ∅ → ABR

creer_arbre() renvoie un arbre vide.

• est_vide: ABR → Booleen

est_vide(a) renvoie True si l'arbre a est vide et False sinon.

• racine: ABR → Element

racine(a) renvoie la clé de la racine de l'arbre non vide a.

• sous_arbre_gauche: ABR → ABR

sous_arbre_gauche(a) renvoie le sous-arbre gauche de l'arbre non vide a.

• sous_arbre_droit: ABR → ABR

sous_arbre_droit(a) renvoie le sous-arbre droit de l'arbre non vide a.

• inserer: ABR, Element → Rien

inserer(a, e) insère la clé e dans l'arbre a.

2.a)

Pour rechercher une clé dans un ABR, il faut comparer la clé donnée avec la clé située à la racine. Si cette clé est à la racine, la fonction renvoie vrai sinon il faut procéder récursivement sur les sous arbres à gauche ou à droite.

2.b)

def RechercheValeur(cle, a):

3.

On considère l'ABR ci-contre: