Insertion dans un ABR (1)

Un arbre binaire est implémenté par la classe Arbre donnée ci-dessous.
Les attributs fg et fd prennent pour valeurs des instances de la classe Arbre ou None.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Arbre:
    def __init__(self, etiquette):
        self.v = etiquette
        self.fg = None
        self.fd = None

def parcours(arbre, liste):
    if arbre != None:
        parcours(arbre.fg, liste)
        liste.append(arbre.v)
        parcours(arbre.fd, 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 insère un nœud d’étiquette cle en feuille de l’arbre implémenté par l’instance arbre selon la spécification indiquée et de façon 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 code 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

.128013witkcvN8o-)yl0bqp_.!P3(a;g=/m4rse97Sf,d 612:é5nuhA050N0H0d0y0c0n0G0O0f0n0y0G0G0B010d0c0r010406050G0W0D0D0y0F0m040K0j0n0W0?0j0V050C0}0 11130{0r04051j1c1m0C1j0{0N0c0g0+0-0/0;0-0V0A0W0y0A0H0k0r0m0d0X1a0O0X0c0A0X0n1O0X0d0_050$0p0n0H1v0.0:011N1P1R1P0d1X1Z1V0d0F1k1J0+160G0r0y0V0;0R011#1x010L0(0H0V0y0D0H1V1`1|211%241Z27290_0a0O0v0F0j0r0j0G0c190V0O0!1^0F0F0H0f2u1c2c0V1k0C1J2H1;1?1=1W0N2e1y0c0V262r1V1s1u0,1$2R2T0V0j2X1V0r2A1k2F2H2.0|1{2v2Z222%0F100n1V0y1M2A0L0;030s0s0f2(0H1R2$0j0k0Q3c0_0O0Q1c0y2/2=0`2;2d2@1%2_2{2}2 0H3101333537392U3c0k1 040O0R3i3k1|3m2F2Q013r0y2|1k2~0X303234360!3B2%3D0w3f0w3J2E3l0{3N3p0;3Q3S053U3W3x3Y3A2S3C3d0E3f0E3+1d3-3n2?1w3q0j2`3R3t3V3v3X3z3!3}3$3d0U3f0U432.3.2=3O3=4d3_3y3Z384j3b3d0P3f0P4p453/483;4a3s3T3u3w4x3|3a3D0J3f0J4G3L4r3o4J3P4L4c4N4e4P3{4i4S3d0i3f0i4X2G4Z472!4$4b3?3^4f3`4h4z4.0k0I3f0I4?3M4s3:4{4M3@4O4g4y3#4B3c0o0_0Q0o584^4t4%4}5f505h4A3D0Q0Q5m3h0C3j3,4Y465r4|4v4 4Q4-3~3c3F0Q3I5D3K4@5H5b4u4)4w4,525O0Q3(045(5p5W4#5Y5e4*5g4R5%405*425T5F5V4I4`5/4~4+515i5y4m5*4o5{445G5~2^5s5K625w530Q4D5*4F694q5-5 6e5Z5L5#643d0Q4U5*4W6n4H5a5.6r5:5!635x6w4:5*4=6B6b6D6q5J6s6g5?4k3c555*576O5}6Q6d6S6G6t6I530R5l046.5,6c496)615=5N6W0R5A6:5C5E6a6$4!6R5d6_5v6V5j0R3F7b6=6%6@765u5M5$6|5)0R3*6#59746(7h5;786{7a5^0R5`716o6?4K6^7i6u6J3E660R687B6C7r7g4(6*6U7w3D0R6k7W7e7P7E7t6H6h5O0R6y7*581n2,1c2X2K0N1?2P5b4y2W1t1k2+0H2-3l5|1k4y802d0c0N0;342F5y3t87896,5%202i0H8f7(6W6~3+7D010e0_3p826p220b3f8v8q0V0f0_0Y0F0p2A8A7f0;0^040S820{72852v8e018a2=7V8d888V8g6|8i288k8#8m7a1V5T0O8:0O8w1%8s040!0L8J7!018y3G8|4_220L0D0_342S2t34913O8M0x9b5b0p8M0G388{8R8?8L0_0M828=8B0_0#0c0q0W0#0d0H9f4#8M0l8O8R8Q2:3N8U8W1|3%8Z8l799O0O8j9Q7U3d5)3J8;9!9s8K019h0_9j0n9l9J9%0j0_0t9C5 0_0g9r9n019:040B9`9t049v9x9z9B9H9b9L0s8b3 9P8+9Rac9T8)9V7k5j5^9Z9#8:9{9)049+9-818q9}9=9ma10L0Aa09/0_9 8R9$8}0e8D040h1aa66oaz4sa9ab0k665ea98,3D4mah29aj6vaV8.3jaoap8qarat9?22axa=3q0_0L0NaD8}9}aG2.aI928@aLaN2T8Pa88!9M0V3D6kaXba8$5j4Da$8*7H53be5T9IavaSbgaU6ybfa(7I4Ubkbx53bv5{8q8^8`a^0;8 8=aR8}0V0L0_1{0F360W0F0GbI019dbX0V0_118HaPbr8}8M9qaH9{b#041R0G9AbX9E9GaQ9.86bt8X4/adbm5O4:bAae9W0k6Lana.9%8^0cau3Lb24tb$8G8Ib.aw0_0ub03lch5baK0_b6b)3L9{8Mb`45bM8Tb~9N3d6Ybwc6ak3D55c5c26WcI8/a-b/bQ11bTbVb^0_9ecDci04b%clb|b30;a@c$5Xa`aCc/9D9pa}c,3P0_b=b@c?4`9Eb8c$aTb 5kc1bh5y5lcOd86w6/ca9#cUb;0cb?cx2G9{c.c+c%0y0r0r26a|c 22bZdwa_c(ckdl8S3Odob*c`b:9_dz9o040ld2dpd4cG3c8o2~aYafdT8(a%cKa)5za+3GcTa1bRcXbWdLbYc!b!cjb(bXdGcyaAdvdp5bb,c_c%c}dDcz0_dOa7d3cFbc6w3FcJcP5j5RdZbldc5Pd(9!9{8^2A0dbU1bcm9%b:e2dPdH0OdRea3c9YdVbgaZ6w3(dbeGeCd(bqd`bs8faU0QameEbB5@eheV8nambEcc0_bHd/bKb!bP042S9jc*eyd~d;d/b:c)e38qd etbN8t1ZcZdNcB5Ge8eQd50QaWeUd#7If8eXfb6iaWe#8}bK8;bX0G0N0_029x0j0d0zfq0Wfsfufrft0Oe_0O0Hb?0O0W2Tez0Vb?1|0f1!2x0-2e1!8Fb(0O9x0cez0D0r0n0T290Vc~b{eyeA5ybefaeef-fef:6wbo5E8qfn3fa-fHfBdC0O0p2S0%2A2w1!2A0f0X0HbSgaayf*eOb}f6dS6xd7eKgkeJdXgk2Hf_9%f{d)8:fvfxgxftgz0zexggcEgieB0Qc9f/ejgIf=gLc9cScbaJ0_cee0c:040,dDcs4#9}020nftgV5.d?e:gEdF9;d=04dKd}c@8NgDdm9Ke95ycIgKgmcN9Uff5%cRa,d*e$e-cf2Gg!9@dBd@d/d_g{euc;g*4`0j8 djhma?8 2%0dhrb4cvaOf1f35Vf58#aU6.gldXhGgoc7hGgrgva-gRdIgTfKgbe`9%dyg@hee_d^g:e@hld/e|b1dhgYf1e6gfhjghhEd56}hHhL5AhKcL3dh^hNhPen9u0)hVb+0_hB3mhDbb7Vech0hI1 h|a)7belhPfla1h!hhh$hY2^h(h+cn9~hw3;8EdCf1c#irdAh-h)e5g`dEf,h~eDezeFhIeIh3f?3E9YgQhd228^389jhAiI5HiK3EeTiNeY7xgNeK7zikaoi2haixc{hfg-h;c`hidEgWa{i^hogTd.iu9/htfsi^cuaMhziGg_e7dQg}h~f9i+h46|a#iRej7Li;ildhe.hUiBg;ioiDc-iqe;g+04j1jeb-j6e~gXf0jeh/cCjhgG7Vf.jliS7Wi.hIf^hOembFi3i!jei8eNi|jUaah@bviehLbzjpi/bDh7iliWdAjzjDhnjCg.j0d|crdnaFi^b:fTi{i g^iCj isjLi5c`d1jg810C847.7 7:7|1c0d7?kt2N2I0y1Ykq0C7;8Q0!0$0(0G04.