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.

🐍 Script 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"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
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

.1280130ldy1,4Aké/we!ibmc:_35qaPr 7=9of.gt28;6sSh)(pNunv050d0n0J0y0p0c0O0B0s0c0y0O0O0D010J0p0T010406050O0V0r0r0y0A0e040P0F0c0V0=0F0W050l0|0~10120`0T04051i1b1l0l1i0`0d0p0X0*0,0.0:0Q0p0I0Q0c1z0Q0J0^050#0q0c0n1u0-0/011y1A1C1A0J1I1K1G0J0A1j0J0Q0*150O0T0y0W0:0K011M1w010G0%0n0W0y0r0n1G1)1+1:1O1?1K1_1{0^0a0B0z0A0F0T0F0O0p180W0B0Z1%0A0A0n0s2g1b1~0W1j0l1#2t1Y1!1Z1H0d200:1C0W1^2d1G1r1t0+1N2D0p2F0W0F2J1G0T2m1j2r2t2X0{1*2h2L1;2Q0A0 0c0^0B0f2q2#0_2!1 2%1O2)2+2-0K2:1+2=2r2C012`0y2,040B0v2~2s0`312^0:34360B0h3a302#323g2-0w3k3c3m3e330F2*352-0N3r2?2$1v2_3w2{370C3B3d3E3f3G3y370L3K3t3M3v3x3h0E3S2@3U3o040f0b3Z3D2M3V3H0f2/1c2;3s3!3,3$0f2}3;2 3?3+2(3O360f393|3b3C3n410^0f3j453l3@403W4a3q4d3~484h3%3A4k473u3_3J4q3L3^493%3R4v3T4x4n0f3Y4B4f3F4n0K3)4H3 4J3H0K3:2X4l4s4y0K3{4T4r3#4W444Z4w4g4Q4c4(4C4*3P0K4j4-4I3N4K4p4?4O4^4Q4u2Z1o2V1b2J2w0d1!2B3u0s2R1|1j541k52502Z5a0Z2W4.1O0j0^2^3k0B4!3^0s0^0i0A0q2m3k5t1;0@040t3r0B5I5s4)5n0^0Z0G5r5C210r0^0u0u2O2f5V5B5L0:5E0S5!5m0:0q5E0O0n0c5P4d5R5$0^0g5Q5#330^0!0p0x0V0!0J0n5)4@015E0R5G4k5J6c5K5*015,0^5.5:654|010F0^0H6l3n0^0X5`6f6o040D6v660W5}0=6062646b6d5I5?6g5-5/5;2Z5{6x6q5=5{6C040G0I6A6m6x6z4d6e660j5v040U196H4T6J6K5{6h046j6P2;6L6S6r4s0^0G0d6!326$743u6+0^6.2F3r4U3U5o045O773#0G0^1*0A5a0V0A0O6 3U5%7t3^0^105z6:6|5{5E5_6(6L6W1C0O637w5D0^695H5J6L7g0p6{2 6)6m6W7z5A7G6R0^0o6%2X7X32796-6/7M1O5E6a6;6=7H7m107p7r7;5@045(6U6f7Z5y7#6Q6w6p7 5|6X6Z83667E7j7x047J7L8f6m687Q6J7`8k0p7K7B2 6}8a8n6s040y0T0T1^738A3u7v8I3#7y868w2s8y046T886B6t8b8p6I8r6V7{7o0F7q7s8L3,8K8U7Y8N7A8b6~8+2(718H8.328h7$840^8l8P5l8g7O8q7,780^2m0J7q1a8~8V8t8v7d7S5N0n7V2s977k0^2O5.877C6f8-9u9f7!926L8}7+8s0+9A7D7O7@3=6L0m2-7R8@1O0O0d0^02600F0J0M9U0V9W9Y9V9X0B9z0B0n7K0B0V2F0B9r0#0W0s1L2j0,201L5x7A0B600p9;0r0T0c0k1{0W8m4{329R9N6J9/9)8O0B0q2O0$2m2i1L2m0s0Q0n7oas8T9K5{ad375J9Z9#aC9XaE0M969j047U8i8^049FaM1O6x020c9XaQ3f8:9t8x7%8S8b6W6u9P809J3}6=9o3,7T9m378s9z8=8z8{708daW6n9MaK8*9D6Rb02Q0Ja~7.7b9G9v0^a,3ba.6c8s9ratbb9481a%aYbl6#a`9x8/a}a*675^a~6WaPbw8Y7^8!6f7g5/5.8Xbd96a.a@8Oa_a$bw6W6Ya~769ebu9~aZ8Q9HbnbS5p1KbK040RaI5{bH0(bq8|bL8Z6daJaLbX8Ba^bw8?a{8M6X8`2;a/1;0Fb08ubVb59Wb86,bab+be0_bg7R8#aK0W9sb=8J0^82c18jb~cuc7bsa!8 c3b+7Fb3cBbBcx7=95b^bhb/5}b;chbM7_cmcwbt75czb#cB72bV0^7*c58sbZcq7ucsboaOb*bCcK4Z0l5j0n2t2Uc_531s552w2z2u0y1Jc|0l540`d60!0$0(04.