Exo bac C5.EB2

Cet exercice porte sur les arbres binaires de recherche

Dans cet exercice, les arbres binaires de recherche ne peuvent pas comporter plusieurs fois la même clé. De plus, un arbre binaire de recherche limité à un nœud a une hauteur de 1.

On considère l’arbre binaire de recherche représenté par la figure 1, où val représente un entier.

 

1.

a. Donner le nombre de feuilles de cet arbre et préciser leur valeur (étiquette).

b. Donner le sous arbre-gauche du nœud 23.

c. Donner la hauteur et la taille de l’arbre.

d. Donner les valeurs entières possibles de val pour cet arbre binaire de recherche.

 

On suppose, pour la suite de cet exercice, que val est égal à 16.

2.

a. Donner les valeurs d’affichage des nœuds dans le cas du parcours infixe de l’arbre.

b. Donner les valeurs d’affichage des nœuds dans le cas du parcours suffixe de l’arbre.

 

3. On considère la classe Noeud définie de la façon suivante en Python :

class noeud():
    def __init__(self, v):
        self.ag = None
        self.ad = None
        self.v = v
    def insere(self, v):
        n = self
        est_insere = False
        while not est_insere :
            if v == n.v:
                # Bloc 1
                est_insere = True
            elif v < n.v:
                # Bloc 2
                if n.ag != None:
                    n = n.ag
                else:
                    n.ag = noeud(v)
                    est_insere = True
            else:
                # Bloc 3
                if n.ad != None:
                    n = n.ad
                else:
                    n.ad = noeud(v)
                    est_insere = True
    def insere_tout(self, vals):
        for v in vals:
            self.insere(v)

a. Représenter l’arbre construit suite à l’exécution de l’instruction suivante :

racine = noeud(18)
racine.insere_tout([12, 13, 15, 16, 19, 21, 32, 23])

b. Écrire les deux instructions permettant de construire l’arbre de la figure 1. On rappelle que le nombre val est égal à 16.

c. On considère l’arbre tel qu’il est présenté sur la figure 1. Déterminer l’ordre d’exécution des blocs (repérés de 1 à 3) suite à l’application de la méthode insere(19) au nœud racine de cet arbre.

 

4. Écrire une méthode recherche(self, v) qui prend en argument un entier v et renvoie la valeur True si cet entier est une étiquette de l’arbre, False sinon.

Afficher la correction

1.a Cet arbre contient 4 feuilles qui ont respectivement pour valeur 12, val, 21 et 32.

1.b Le sous arbre-gauche du nœud 23 est :

1.c La hauteur de l'arbre est de 4 et sa taille est de 9.

1.d Les valeurs possibles pour val sont 16 et 17.

2.a Parcours infixe : 12, 13, 15, val = 16, 18, 19, 21, 23 et 32.

2.b Parcours suffixe : 12, 13, val = 16, 15, 21, 19, 32, 23 et 18.

3.a

3.b 

racine = Noeud(18)
racine.insere_tout([15, 13, 12, 16, 23, 19, 21, 32])

ou

racine = Noeud(18)
racine.insere_tout([23, 15, 32, 19, 16, 13, 21, 12])

3.c L’ordre d’exécution est : bloc 3 (car 19 > 18), bloc 2 (car 19 < 23) et bloc 1 (car 19 est déjà dans l’arbre).

4. 

    def recherche(self, v):
        if v == self.v:
            return True
        elif v < self.v and self.ag is not None:
            return self.ag.recherche(v)
        elif self.ad != None:
            return self.ad.recherche(v)
        return False