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

.1280137w4h)1(M5-,_s3u:/SC bqn=èé!ve08imI.tPN69p2drg;ylckfao050R0D0K0!0G0W0n0u0X0W0!0n0n0y010K0G0P010406050n0p0H0H0!0S0V040s0#0W0p0_0#0x050r101214160~0P04051m1f1p0r1m0~0R0G0C0.0:0=0@0:0x0T0p0!0T0D0k0P0V0K0e1d0u0e0G0T0e0W1R0e0K0|050)0v0W0D1y0;0?011Q1S1U1S0K1!1$1Y0K0S1n1M0.190n0P0!0x0@0Q011(1A010Z0+0D0x0!0H0D1Y1}1 241*271$2a2c0|0a0u0L0S0#0P0#0n0G1c0x0u0%1{0S0S0D0X2x1f2f0x1n0r1M2K1@1_1^1Z0R2h1B0G0x292u1Y1v1x0/1)2U2W0x0#2!1Y0P2D1n2I2K2;0 1~2y2$252*0S130W1Y0!1P2D0Z0@030m0m0X2+0D1U2)0#0k0g3f0|0u0g1f0!2=2^0}2@2g2`1*2|2~30320D340136383a3c2X3f0k22040u0Q3l3n1 3p2I2T013u0!2 1n310e333537390%3E2*3G0o3i0o3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0d3i0d3.1g3:3q2_1z3t0#2}3U3w3Y3y3!3C3%403)3g0j3i0j462;3;2^3R3^4g3|3B3$3b4m3e3g0N3i0N4s483=4b3@4d3v3W3x3z4A3 3d3G0b3i0b4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0F3i0F4!2J4$4a2%4)4e3_3{4i3}4k4C4;0k0O3i0O4_3P4v3?4~4P3`4R4j4B3(4E3f0E0|0g0E5b4{4w4*505i535k4D3G0g0g5p3k0r3m3/4#495u4 4y524T4:413f3I0g3L5G3N4`5K5e4x4,4z4/555R0g3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560g4G5-4I6c4t5:626h5$5O5(673g0g4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560Q5o046;5/6f4c6,645^5Q6Z0Q5D6?5F5H6d2J1q2/1f2!2N0R1_2S5e4B2Z1w1n2.0D2:3o5 1n4B7m2g0G0R0@372I5B3w7t7v6/5*232l0D7B6k7D2K5H6_0@0Y0|3s7o6s250c3i7R7M3S0X0|0M0#0D0p0R7W6*1*0{040q7o0~757r2y7A017w2^3G3I5h7^6x6M3H7E2b7G7_7C6 1Y5W0u8b0u7S1*7O040%0Z7*4%4}7U3J8k4|250Z0H0|372V2w378p3R7-0h8z5e0v7-0n3b8j7=8e0@7-0l7o8d7X0x0|0(0G0w0p0(0K0D8D4(7-0f7/7=7;2?3Q7 0m7x3g5,7~7u867I6Z3+0u7F7H6Y5m8=5~7X8n8c958d8K7X0n0R0|009d0i0A1M3a1{0x0n1@0p2F7%0S0u2t0p9q0:2h1%7#7%0R0J7:8z8.8:0k5{8?8~6~5m438|849J5)6Z9H927+0@9a3i968b0t0S0A1%0p2W0u0Z7%0+1$2z009g8V8X1:1%0R1d0x9$0J9d009C984v9E7{4o7z8@80564p9N2c9P6y0k693M9Y8b8L018F0|8H0W8J8,9U010#0|9Ba18l2{8T0_8W8Y8!7=8Qasau040y8Pak8S048UaC9@a0ar7sa78/a40k6n9I8^8 3G4Gab85a85RaZ8aaiakam04aoaq7n7XaIawaT8q3t0|0T0!9n0eaE2;aGay1*aIaKaFak0Y7Z047#2WaSa^a2aV9F6Ba!a+6Z4Xa)ad81bna.9Ya:8G8I8#4}a`bBaz8h2r2waLa_0|bab5bcbebgb448ax7@blaX6Obo875m4?bsa#9K3GbX5W8+bjaU7B9F6#bY8_5m58b$bpb@893m95bc0|8ibE1*94c23@0Z0|2V8H2D0Sc5018Bcda;a?cd8NbJasaN0/bR3Oak8%8)6rbT0ua31 5B6=b=a$6z5ob_bZczb|7?3R94a/cv5e9W049~0I9k0z2D0u9v0/0A2z1 0-0W00140vcV0v2V0*cV2A2D0Xb30Sc=cp5Ycvcx0x5B71cBb(6z5DcFb?c~cIakcPai0u299r9#ca0C1 0K0u0n319l0S9n0K9t0D9}9dbicq8-bVcy6z7}318.d5dz83acb%9Q5m5UcIdab 040Ga@3Ob6a}3@7P1$clb70@aI020W0K0UdXdTalbzapcdbDcN5;aA9=aDcj0|ctbSa|cwdxc}6z8=dBaVdD3f8{8}dHae5+dLda8cdNdPd)3RchbAd:bCavcdaNb0b2c_8obK040BbM3odS3Rbd7!1dercrd_du76dwb/aX0g9He2bt6l9Me7b`5B9Sb}ecbx7Xeid-ek25d/d|5!a b1c^d.eme#a~dO9k0Dcbd^048Ce/dU04coe^0feGcJc|68a6eO5*aaeRcG6zagbwecdN3b8He^d`5Jc{d~5BaZeNe8816mdFa*fa3fa-eVeWb~eYd,dQeHaHe.e(d;04epe,bbetewdRaMeB9ze^e`fH62dVeD7X8%8Pb,dvbkeJdy3fbnfpeS6zbrf9e46AebeXas8gfgfYas7-fjc`d|f36Nf5fq6lb#f;cC3fb*fyfe7X8geffMaseZfDcJ5ee%b-d*aN0RbH0Keggm0|evgu4(eAbfeCfif15Kg26!g4f.gHd4g90gb;fdfzey8EfCe-04a{go4wc0gsgUgWf%dY3Sc8e=e@e{ce0|fUgXe)e}dWg-f!8*9Dfm3g6;gIfvg~gLd13HcAgPa/ge8T0,f|g(f~gEeI869F70g e4hih2dI7|c h6eWbyanejfVe$fGg;fIgr0#bIghg(b9gyfWgBfSg^g/enfXe gE0r7q777l797i1f0K7chW2Q2L0!1#hT0r7a7;0%0)0+0n04.
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)