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

Exercice 5

Principaux thèmes abordés: structures de données (arbre, arbre binaire, pile).

Les valeurs relatives à des temps d'attente en secondes de systèmes électroniques sont stockées dans l'arbre binaire de recherche ci-dessous:

1. a)

Rappeler brièvement ce qu'est un arbre binaire de recherche.

1. b)

Quelle est la première valeur qui a été positionnée dans cet arbre ?

1. c)

Préciser la hauteur de cet arbre. (La racine est considérée au niveau 0)

2.

Recopier l'arbre donné ci-dessus sur votre copie en y ajoutant successivement les données 16 et 12.

3.

Déterminer sur l'arbre ci-dessus, la liste des valeurs obtenue avec un parcours d'arbre en profondeur infixe. Que permet d'obtenir ce parcours ?

4.

On considère l'interface suivante relative à la structure de données « arbre binaire »:

EstVide: ArbreBinaire[E] → Booléen

Racine: ArbreBinaire[E] → E

Sag: ArbreBinaire[E] → ArbreBinaire[E] (sous arbre gauche)

Sad: ArbreBinaire[E] → ArbreBinaire[E] (sous arbre droite)

Recopier sur votre copie et compléter l'algorithme de recherche suivant, qui retourne Vrai si la valeur x est dans l'arbre binaire de recherche A, Faux sinon.

Recherche(A, x):

Si EstVide(A) alors Faux

Si Racine(A)=x alors...

Si x<Racine(A) alors...

Sinon... Si Racine(A)=x alors

Si x<Racine(A) alors

Sinon