Aller au contenu

ABR

On utilise dans tous les exercices l'implémentation des arbres binaires à l'aide d'une classe ArbreBinaire. On pourra utiliser sans justification supplémentaires les méthodes gauche, droit, etiquette, est_vide de la classe ArbreBinaire, ainsi que la méthode inserer de la classe ABR.

1
from ArbreBinaire import Noeud, ArbreBinaire, ABR

Question de cours

L'arbre binaire \(\mathcal{A}\) ci-dessous est-il un arbre binaire de recherche ? Justifier votre réponse à l'aide de deux arguments différents.

img

Le sous-arbre droit de \(\mathcal{A}\) n'est pas un arbre binaire de recherche. Il y a une étiquette d'un nœud du sous-arbre gauche de \(\mathcal{A}\) qui est supérieur à l'étiquette de la racine.

Tranche d'un ABR

  1. Écrire une fonction parcours_stocke_cles_entre qui prend en argument un ABR a, une liste l ainsi que deux entiers vmin et vmax et qui ajoute à la liste l les éléments e de a compris strictement entre vmin et vmax.

    On effectuera un parcours en profondeur infixe de l'arbre a.

    1
2
3
4
5
6
7
8
    def parcours_stocke_cles_entre(a, l, vmin, vmax):
    if a.est_vide():
        pass
    else:
        parcours_stocke_cles_entre(a.gauche(), l, vmin, vmax)
        if vmin < a.etiquette() < vmax:
            l.append(a.etiquette())
        parcours_stocke_cles_entre(a.droit(), l, vmin, vmax)

  2. Quel affichage produit le code suivant ?

    1
2
3
4
5
6
    a = ABR()
for e in [5, 7, 3, 4, 1, 2, 8, 4, 9]:
    a.inserer(e)
l = []
print(parcours_stocke_cles_entre(a, l, 3, 6))
print(l)

    None
[4, 4, 5]

    La ligne 6 affiche None, la ligne 7 affiche [4, 4, 5].

  3. On exécute à nouveau les deux dernières lignes du code précédent. Quel est l'affichage alors réalisé ?

    L'avant dernière ligne affiche None, la dernière ligne affiche [4, 4, 5, 4, 4, 5]

Arbre d'appel

On donne ci-dessous le code d'une fonction python m.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def m(a, s):
    """ ABR, int -> int | Nonetype """
    if a.est_vide():
        return None
    elif a.etiquette() <= s:
        if a.droit().est_vide():
            return None
        else:
            return m(a.droit(), s)
    else:
        f = m(a.gauche(), s)
        if f is None:
            return a.etiquette()
        else:
            return f

1
2
3
4
a = ABR()
for e in [1, 9, 5, 12, 4, 42, 3, 6, 8]:
    a.inserer(e)
print(a.to_latex())

[$1$ [,phantom] [$9$ [$5$ [$4$ [$3$ [,phantom] [,phantom]] [,phantom]] [$6$ [,phantom] [$8$ [,phantom] [,phantom]]]] [$12$ [,phantom] [$42$ [,phantom] [,phantom]]]]]

Dresser l’arbre d’appel de l’instruction m(A, 8) où l’arbre \(\mathcal{A}\) est l’arbre dont on a donné la représentation ci-dessous. En déduire la valeur renvoyée par m(A, 8).

img

m(A, 8) 
1
print(m(a, 8))

9