Exercice 3 · Bac Numérique et Sciences Informatiques Sujets zéro et spécimens sujet 2023 (sujet 2)

Exercice 3 (4 points)

Cet exercice est consacré aux arbres binaires de recherche et à la notion d'objet.

1. Voici la définition d'une classe nommée ArbreBinaire, en Python:

a.

En utilisant la classe définie ci-dessus, donner un exemple d'attribut, puis un exemple de méthode.

b.

Après avoir défini la classe ArbreBinaire, on exécute les instructions Python suivantes:

r = ArbreBinaire(15)

r.insert_gauche(6)

r.insert_droit(18)

a = r.get_valeur()

b = r.get_gauche()

c = b.get_valeur()

Donner les valeurs associées aux variables a et c après l'exécution de ce code.

a =

c =

On utilise maintenant la classe ArbreBinaire pour implémenter un arbre binaire de recherche.

On utilisera la définition suivante: un arbre binaire de recherche est un arbre binaire, dans lequel:

on peut comparer les valeurs des nœuds: ce sont par exemple des nombres entiers, ou des lettres de l'alphabet.

si x est un nœud de cet arbre et y est un nœud du sous-arbre gauche de x, alors il faut que y.valeur <= x.valeur.

si x est un nœud de cet arbre et y est un nœud du sous-arbre droit de x, alors il faut que y.valeur => x.valeur.

2.

On exécute le code Python suivant. Représenter graphiquement l'arbre ainsi obtenu.

racine_r = ArbreBinaire(15)

racine_r.insert_gauche(6)

racine_r.insert_droit(18)

r_6 = racine_r.get_gauche()

r_6.insert_gauche(3)

r_6.insert_droit(7)

r_18 = racine_r.get_droit()

r_18.insert_gauche(17)

r_18.insert_droit(20)

r_3 = r_6.get_gauche()

r_3.insert_gauche(2)

3.

On a représenté sur la figure 1 ci-dessous un arbre. Justifier qu'il ne s'agit pas d'un arbre binaire de recherche. Redessiner cet arbre sur votre copie en conservant l'ensemble des valeurs {2,3,5,10,11,12,13} pour les nœuds afin qu'il devienne un arbre binaire de recherche.

4.

On considère qu'on a implémenté un objet ArbreBinaire nommé A représenté sur la figure 2.

On définit la fonction parcours_infixe suivante, qui prend en paramètre un objet ArbreBinaire T et un second paramètre parcours de type liste.

Numéro de lignes

Fonction parcours_infixe

1

2

3

4

5

6

7

def parcours_infixe(T, parcours):

""" Affiche la liste des valeurs de l'arbre """

if T is not None:

parcours_infixe(T.get_gauche(), parcours)

parcours.append(T.get_valeur())

parcours_infixe(T.get_droit(), parcours)

return parcours

Donner la liste renvoyée par l'appel suivant: parcours_infixe(A, [ ]).