Exercice 2 · Bac Numérique et Sciences Informatiques Amérique du Nord 2023 (jour 2)

Exercice 2 (5 points)

Cet exercice porte sur les arbres binaires, notamment les arbres binaires de recherche et sur la programmation en langage Python.

Partie A

Dans cet exercice, on considère que la hauteur de l'arbre vide est 0.

On considère l'arbre binaire suivant, noté $A$ dans la suite de l'exercice:

1.

Déterminer, sans justifier, la hauteur et la taille de l'arbre binaire $A$:

2.

On utilise l'interface suivante pour un arbre binaire:

Cette interface a été implémentée en langage Python.

a)

Dessiner l'arbre binaire obtenu avec l'instruction suivante:

cons(7,

cons(4,

cons(2, arbre_vide(), arbre_vide()),

cons(6,

cons(5, arbre_vide(), arbre_vide()),

arbre_vide())),

cons(9,

arbre_vide(),

cons(8, arbre_vide(), arbre_vide())))

b)

Déterminer la ou les instructions en langage Python permettant d'obtenir l'arbre binaire suivant:

3.

a)

Déterminer l'ordre des valeurs obtenu lorsqu'on parcourt l'arbre $A$ à l'aide d'un parcours infixe.

b)

La fonction parcours incomplète ci-après prend en argument un arbre binaire et renvoie un tableau contenant les valeurs de l'arbre, dans l'ordre obtenu lors d'un parcours infixe.

def parcours(arbre):

if est_vide(arbre):

return []

else:

...

Déterminer parmi les trois propositions suivantes, quelle instruction doit-être écrite à la ligne 5:

Partie B

Un arbre binaire de recherche est un arbre binaire dans lequel chaque nœud possède une valeur, telle que chaque nœud du sous arbre gauche ait une valeur inférieure ou égale à celle du nœud considéré, et que chaque nœud du sous arbre droit ait une valeur supérieure à celle-ci.

Par exemple, l'arbre suivant, noté $B$ dans la suite de l'exercice, est un arbre binaire de recherche:

4.

Déterminer en justifiant, parmi les arbres suivants, ceux qui ne sont pas des arbres binaires de recherche:

5.

Déterminer, en justifiant, quel parcours d'un arbre binaire de recherche permet d'obtenir les valeurs de l'arbre classées par ordre croissant.

6.

On ajoute à l'interface des arbres binaires une fonction inserer_dans_ABR qui prend en arguments un arbre binaire de recherche et une valeur, et qui ajoute une feuille contenant la valeur, à sa place dans l'arbre binaire de façon à ce que la structure d'arbre binaire de recherche soit toujours respectée.

a)

Dessiner l'arbre $B$ obtenu après exécution de l'instruction suivante:

inserer_dans_ABR(B, 16)

b)

Dessiner l'arbre binaire de recherche que l'on obtient, en partant de l'arbre vide, et en insérant les valeurs suivantes dans cet ordre: 5, 3, 7, 8, 4, 1, 9, 2 et 6.

7.

On veut écrire une fonction tri qui prend en argument un tableau de nombres T et qui renvoie un tableau trié en utilisant l'algorithme suivant:

on construit un arbre binaire de recherche en insérant, à partir d'un arbre vide, les éléments du tableau T;

on construit le tableau que l'on obtient en parcourant cet arbre binaire de recherche grâce à la fonction parcours de la partie A.

Écrire la fonction tri en Python, en utilisant cet algorithme:

def tri(T):

""" Trie le tableau de nombres T. """