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

.128013lA9( _4:;=vm26!-uS8w.s3/fr7gebhpPicN0Ă©5qa,onkyd1)t050V0D0Y0P0I0b0w0f0J0b0P0w0w0k010Y0I0G010406050w0r0m0m0P0A0U040s0R0b0r0?0R0S050y0}0 11130{0G04051j1c1m0y1j0{0V0I0l0+0-0/0;0-0S0C0r0P0C0D0q0G0U0Y0F1a0f0F0I0C0F0b1O0F0Y0_050$0E0b0D1v0.0:011N1P1R1P0Y1X1Z1V0Y0A1k1J0+160w0G0P0S0;0n011#1x010z0(0D0S0P0m0D1V1`1|211%241Z27290_0a0f0H0A0R0G0R0w0I190S0f0!1^0A0A0D0J2u1c2c0S1k0y1J2H1;1?1=1W0V2e1y0I0S262r1V1s1u0,1$2R2T0S0R2X1V0G2A1k2F2H2.0|1{2v2Z222%0A100b1V0P1M2A0z0;030g0g0J2(0D1R2$0R0q0W3c0_0f0W1c0P2/2=0`2;2d2@1%2_2{2}2 0D3101333537392U3c0q1 040f0n3i3k1|3m2F2Q013r0P2|1k2~0F303234360!3B2%3D0x3f0x3J2E3l0{3N3p0;3Q3S053U3W3x3Y3A2S3C3d0h3f0h3+1d3-3n2?1w3q0R2`3R3t3V3v3X3z3!3}3$3d0N3f0N432.3.2=3O3=4d3_3y3Z384j3b3d0o3f0o4p453/483;4a3s3T3u3w4x3|3a3D0B3f0B4G3L4r3o4J3P4L4c4N4e4P3{4i4S3d0t3f0t4X2G4Z472!4$4b3?3^4f3`4h4z4.0q0d3f0d4?3M4s3:4{4M3@4O4g4y3#4B3c0L0_0W0L584^4t4%4}5f505h4A3D0W0W5m3h0y3j3,4Y465r4|4v4 4Q4-3~3c3F0W3I5D3K4@5H5b4u4)4w4,525O0W3(045(5p5W4#5Y5e4*5g4R5%405*425T5F5V4I4`5/4~4+515i5y4m5*4o5{445G5~2^5s5K625w530W4D5*4F694q5-5 6e5Z5L5#643d0W4U5*4W6n4H5a5.6r5:5!635x6w4:5*4=6B6b6D6q5J6s6g5?4k3c555*576O5}6Q6d6S6G6t6I530n5l046.5,6c496)615=5N6W0n5A6:5C5E6a6$4!6R5d6_5v6V5j0n3F7b6=6%6@765u5M5$6|5)0n3*6#59746(7h5;786{7a5^0n5`716o6?4K6^7i6u6J3E660n687B6C7r7g4(6*6U7w3D0n6k7W7e7P7E7t6H6h5O0n6y7*581n2,1c2X2K0V1?2P5b4y2W1t1k2+0D2-3l5|1k4y802d0I0V0;342F5y3t87896,5%202i0D8f7(6W6~3+7D010T0_3p826p220u3f8v8q0S0J0_0c0A0E2A8A7f0;0^040i820{72852v8e018a2=7V8d888V8g6|8i288k8#8m7a1V5T0f8:0f8w1%8s040!0z8J7!018y3G8|4_220z0m0_342S2t34913O8M0e9b5b0E8M0w388{8R8?8L0_0Q828=8B0_0#0I0O0r0#0Y0D9f4#8M0X8O8R8Q2:3N8U8W1|3%8Z8l799O0f8j9Q7U3d5)3J8;9!9s8K019h0_9j0b9l9J9%0R0_0v9C5 0_0l9r9n019:040k9`9t049v9x9z9B9H9b9L0g8b3 9P8+9Rac9T8)9V7k5j5^9Z9#8:9{9)049+9-818q9}9=9ma10z0Ca09/0_9 8R9$8}0T8D040K1aa66oaz4sa9ab0q665ea98,3D4mah29aj6vaV8.3jaoap8qarat9?22axa=3q0_0z0VaD8}9}aG2.aI928@aLaN2T8Pa88!9M0S3D6kaXba8$5j4Da$8*7H53be5T9IavaSbgaU6ybfa(7I4Ubkbx53bv5{8q8^8`a^0;8 8=aR8}0S0z0_1{0A360r0A0wbI019dbX0S0_118HaPbr8}8M9qaH9{b#041R0w9AbX9E9GaQ9.86bt8X4/adbm5O4:bAae9W0q6Lana.9%8^0Iau3Lb24tb$8G8Ib.aw0_0pb03lch5baK0_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;0Ib?cx2G9{c.c+c%0P0G0G26a|c 22bZdwa_c(ckdl8S3Odob*c`b:9_dz9o040Xd2dpd4cG3c8o2~aYafdT8(a%cKa)5za+3GcTa1bRcXbWdLbYc!b!cjb(bXdGcyaAdvdp5bb,c_c%c}dDcz0_dOa7d3cFbc6w3FcJcP5j5RdZbldc5Pd(9!9{8^2A0YbU1bcm9%b:e2dPdH0fdRea3c9YdVbgaZ6w3(dbeGeCd(bqd`bs8faU0WameEbB5@eheV8nambEcc0_bHd/bKb!bP042S9jc*eyd~d;d/b:c)e38qd etbN8t1ZcZdNcB5Ge8eQd50WaWeUd#7If8eXfb6iaWe#8}bK8;bX0w0V0_029x0R0Y0jfq0rfsfufrft0fe_0f0Db?0f0r2Tez0Sb?1|0J1!2x0-2e1!8Fb(0f9x0Iez0m0G0b0M290Sc~b{eyeA5ybefaeef-fef:6wbo5E8qfn3fa-fHfBdC0f0E2S0%2A2w1!2A0J0F0DbSgaayf*eOb}f6dS6xd7eKgkeJdXgk2Hf_9%f{d)8:fvfxgxftgz0jexggcEgieB0Wc9f/ejgIf=gLc9cScbaJ0_cee0c:040,dDcs4#9}020bftgV5.d?e:gEdF9;d=04dKd}c@8NgDdm9Ke95ycIgKgmcN9Uff5%cRa,d*e$e-cf2Gg!9@dBd@d/d_g{euc;g*4`0R8 djhma?8 2%0Yhrb4cvaOf1f35Vf58#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`d1jg810y847.7 7:7|1c0Y7?kt2N2I0P1Ykq0y7;8Q0!0$0(0w04.