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

.128013Mnur!9w6cs _1pk(d3tv0oé2=il:,è;7e8qfSb4/-.gy5mCPh)aIN050r0H0t0Z0A0B0k0l0j0B0Z0k0k0z010t0A0o010406050k0d0U0U0Z0e0S040L0w0B0d0_0w0c050O101214160~0o04051m1f1p0O1m0~0r0A0u0.0:0=0@0:0c0R0d0Z0R0H0P0o0S0t0X1d0l0X0A0R0X0B1R0X0t0|050)0M0B0H1y0;0?011Q1S1U1S0t1!1$1Y0t0e1n1M0.190k0o0Z0c0@0y011(1A010K0+0H0c0Z0U0H1Y1}1 241*271$2a2c0|0a0l0W0e0w0o0w0k0A1c0c0l0%1{0e0e0H0j2x1f2f0c1n0O1M2K1@1_1^1Z0r2h1B0A0c292u1Y1v1x0/1)2U2W0c0w2!1Y0o2D1n2I2K2;0 1~2y2$252*0e130B1Y0Z1P2D0K0@030m0m0j2+0H1U2)0w0P0n3f0|0l0n1f0Z2=2^0}2@2g2`1*2|2~30320H340136383a3c2X3f0P22040l0y3l3n1 3p2I2T013u0Z2 1n310X333537390%3E2*3G0s3i0s3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0N3i0N3.1g3:3q2_1z3t0w2}3U3w3Y3y3!3C3%403)3g0T3i0T462;3;2^3R3^4g3|3B3$3b4m3e3g0i3i0i4s483=4b3@4d3v3W3x3z4A3 3d3G0G3i0G4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0I3i0I4!2J4$4a2%4)4e3_3{4i3}4k4C4;0P0g3i0g4_3P4v3?4~4P3`4R4j4B3(4E3f0v0|0n0v5b4{4w4*505i535k4D3G0n0n5p3k0O3m3/4#495u4 4y524T4:413f3I0n3L5G3N4`5K5e4x4,4z4/555R0n3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560n4G5-4I6c4t5:626h5$5O5(673g0n4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560y5o046;5/6f4c6,645^5Q6Z0y5D6?5F5H6d2J1q2/1f2!2N0r1_2S5e4B2Z1w1n2.0H2:3o5 1n4B7m2g0A0r0@372I5B3w7t7v6/5*232l0H7B6k7D2K5H6_0@0p0|3s7o6s250h3i7R7M3S0j0|0#0w0H0d0r7W6*1*0{040C7o0~757r2y7A017w2^3G3I5h7^6x6M3H7E2b7G7_7C6 1Y5W0l8b0l7S1*7O040%0K7*4%4}7U3J8k4|250K0U0|372V2w378p3R7-0q8z5e0M7-0k3b8j7=8e0@7-0D7o8d7X0c0|0(0A0J0d0(0t0H8D4(7-0Y7/7=7;2?3Q7 0m7x3g5,7~7u867I6Z3+0l7F7H6Y5m8=5~7X8n8c958d8K7X0k0r0|009d0b0x1M3a1{0c0k1@0d2F7%0e0l2t0d9q0:2h1%7#7%0r0Q7:8z8.8:0P5{8?8~6~5m438|849J5)6Z9H927+0@9a3i968b0V0e0x1%0d2W0l0K7%0+1$2z009g8V8X1:1%0r1d0c9$0Q9d009C984v9E7{4o7z8@80564p9N2c9P6y0P693M9Y8b8L018F0|8H0B8J8,9U010w0|9Ba18l2{8T0_8W8Y8!7=8Qasau040z8Pak8S048UaC9@a0ar7sa78/a40P6n9I8^8 3G4Gab85a85RaZ8aaiakam04aoaq7n7XaIawaT8q3t0|0R0Z9n0XaE2;aGay1*aIaKaFak0p7Z047#2WaSa^a2aV9F6Ba!a+6Z4Xa)ad81bna.9Ya:8G8I8#4}a`bBaz8h2r2waLa_0|bab5bcbebgb448ax7@blaX6Obo875m4?bsa#9K3GbX5W8+bjaU7B9F6#bY8_5m58b$bpb@893m95bc0|8ibE1*94c23@0K0|2V8H2D0ec5018Bcda;a?cd8NbJasaN0/bR3Oak8%8)6rbT0la31 5B6=b=a$6z5ob_bZczb|7?3R94a/cv5e9W049~0!9k0E2D0l9v0/0x2z1 0-0B00140McV0M2V0*cV2A2D0jb30ec=cp5Ycvcx0c5B71cBb(6z5DcFb?c~cIakcPai0l299r9#ca0u1 0t0l0k319l0e9n0t9t0H9}9dbicq8-bVcy6z7}318.d5dz83acb%9Q5m5UcIdab 040Aa@3Ob6a}3@7P1$clb70@aI020B0t0FdXdTalbzapcdbDcN5;aA9=aDcj0|ctbSa|cwdxc}6z8=dBaVdD3f8{8}dHae5+dLda8cdNdPd)3RchbAd:bCavcdaNb0b2c_8obK040fbM3odS3Rbd7!1dercrd_du76dwb/aX0n9He2bt6l9Me7b`5B9Sb}ecbx7Xeid-ek25d/d|5!a b1c^d.eme#a~dO9k0Hcbd^048Ce/dU04coe^0YeGcJc|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*aN0rbH0teggm0|evgu4(eAbfeCfif15Kg26!g4f.gHd4g90nb;fdfzey8EfCe-04a{go4wc0gsgUgWf%dY3Sc8e=e@e{ce0|fUgXe)e}dWg-f!8*9Dfm3g6;gIfvg~gLd13HcAgPa/ge8T0,f|g(f~gEeI869F70g e4hih2dI7|c h6eWbyanejfVe$fGg;fIgr0wbIghg(b9gyfWgBfSg^g/enfXe gE0O7q777l797i1f0t7chW2Q2L0Z1#hT0O7a7;0%0)0+0k04.

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)