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 :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.1280130ldCy1,4ké/we!ibmc:_I35qaPr 7=9of.gt28;6sSh)(MpNuènv050d0n0K0z0p0c0P0C0s0c0z0P0P0E010K0p0V010406050P0X0r0r0z0B0f040Q0G0c0X0^0G0Z050l0 1113150}0V04051l1e1o0l1l0}0d0p0!0-0/0;0?0R0p0J0R0c1C0R0K0{050(0q0c0n1x0:0=011B1D1F1D0K1L1N1J0K0B1m0K0R0-180P0V0z0Z0?0L011P1z010H0*0n0Z0z0r0n1J1,1.1?1R1_1N1|1~0{0a0C0A0B0G0V0G0P0p1b0Z0C0$1*0B0B0n0s2j1e210Z1m0l1(2w1#1%1$1K0d230?1F0Z1{2g1J1u1w0.1Q2G0p2I0Z0G2M1J0V2p1m2u2w2!0~1-2k2O1@2T0B120c0{0C0g2t2(0|2%222*1R2,2.2:0L2?1.2^2u2F012}0z2/040C0w312v0}342{0?37390C0i3d332(353j2:0x3n3f3p3h360G2-382:0O3u2_2)1y2|3z2~3a0D3E3g3H3i3J3B3a0M3N3w3P3y3A3k0F3V2`3X3r040g0b3$3G2P3Y3K0g2=1f2@3v3%3/3)0g303@323_3.2+3R390g3c3 3e3F3q440{0g3m483o3`433Z4d3t4g414b4k3*3D4n4a3x3|3M4t3O3{4c3*3U4y3W4A4q0g3#4E4i3I4q0L3,4K424M3K0L3?2$1r2Y1e2M2z0d1%2E3x0s2U1 1m4!1n4Y4W2$4*0$2Z4F1@0j0{2{3n0C4u3(0s0{0W0G0n0X0d3n503/0`040t3u0C5g4 4z4`0{0$0H4~5a1@0H0r0{0u0u2R2i5u595j1R5c0T5z4_1R0q5c0P0n0c5n4g5p5B0{0h5o5A3i0{0%0p0y0X0%0K0n5E4L0?5c0S5e4Q350m2:5h5;5%4R0?0P0d0{02030w0F0N5|5~605}5 0U0k1(4+1*0Z0P1#0X2r560B0C2f0X6h0/231O54560d0I3-355_5:5;5g0e0B0k1O0X2I0C0H560*1N2l615 675X5Z1X1O0d1c0Z6B0I6L63626X5f6x5g5O0?5H0{5J5L5?350G0{6s5N5T365V0^5Y5!5$4g5i5F0?6:040E5S706^045W6{6Q6#6$6(016*046,5M2$6@726=7k760Z0{0J0z6e0R6}2!6 5(0172746~7e0j5204542I7c6x7e7g7i6.3x7m7P3(5l2d2i757z7B7X5@017F531c7w3^065=6@4{045m7!3q0H0{2R5J2p0B7S5b0{5D6?767N5K7j2@7e5c5R7D6@7q040.7*32870{5+6t3x5/3a6$4 817z6v046X8u640N0v6b0Y2p0C6m0.0k2l1.0,0c6X130q8B0q2R0)8B2m2p0s7v0B8U8f496@8s8o0C1{6i6A7`0!1.0K0C0P0z8/6d2r6k0n6W8w8v627K7-767/0p85327y7#8c8e7=7Q5{0c0K0N993X836-8q7#7R9j3q6_6O6|7}1@5c5,2!7,8$5h7E7^932v95359h9B4^7Y6;9r2|7r7t8X9f3/720o7C7x7E7G7I8Y9H7#9t8~9x6%6@9F9K719J9m4v9M7u9Y7e9l7o7z8c7_0n7{9+015C9~971N9~5*9$7d7.5V0+9=6@9#4n9%a7825I849~9@868b9:9O8a767Zaq9_7(6qa47 a14|a39.3Xa56~9wag7z7/5K5Jax5da67La804929P1@9*aC9Q9-9^967U0G7Wat9k0{9SaT1R7%7H7)aM9u3^afaPah6+ajaW1@al8gan7:7V0KakaYam7p7^6b9|9|aM80aZ9n8daBbe3xaE9va@9z78aaa;aO8$7Mai9ibi3Xa~2v7e8c0db2a,9,73bE776p57bcazbgab76bk3^1e4?0n2w2XbU4Z1v4#2z2C2x0z1MbX0l4!0}b+0%0)0+04.
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)