Insertion dans un ABR (2)

Un arbre binaire de recherche est soit vide, représenté en Python par la valeur None, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance de la classe Noeud donnée ci-dessous.

On considère ici que les étiquettes des nœuds sont des entiers et que les arbres binaires de recherche considérés ne contiennent pas de doublons.

Exemple d'utilisation

🐍 Console Python

>>> arbre = Noeud(7)
>>> for cle in (3, 9, 1, 6):
        arbre.inserer(cle)
>>> arbre.gauche.etiquette
3
>>> arbre.droit.etiquette
9
>>> arbre.gauche.gauche.etiquette
1
>>> arbre.gauche.droit.etiquette
6

Exercice

Compléter le script ci-dessous :

###

Lancer # Testsbksl-nlbksl-nlarbre = Noeud(7)bksl-nlfor cle in (3, 9, 1, 6):bksl-nl arbre.inserer(cle)bksl-nlassert arbre.gauche.etiquette == 3bksl-nlassert arbre.droit.etiquette == 9bksl-nlassert arbre.gauche.gauche.etiquette == 1bksl-nlassert arbre.gauche.droit.etiquette == 6bksl-nlbksl-nl# Autres testsbksl-nlbksl-nlarbre = Noeud(2)bksl-nlfor cle in (3, 9, 1, 6):bksl-nl arbre.inserer(cle)bksl-nlassert arbre.gauche.etiquette == 1bksl-nlassert arbre.droit.etiquette == 3bksl-nlassert arbre.droit.droit.etiquette == 9bksl-nlassert arbre.droit.droit.gauche.etiquette == 6bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

class Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette):bksl-nl '''Méthode constructeur pour la classe Noeud.bksl-nl Crée une feuille d'étiquette donnée.'''bksl-nl self.etiquette = etiquettebksl-nl self.gauche = Nonebksl-nl self.droit = Nonebksl-nlbksl-nl def inserer(self, cle):bksl-nl '''Insère la clé dans l'arbre binaire de recherchebksl-nl en préservant sa structure.'''bksl-nl if cle < self.etiquette:bksl-nl if self.gauche != None:bksl-nl ...bksl-nl else:bksl-nl self.gauche = ... bksl-nl else:bksl-nl ...bksl-nl ...bksl-nl else:bksl-nl ... = Noeud(cle)bksl-nlbksl-nl# Testsbksl-nlbksl-nlarbre = Noeud(7)bksl-nlfor cle in (3, 9, 1, 6):bksl-nl arbre.inserer(cle)bksl-nlassert arbre.gauche.etiquette == 3bksl-nlassert arbre.droit.etiquette == 9bksl-nlassert arbre.gauche.gauche.etiquette == 1bksl-nlassert arbre.gauche.droit.etiquette == 6bksl-nlbksl-nlclass Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette):bksl-nl '''Méthode constructeur pour la classe Noeud.bksl-nl Crée une feuille d'étiquette donnée.'''bksl-nl self.etiquette = etiquettebksl-nl self.gauche = Nonebksl-nl self.droit = Nonebksl-nlbksl-nl def inserer(self, cle):bksl-nl '''Insère la clé dans l'arbre binaire de recherchebksl-nl en préservant sa structure.'''bksl-nl if cle < self.etiquette:bksl-nl if self.gauche != None:bksl-nl self.gauche.inserer(cle)bksl-nl else:bksl-nl self.gauche = Noeud(cle) bksl-nl else:bksl-nl if self.droit != None:bksl-nl self.droit.inserer(cle)bksl-nl else:bksl-nl self.droit = Noeud(cle)bksl-nlbksl-nl

---

---

Solution

🐍 Script Python

class Noeud:
    def __init__(self, etiquette):
        '''Méthode constructeur pour la classe Noeud.
        Crée une feuille d'étiquette donnée.'''
        self.etiquette = etiquette
        self.gauche = None
        self.droit = None

    def inserer(self, cle):
        '''Insère la clé dans l'arbre binaire de recherche
        en préservant sa structure.'''
        if cle < self.etiquette:
            if self.gauche != None:
                self.gauche.inserer(cle)
            else:
                self.gauche = Noeud(cle) 
        else:
            if self.droit != None:
                self.droit.inserer(cle)
            else:
                self.droit = Noeud(cle)