Insertion dans un ABR (1)

Un arbre binaire est implémenté par la classe Arbre donnée ci-dessous.
Les attributs fg et fd prennent pour valeurs des instances de la classe Arbre ou None.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Arbre:
    def __init__(self, etiquette):
        self.v = etiquette
        self.fg = None
        self.fd = None

def parcours(arbre, liste):
    if arbre != None:
        parcours(arbre.fg, liste)
        liste.append(arbre.v)
        parcours(arbre.fd, liste)
    return liste

La fonction récursive parcours renvoie la liste des étiquettes des nœuds de l’arbre implémenté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.

Compléter le code de la fonction insere qui insère un nœud d’étiquette cle en feuille de l’arbre implémenté par l’instance arbre selon la spécification indiquée et de façon que l’arbre ainsi complété soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci-dessous :

flowchart TD
    A(5) --- B(2)
    A --- C(7)
    B --- D( )
    B --- E(3)
    linkStyle 2 stroke-width:0px;
    style D opacity:0;
Compléter le code ci-dessous

###
# Testsbksl-nla = Arbre(5)bksl-nlinsere(a, 2)bksl-nlinsere(a, 7)bksl-nlinsere(a, 3)bksl-nlassert parcours(a, []) == [2, 3, 5, 7]bksl-nlinsere(a, 1)bksl-nlinsere(a, 4)bksl-nlinsere(a, 6)bksl-nlinsere(a, 8)bksl-nlassert parcours(a, []) == [1, 2, 3, 4, 5, 6, 7, 8]bksl-nlbksl-nl# Autres Testsbksl-nlb = Arbre(10)bksl-nlinsere(b, 2)bksl-nlinsere(b, 12)bksl-nlinsere(b, 1)bksl-nlinsere(b, 11)bksl-nlinsere(b, 13)bksl-nlinsere(b, 9)bksl-nlassert parcours(b, []) == [1, 2, 9, 10, 11, 12, 13]bksl-nlc = Arbre(10)bksl-nlinsere(c, 2)bksl-nlinsere(c, 12)bksl-nlinsere(c, 1)bksl-nlinsere(c, 11)bksl-nlinsere(c, 13)bksl-nlinsere(c, 9)bksl-nlinsere(c, 14)bksl-nlassert parcours(c, []) == [1, 2, 9, 10, 11, 12, 13, 14]bksl-nld = Arbre(10)bksl-nlinsere(d, 2)bksl-nlinsere(d, 12)bksl-nlinsere(d, 1)bksl-nlinsere(d, 11)bksl-nlinsere(d, 13)bksl-nlinsere(d, 9)bksl-nlinsere(d, 14)bksl-nlinsere(d, 0)bksl-nlassert parcours(d, []) == [0, 1, 2, 9, 10, 11, 12, 13, 14]bksl-nlbksl-nlbksl-nl 5/5
class Arbre:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette):bksl-nl self.v = etiquettebksl-nl self.fg = Nonebksl-nl self.fd = Nonebksl-nlbksl-nldef parcours(arbre, liste):bksl-nl if arbre != None:bksl-nl parcours(arbre.fg, liste)bksl-nl liste.append(arbre.v)bksl-nl parcours(arbre.fd, liste)bksl-nl return listebksl-nlbksl-nldef insere(arbre, cle):bksl-nl """ arbre est une instance de la classe Arbre qui implémentebksl-nl un arbre binaire de recherche.bksl-nl """bksl-nl if ...:bksl-nl if ...:bksl-nl insere(arbre.fg, cle)bksl-nl else:bksl-nl arbre.fg = Arbre(cle)bksl-nl else:bksl-nl if ...:bksl-nl insere(arbre.fd, cle)bksl-nl else:bksl-nl arbre.fd = Arbre(cle)bksl-nlbksl-nl# Testsbksl-nl...bksl-nlbksl-nlclass Arbre:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette):bksl-nl self.v = etiquettebksl-nl self.fg = Nonebksl-nl self.fd = Nonebksl-nlbksl-nldef parcours(arbre, liste):bksl-nl if arbre != None:bksl-nl parcours(arbre.fg, liste)bksl-nl liste.append(arbre.v)bksl-nl parcours(arbre.fd, liste)bksl-nl return listebksl-nlbksl-nldef insere(arbre, cle):bksl-nl """ arbre est une instance de la classe Arbre qui implémentebksl-nl un arbre binaire de recherche.bksl-nl """bksl-nl if cle < arbre.v:bksl-nl if arbre.fg is not None:bksl-nl insere(arbre.fg, cle)bksl-nl else:bksl-nl arbre.fg = Arbre(cle)bksl-nl else:bksl-nl if arbre.fd is not None:bksl-nl insere(arbre.fd, cle)bksl-nl else:bksl-nl arbre.fd = Arbre(cle)bksl-nlbksl-nlbksl-nl