Insertion dans un ABR (4)

Un arbre binaire 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.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Noeud:
    """Classe représentant un noeud d'un arbre binaire"""
    def __init__(self, etiquette, gauche, droit):
        """Crée un noeud de valeur etiquette avec 
        gauche et droit comme fils."""
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit

def parcours(arbre, liste):
    """parcours récursivement l'arbre en ajoutant les étiquettes
    de ses noeuds à la liste passée en argument en ordre infixe."""
    if arbre != None:
        parcours(arbre.gauche, liste)
        liste.append(arbre.etiquette)
        parcours(arbre.droit, liste)
    return liste

La fonction récursive parcours renvoie la liste des étiquettes des nœuds de l’arbre implé- menté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.

Compléter le code de la fonction insere, qui prend en argument un arbre binaire de recherche arbre représenté ainsi et une étiquette cle, non présente dans l’arbre, et qui :

  • renvoie une nouvelle feuille d’étiquette cle s’il est vide ;
  • renvoie l’arbre après l’avoir modifiĂ© en insĂ©rant cle sinon ;
  • garantit que l’arbre ainsi complĂ©tĂ© soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci- dessous :

flowchart TD
    A(5) --- B(2)
    A --- C(7)
    B --- D( )
    B --- E(3)
    linkStyle 2 stroke-width:0px;
    style D opacity:0;
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(5-,_s3u:/S bqn=Ă©ve08im.tPNR69p2drg;ylckfao050N0z0F0W0C0S0m0s0T0S0W0m0m0w010F0C0L010406050m0o0D0D0W0O0R040r0X0S0o0=0X0v050q0|0~10120`0L04051i1b1l0q1i0`0N0C0y0*0,0.0:0,0v0P0o0W0P0z0j0L0R0F0e190s0e0C0P0e0S1N0e0F0^050#0t0S0z1u0-0/011M1O1Q1O0F1W1Y1U0F0O1j1I0*150m0L0W0v0:0M011!1w010V0%0z0v0W0D0z1U1_1{201$231Y26280^0a0s0G0O0X0L0X0m0C180v0s0Z1@0O0O0z0T2t1b2b0v1j0q1I2G1:1=1;1V0N2d1x0C0v252q1U1r1t0+1#2Q2S0v0X2W1U0L2z1j2E2G2-0{1`2u2Y212$0O0 0S1U0W1L2z0V0:030l0l0T2%0z1Q2#0X0j0g3b0^0s0g1b0W2.2;0_2:2c2?1$2^2`2|2~0z3001323436382T3b0j1~040s0M3h3j1{3l2E2P013q0W2{1j2}0e2 3133350Z3A2$3C0n3e0n3I2D3k0`3M3o0:3P3R053T3V3w3X3z2R3B3c0d3e0d3*1c3,3m2=1v3p0X2_3Q3s3U3u3W3y3Z3|3#3c0i3e0i422-3-2;3N3;4c3^3x3Y374i3a3c0J3e0J4o443.473:493r3S3t3v4w3{393C0b3e0b4F3K4q3n4I3O4K4b4M4d4O3`4h4R3c0B3e0B4W2F4Y462Z4#4a3=3@4e3_4g4y4-0j0K3e0K4=3L4r3/4`4L3?4N4f4x3!4A3b0A0^0g0A574@4s4$4|5e4 5g4z3C0g0g5l3g0q3i3+4X455q4{4u4~4P4,3}3b3E0g3H5C3J4?5G5a4t4(4v4+515N0g3%045%5o5V4!5X5d4)5f4Q5$3 5)415S5E5U4H4_5.4}4*505h5x4l5)4n5`435F5}2@5r5J615v520g4C5)4E684p5,5~6d5Y5K5!633c0g4T5)4V6m4G595-6q5/5Z625w6v4/5)4;6A6a6C6p5I6r6f5=4j3b545)566N5|6P6c6R6F6s6H520M5k046-5+6b486(605;5M6V0M5z6/5B5D692F1m2+1b2W2J0N1=2O5a4x2V1s1j2*0z2,3k5{1j4x7i2c0C0N0:332E5x3s7p7r6+5$1 2h0z7x6g7z2G5D6=0:0U0^0Z0V7k6o210c3e7O7I3O0V0^2R0m0z2z7T6$1$0@040h7$4Z5~0^100t7#717n4^217)0k7k0s7P3p0^0+0z7,7^7(0^0f0p7k0`7?5G7w017s2;3C3E5d8d6t6I3D7A277C8e7y6{1U5`7U7R3F0s8z833N0m0N0^018G7Y7!1Z0,1u1Z0N1{0)0S007:2z0s0t2R0$8U2w2z0T0e7!8$827?8a2/3M8k0l7t3c5(8j7q8r7E6V3%0s7B7D6U5i8?8v7%0:8D3e8z0s2z2*0x7Z0v0F0x0s1`0O0s8T0z0E898B8/8;0j5@8@8 6`5i3 8}8p9v5#6V9t937-21968y8z0I0!0X0o0O2S0s8R9l0s0D2%0C230x0E8G019o8b8.8^8f1{3C659u8_909-8o289B6u0j9.5S987}7U7K049X7|7~3:7/0O7;8*2-9~94010X0^0w0wa39 0T0^0H19a97j7U7)888+9p9*8:8g4B7vav8`5i4C9z9@9:9w3C6j3I9}9}a401a02z0F9O1a7?ab9G7 04am0z0o0N8B5a7)7+9(ac0v801Ya%4!7`aiac0UakaYana:4_a=aUaNa^ala{a+aW0:7)0fa?b5010T6}030*2z0W2t2v000o9Q0Va!0%a/atb42u9qax0j6x9/8l524TaE8qbz5Nbx9|98b00^377Za|7_0^as6nbs0sbu9,4.az9^8m4/bCbY526KaKaL8A9 7X7Na 7Ua-0481b9840:ae04020S0F0Qb@4sa6a8bN1$b`9nbS5WbK0=0u0o0!0Fao3KaNar7|8,ap4rbU0v3C6Xby8s5i54b#aG9Ccu8u3ib*b*aNb;9lc4b_0^c78-a,0^0P0W0o8)c05ab`ahb/cMa10v7Z7=cLbaa)cH3Oc2c#cmbac6c)b;cOcQ8%c)a~aacEa.cg72aq869%c$btav9r5mbXcx9_d6cwbE6Vd67G9JaLbJ04bLc}7@3Ncjbrd2bTd4bv5yd7dc5idudbct5x6}b)cCbIb:c+dlaNc/c85-7L2n2scS4!cUdQ7.cYc!dIc 7*c:dHc)dKdqc9040NdO0Fc^0^7{cWbab;b?dLa}d0aUclch9)7xd58i2}8/aB5x1~dze46v8ibHcDb,04aQaSdT2@d#dpc-d3d dt8?e2aA9;6v8|8~d88m5%cA3lbSco5x9teqb$5?9?bDdA6v9E7HcX0Wehc5afeQa5a`a!a$d^bOdZeY1$0D0C0^67d(a;d/eTaOa_am2Sd.04d:c`ajb2e=e#b6d`bRdqeC6v9.eFew6h4le7es3b9{eNd=7/e.dSd;b^c*dV8Je?a*e+dUePe}01c_3kaVfje%0^5RfpeZb8ekd}cndsbV3baJf5dw5xaDevfM6vaJ9FfjcFfgeSfic1flc,fFc%0^foelfZfrfB85e@e.fy043)fsb7d1f*f23bbxfLeKf|eIeGddbGfdfUfffYcTfXe_cX8If#c~acc(fsfVf@e-g84!f;6zf-e~04fDf0f`fHcp6Jdvf 0gb!fPgAb(fTf+fW04cVgbfef!dXggf(d!04f,f*a(glgLfxe(5)e?gt44eBgw5xcrf~e86Wg1f65$crgGd)gT3Kfw3NfhgXfZgdgOf%e!gqfkg^gfh1e^fvaNf;5_h3f^fEh6em8r9r6-gzg-hkf9aH3chkdfc{gSgIgKh9dGgNfngRh5dmgVf/gm4_f;6lhde g%f1g)hqdCg,fa6|g/fQ3DdCg?dMhuhG21g|hxgccZfmgkh2gUhZhCcigWh(baf;6MhKgsf_ch0q7m737h757e1b0F78i42M2H0W1Xi10q768a0Z0#0%0m04.