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

Python Console Session
>>> 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

.128013kg: r);Sé/N(q.èlo4y,6Ib=ac15ud3t2!M8_Pw7evp-fh09mniCs050E0P0G0z0Z0q0#0e0A0q0z0#0#0y010G0Z0R010406050#0D0X0X0z0f0t040i0r0q0D0_0r0Y050k101214160~0R04051m1f1p0k1m0~0E0Z0Q0.0:0=0@0:0Y0c0D0z0c0P0S0R0t0G0U1d0e0U0Z0c0U0q1R0U0G0|050)0x0q0P1y0;0?011Q1S1U1S0G1!1$1Y0G0f1n1M0.190#0R0z0Y0@0H011(1A010T0+0P0Y0z0X0P1Y1}1 241*271$2a2c0|0a0e0M0f0r0R0r0#0Z1c0Y0e0%1{0f0f0P0A2x1f2f0Y1n0k1M2K1@1_1^1Z0E2h1B0Z0Y292u1Y1v1x0/1)2U2W0Y0r2!1Y0R2D1n2I2K2;0 1~2y2$252*0f130q1Y0z1P2D0T0@030L0L0A2+0P1U2)0r0S0B3f0|0e0B1f0z2=2^0}2@2g2`1*2|2~30320P340136383a3c2X3f0S22040e0H3l3n1 3p2I2T013u0z2 1n310U333537390%3E2*3G0F3i0F3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0s3i0s3.1g3:3q2_1z3t0r2}3U3w3Y3y3!3C3%403)3g0C3i0C462;3;2^3R3^4g3|3B3$3b4m3e3g0v3i0v4s483=4b3@4d3v3W3x3z4A3 3d3G0O3i0O4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0K3i0K4!2J4$4a2%4)4e3_3{4i3}4k4C4;0S0W3i0W4_3P4v3?4~4P3`4R4j4B3(4E3f0V0|0B0V5b4{4w4*505i535k4D3G0B0B5p3k0k3m3/4#495u4 4y524T4:413f3I0B3L5G3N4`5K5e4x4,4z4/555R0B3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560B4G5-4I6c4t5:626h5$5O5(673g0B4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560H5o046;5/6f4c6,645^5Q6Z0H5D6?5F5H6d2J1q2/1f2!2N0E1_2S5e4B2Z1w1n2.0P2:3o5 1n4B7m2g0Z0E0@372I5B3w7t7v6/5*232l0P7B6k7D2K5H6_0@0b0|3s7o0e6s2{0A0|0l0r0P0D0E7o7T1*0{040d7o0~757r2y7A017w2^3G3I5h7;6x6M3H7E2b7G7=7C6 1Y5W0e877S7M017O040%0T7R7%0@0T0X0|372V2w377$8a7)0m8q6*1*0x7)0#3b8f7.8h017)0u8g8a0Y0|0(0Z0n0D0(0G0P8u4%4}7)0g7+7.7-2?3Q7{0L7x3g5,7`7u827I6Z3+0e7F7H6Y5m8*5~8a0N3i888~8S4|250#0E0|02030F0W0h96989a97990J0j1M3a1{0Y0#1@0D2F7Z0f0e2t0D9r0:2h1%7X7Z0E0o7,900e8$8(0S5{8+8?6~5m438;809L5)6Z9J8`8v0@938}8~870!0f0j1%0D2W0e0T7Z0+1$2z9b999h8M8O1:1%0E1d0Y9(0o9=9d9ca19D8C8#8,7?1 3G699K8-8@ab7 2c9R6y0Sac869!878D8x0|8z0q8B8!9W010r0|9Ca6ax8J048L8N8P8R7.89axaz040y8HaD8K0_aH9`a5aw7sa88%7@4F7zaZ8.5m4G9Paiae9M3G6n3Maoap8aar04atav7n8aaNaBaX913t0|0c0z9o0UaJ2;aL8T25aNaPaK8D0b7V047X2WaWa}4v9Ga#0S6Bad7|564Xa,81bv5Rbtanaoaq8y8A9E5ea bI5;0|0E2r2waQbc1*bebRb27Nbjblb948aCaY7B9H6Obu835m4?byaj7}b*5W8Zbob%829H6#b+a)3G58b/a.9S5mb|bDbbbW8bbN3ybV4w0T0|2V8z2D0fbL8U0|8tb$c8a_a{ck258Fcc5!7P1$cs7(0|8Wbn3O5Kbqaa6z6=b}afcIahbzb,5BcJ9VbS0@8|3Ja?cz9X9404a1c$9e0h0w9l0p2D0e9w0/0j2z1 0-0qa1140xc-0x2V0*c-2A2D0Ab80fd3b!5Jco9FaZ9H5Ca%b:6l5Dc1bA6Zdd7K7/3R9YcWao299s9%ch0Q1 0G0e0#319m0f9o0G9u0Pa0c(c%9ccD76a7b(br5Udec2akdRdicP6z7_c68 8a8c0Za|3Oc74wcxd72Jd+bJ950q0G0hcv4(cqbHd9d;04b0b^c8aEaG9_8QcY8E0|8X6rd9cG0Y5B8*318$b~6z8:8=dT7}5+853ma?9!bhcfd)d/bFasd|b13RbKd}bM04b5b7d.3J8DaN0IbfbabhbY1deJ8D7)eab#eBed5B9Jeha(cL3f9Oemdj5m0B9UerescXa^bGaue7eDeBcweGb6d6e_aAe7aEcg0Pcie78sf2d-f7cBdMdneZ6zace$df5*4pdWej3fame:e;d:4(8c3b8zfb7*fdcFdbdQa;fien6la+e+dX3fa;d!frfs4}d{e^eE4}e`e1d,e}eId_fT0|eO3ofO2{7W7Y7!fxcne{eF0/eT8rfcaKb@cEdOb`dQbtfEe,5BbxfIfn6Aeqdqetd$8K0,f=axeVfzf{a9ee6NdSg0gjfme(0Bb=fqe;eu04d(fZ25fQewdnd~e0f`aR8dbP0GgwbT0|eNgIbXf*bmfScte9gfbpfBcH6!gkfJ0Bc0g3goc5grfNf(8we@gzeLf1gQb3gF0rbQg;0@fUgDcT3Scf9lf5f5f-f904f;fx0ggTb_gh7^cJf fJ6;cNfj6 cRg)e=axfugbfxeWd8eYgVgi3H71cKa/3g70hhfF5RhBdmg*d#axgyf0d h4bOg@gHbga~f#gMg~bkf+7#g_e804f.fVe|h6hZ8Vfz0k7q777l797i1f0G7ch?2Q2L0z1#h:0k7a7-0%0)0+0#04.
Solution
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)