Sujet NSI — Terminale — Métropole — Bac 2022

EXERCICE 1 (4 points) Cet exercice porte sur les arbres binaires de recherche, la programmation orientée objet et la récursivité. Dans cet exercice, la taille d’un arbre est le nombre de nœuds qu’il contient. Sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l’une des feuilles (nœuds sans sous-arbres). On convient que la hauteur d’un arbre ne contenant qu’un nœud vaut 1 et la hauteur de l’arbre vide vaut 0. 1. On considère l’arbre binaire représenté ci-dessous: Figure 1 a. Donner la taille de cet arbre. b. Donner la hauteur de cet arbre. c. Représenter sur la copie le sous-arbre droit du nœud de valeur 15. d. Justifier que l’arbre de la figure 1 est un arbre binaire de recherche. e. On insère la valeur 17 dans l’arbre de la figure 1 de telle sorte que 17 soit une nouvelle feuille de l’arbre et que le nouvel arbre obtenu soit encore un arbre binaire de recherche. Représenter sur la copie ce nouvel arbre. 2. On considère la classe Noeud définie de la façon suivante en Python : 1 class Noeud: 2 def __init__(self, g, v, d): 3 self.gauche = g 4 self.valeur = v 5 self.droit = d a. Parmi les trois instructions (A), (B) et (C) suivantes, écrire sur la copie la lettre correspondant à celle qui construit et stocke dans la variable abr l’arbre représenté ci-contre. (A) (B) (C) 22-NSIJ2ME1 Page : 2/14 b. Recopier et compléter la ligne 7 du code de la fonction ins ci-dessous qui prend en paramètres une valeur v et un arbre binaire de recherche abr et qui renvoie l’arbre obtenu suite à l’insertion de la valeur v dans l’arbre abr. Les lignes 8 et 9 permettent de ne pas insérer la valeur v si celle-ci est déjà présente dans abr. 1 def ins(v, abr): 2 if abr is None: 3 return Noeud(None, v, None) 4 if v > abr.valeur: 5 return 6 elif v < abr.valeur: 7 return 8 else: 9 return abr 3. La fonction nb_sup prend en paramètres une valeur v et un arbre binaire de recherche abr et renvoie le nombre de valeurs supérieures ou égales à la valeur v dans l’arbre abr. Le code de cette fonction nb_sup est donné ci-dessous : 1 def nb_sup(v, abr): 2 if abr is None: 3 return 0 4 else: 5 if abr.valeur >=