Exercice 1 · Bac Numérique et Sciences Informatiques Métropole 2022 (sujet 2)

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:

a.

b.

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:

class Noeud:

def __init__(self, g, v, d):

self.gauche = g

self.valeur = v

self.droit = d a.

Parmi les trois instructions (A), (B) et (C) suivantes, déterminer celle qui construit et stocke dans la variable abr l'arbre représenté ci-contre:

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.

def ins(v, abr):

if abr is None:

return Noeud(None, v, None)

if v > abr.valeur:

return Noeud(abr.gauche, abr.valeur, ins(v, abr.droit))

elif v < abr.valeur:

return....................................

else:

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:

def nb_sup(v, abr):

if abr is None:

return 0

else:

if abr.valeur >= v:

return 1+nb_sup(v, abr.gauche)+nb_sup(v, abr.droit)

else:

return nb_sup(v, abr.gauche)+nb_sup(v, abr.droit) a.

On exécute l'instruction nb_sup(16, abr) dans laquelle abr est l'arbre initial de la figure 1. Déterminer le nombre d'appels à la fonction nb_sup.

b.

L'arbre passé en paramètre étant un arbre binaire de recherche, on peut améliorer la fonction nb_sup précédente afin de réduire ce nombre d'appels. Écrire le code modifié de cette fonction.