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"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
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

.128013f06S:d=4yr./èNopg2mcb1!w937Cve l,8P5)tikné;Iua(M_shq050g0E0M0U0N0G0Y0F0u0G0U0Y0Y0h010M0N0q010406050Y0T0t0t0U0k0j040e0p0G0T0^0p0P050m0 1113150}0q04051l1e1o0m1l0}0g0N0D0-0/0;0?0Z0N0r0Z0G1C0Z0M0{050(0v0G0E1x0:0=011B1D1F1D0M1L1N1J0M0k1m0M0Z0-180Y0q0U0P0?0s011P1z010b0*0E0P0U0t0E1J1,1.1?1R1_1N1|1~0{0a0F0J0k0p0q0p0Y0N1b0P0F0$1*0k0k0E0u2j1e210P1m0m1(2w1#1%1$1K0g230?1F0P1{2g1J1u1w0.1Q2G0N2I0P0p2M1J0q2p1m2u2w2!0~1-2k2O1@2T0k120G0{0F0w2t2(0|2%222*1R2,2.2:0s2?1.2^2u2F012}0U2/040F0A312v0}342{0?37390F0i3d332(353j2:0K3n3f3p3h360p2-382:0d3u2_2)1y2|3z2~3a0B3E3g3H3i3J3B3a0I3N3w3P3y3A3k0z3V2`3X3r040w0c3$3G2P3Y3K0w2=1f2@3v3%3/3)0w303@323_3.2+3R390w3c3 3e3F3q440{0w3m483o3`433Z4d3t4g414b4k3*3D4n4a3x3|3M4t3O3{4c3*3U4y3W4A4q0w3#4E4i3I4q0s3,4K424M3K0s3?2$1r2Y1e2M2z0g1%2E3x0u2U1 1m4!1n4Y4W2$4*0$2Z4F1@0O0{2{3n4u3X0y2:4~4z2+0u0{0o0p0E0T0g534_1R0`040f3u0F5k0F4 3/4{040$0b5d4L0?513a5t4R0?0b0t0{0X0X2R2i5E5y355g0V5J3x0v5g0Y0E0G5s4g5n1@5g0H3n5m542|0{0%0N0!0T0%0M0E5N3X5g0L5i4Q355w5l5{5m5V5$0?0Y0g0{02030A0z0R64666865670W0Q1(4+1*0P0Y1#0T2r5a0k0F2f0T6p0/231O585a0g0l3-35612:5|5k0C0k0Q1O0T2I0F0b5a0*1N2l69676f5*5,1X1O0g1c0P6J0l6T6b6a6)5j6F5#5e0?5P0{5R5T5:3/0p0{6A5~6:365(0^5+5-5/4g6/5u016{040h5!5W5%045)736Y6-6F7e6;5Q5S5U2$5 796|6_2+0{0r0U6m0Z752!775z7t7b7d7s0O5604582I7k5|7m016=046@7q2@7R7a6}7r6 0P0{0g2d2i7I6 7a7c767R7K571c7C3^065{7;7(0E7W327R5`7v2|0b0{2R5R2p0k830?5L8b7S7o6^6~785Y7,787%040.7^807s5=5@2!4o3x5`6.8e6D046)8D6c0R0S6j0n2p0F6u0.0Q2l1.0,0G6)130v8K0v2R0)8K2m2p0u7B0k8%8q497s8B6.0F1{6q6I880D1.0M0F0Y0U8{6l2r6s0E6(8F8E6a7P7{7J867 2v7E3q4|1N8l7F7a020G0M0R9h357T7V8e7Z8e8n7h6X5.8e5g8u3^8/986 5p0N9b5x7s9q7p9s7u8i7F8n7y7A8+9J7-0{0x7/7D7;7L7N9U7R9A979D5k7R9L8h7#789t9P9e049S8*9N047!7X7s8n870E899z0{5M9@4v9f9(8s0{0L9+7l997g0+ab6 9*4n9,ag6 9/9I7Y9O9;9Q7x7z9{7:7s7.9oa97M595ba504a7av9^8paIae767`8zah5S5RaI9B40ao9d3x9G9Ia!3Xar9|9~8r7$7(7*0MaD3X7a9Ya=5o9$7@aWaf9D9.8gasaBau9 a.5qa:a+9u866ja3a3aIaKb58maaaOa~9E785paUak8j0{aX3eaZbm7Fa*a8a?b4a-bib70p7+aA9W7HbHbD6xaHbz3/8dbO7w8o9gbR5fad3E0m4?0E2w2Xb#4Z1v4#2z2C2x0U1Mb(0m4!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)