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

.128013fdq6nmi7é4=3y_ 9pu08C!ts5M/vè1b(P)l;goIw-ah:rS2cekN,.050c0X0x0Q0h0J0y0p0W0J0Q0y0y0l010x0h0r010406050y0s0g0g0Q0T0n040U0M0J0s0_0M0f050B101214160~0r04051m1f1p0B1m0~0c0h0C0.0:0=0@0:0f0L0s0Q0L0X0P0r0n0x0R1d0p0R0h0L0R0J1R0R0x0|050)0F0J0X1y0;0?011Q1S1U1S0x1!1$1Y0x0T1n1M0.190y0r0Q0f0@0V011(1A010b0+0X0f0Q0g0X1Y1}1 241*271$2a2c0|0a0p0H0T0M0r0M0y0h1c0f0p0%1{0T0T0X0W2x1f2f0f1n0B1M2K1@1_1^1Z0c2h1B0h0f292u1Y1v1x0/1)2U2W0f0M2!1Y0r2D1n2I2K2;0 1~2y2$252*0T130J1Y0Q1P2D0b0@030o0o0W2+0X1U2)0M0P0E3f0|0p0E1f0Q2=2^0}2@2g2`1*2|2~30320X340136383a3c2X3f0P22040p0V3l3n1 3p2I2T013u0Q2 1n310R333537390%3E2*3G0m3i0m3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0k3i0k3.1g3:3q2_1z3t0M2}3U3w3Y3y3!3C3%403)3g0z3i0z462;3;2^3R3^4g3|3B3$3b4m3e3g0e3i0e4s483=4b3@4d3v3W3x3z4A3 3d3G0i3i0i4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0u3i0u4!2J4$4a2%4)4e3_3{4i3}4k4C4;0P0q3i0q4_3P4v3?4~4P3`4R4j4B3(4E3f0t0|0E0t5b4{4w4*505i535k4D3G0E0E5p3k0B3m3/4#495u4 4y524T4:413f3I0E3L5G3N4`5K5e4x4,4z4/555R0E3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560E4G5-4I6c4t5:626h5$5O5(673g0E4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560V5o046;5/6f4c6,645^5Q6Z0V5D6?5F5H6d2J1q2/1f2!2N0c1_2S5e4B2Z1w1n2.0X2:3o5 1n4B7m2g0h0c0@372I5B3w7t7v6/5*232l0X7B6k7D2K5H6_0@0Y0|3s7o6s250O3i7R7M3S0W0|0Z0M0X0s0c7W6*1*0{040S7o0~757r2y7A017w2^3G3I5h7^6x6M3H7E2b7G7_7C6 1Y5W0p8b0p7S1*7O040%0b7*4%4}7U3J8k4|250b0g0|372V2w378p3R7-0G8z5e0F7-0y3b8j7=8e0@7-0!7o8d7X0f0|0(0h0d0s0(0x0X8D4(7-0I7/7=7;2?3Q7 0o7x3g5,7~7u867I6Z3+0p7F7H6Y5m8=5~7X8n8c958d8K7X0y0c0|02030m0q0K9d9f9h9e9g0A0j1M3a1{0f0y1@0s2F7%0T0p2t0s9y0:2h1%7#7%0c0#7:8z8.8:0P5{8?8~6~5m438|849R5)6Z9P927+0@9a3i968b0v0T0j1%0s2W0p0b7%0+1$2z9i9g9o8V8X1:1%0c1d0f9.0#9{9k9ja79K984v9M7{4o7z8@80564p9V2c9X6y0P693M9*8b8L018F0|8H0J8J8,9$010M0|9Jac8l2{8T0_8W8Y8!7=8QaDaF040l8Pav8S048UaNa0abaC7sai8/af0P6n9Q8^8 3G4Gam85aj5Ra.8aatavax04azaB7n7XaTaHa(8q3t0|0L0Q9v0RaP2;aRaJ1*aTaVaQav0Y7Z047#2Wa%b3ada*9N6Ba/a_6Z4Xa@ao81bya|9*a~8G8I8#4}b5bMaK8h2r2waWb40|blbgbnbpbrbf48aI7@bwa,6Obz875m4?bDa:9S3Gb,5W8+bua)7B9N6#b-8_5m58b;bAc2893m95bn0|8ibP1*94cd3@0b0|2V8H2D0Tcg018Bcoa b1co8NbUaDaY0/b$3Oav8%8)6rb(0pae1 5B6=c0a;6z5oc4b.cKc77?3R94a}cG5e9(04a7c$9l0K0N9s0D2D0p9D0/0j2z1 0-0Ja7140Fc-0F2V0*c-2A2D0Wbe0Td3cA5YcGcI0f5B71cMb?6z5DcQc1dccTavc!at0p299z9-cl0C1 0x0p0y319t0T9v0x9B0Xa6c(c%9jbtcB8-b*cJ6z7}318.djdP83anb=9Y5m5UcTdoca040hb23Obhb83@7P1$cwbi0@aT020J0x0Kd;d-awbKaAcobOcY5;aL9~aOcu0|cEb%b7cHdNdb6z8=dRa*dT3f8{8}dXap5+d#do8cd%d)d|3RcsbLe3bNaGcoaYbbbdd78obV040wbX3od,3Rbo7!1deHcCe9dK76dMb}a,0E9PeibE6l9Uenc55B9!c8esbI7Xeye0eA25e2ec5!babcd6e1eCe^b9d(9s0Xcme8048Cf2d.04czf80IeWcUda68ahe(5*ale+cR6zarbHesd%3b8Hf8ea5Jd9ee5Ba.e%eo816mdVa^fq3fa{e/e:c9e=d d*eXaSf1e{e404eFe bmeJeMd+aXeR9Hf8fafX62d/eT7X8%8Pb`dLbveZdO3fbyfFe,6zbCfpek6Aere;aD8gfwf=aD7-fzd8ecfj6NflfG6lb:g4cN3fb^fOfu7X8gevf$aDe?fTcU5ee`b{d}aY0cbS0xewgC0|eLgK4(eQbqeSfyfh5Kgi6!gkg1gXdigp0Eb ftfPeO8EfSf004b6gE4wcbgIg.g:f`d=3Scjf5f7fbcp0|f.g;e|fdd:h0f@8*9LfC3g6;gYfLheg#df3HcLg)a}gu8T0,gcg{gegUeY869N70hfekhyhidY7|ddhme:bJayezf/e_fWh4fYgH0MbTgxg{bkgOf:gRf,h8h2eDf;ffgU0B7q777l797i1f0x7ch:2Q2L0Q1#h-0B7a7;0%0)0+0y04.
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)