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"
(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

.128013f06S:d=4yrA./Nopg2mcb1!w937ve l,8P5)tikné;ua(_shq050g0D0L0S0M0F0V0E0u0F0S0V0V0h010L0M0q010406050V0R0t0t0S0k0j040e0p0F0R0=0p0O050n0|0~10120`0q04051i1b1l0n1i0`0g0M0C0*0,0.0:0W0M0r0W0F1z0W0L0^050#0v0F0D1u0-0/011y1A1C1A0L1I1K1G0L0k1j0L0W0*150V0q0S0O0:0s011M1w010b0%0D0O0S0t0D1G1)1+1:1O1?1K1_1{0^0a0E0I0k0p0q0p0V0M180O0E0Z1%0k0k0D0u2g1b1~0O1j0n1#2t1Y1!1Z1H0g200:1C0O1^2d1G1r1t0+1N2D0M2F0O0p2J1G0q2m1j2r2t2X0{1*2h2L1;2Q0k0 0F0^0E0w2q2#0_2!1 2%1O2)2+2-0s2:1+2=2r2C012`0S2,040E0A2~2s0`312^0:34360E0i3a302#323g2-0J3k3c3m3e330p2*352-0d3r2?2$1v2_3w2{370B3B3d3E3f3G3y370H3K3t3M3v3x3h0z3S2@3U3o040w0c3Z3D2M3V3H0w2/1c2;3s3!3,3$0w2}3;2 3?3+2(3O360w393|3b3C3n410^0w3j453l3@403W4a3q4d3~484h3%3A4k473u3_3J4q3L3^493%3R4v3T4x4n0w3Y4B4f3F4n0s3)4H3 4J3H0s3:2X4l4s4y0s3{4T4r3#4W444Z4w4g4Q4c4(4C4*3P0s4j4-4I3N4K4p4?4O4^4Q4u2Z1o2V1b2J2w0g1!2B3u0u2R1|1j541k52502Z5a0Z2W4.1O0N0^2^3k4!3,0y2-5r4)2_0u0^0l0k0v2m5w5m0:0@040f3r0E5M0E5s1;5o040Z0b5F4@015u375V4|1=0t0^0U0U2O2f5)5!325I0T5.3u0v5I0V0D0F5U4d5P1O5I0G3k5O5x3f0^0!0M0X0R0!0L0D5=3U5I0K5K4k5N6k635G015@0^5_5{6e3,0p0^0m6t2(0^0C625~0:6v040h6C6433660=696b6d6j6l5M6D6o5^5`5|2Z6J6F6x5}6J0O0^0b0r6I6n6F6H4d6m5W0N5z040o196P4T6R6S6J6p046r6X2;6T6!6y2_6)0g6,5W6.7b5#6?0^6_2F3r4U3U5R5T770:5Y5O6$6n0O0b0^1*0k5a0R0k0V7p015:7E6(04105D6{746J607e3n0^1C0V6c7E6g6i6|5N6T5R0M732 6;5#7I7K5E6:750^0x6/2X7*327g6^6`7W0^7Y3=6}7^4s7x107A7C7}045;7t5W7,5C7.6Y6-6w7H6)6+8b5#7P7/6%7S0M7U7M2 6T6g5L6}6T7I7T7V8m32768E837J0q0q1^7a8H6f0^8a8g8c0^7-8u2s7:046#8S7+6A880K8y6R8A847z0p7B7D8O3,7G8=6z7J8e8W5l7c8i8^78040b8N8#5/0^618p7u8r8t8(8*827m0^2m0L7B1a998T048C8|067l3,7n0D7(8X6J7r7H7w042O5_8f7N6n8@958I8V88987@8,040+8|8w0^6h3*327r7!900:0V0g0^02690p0L0Q9)0R9+9-9*9,0E8V0E0D7U0E0R2F0E9D0#0O0u1L2j0,201L5B7L0E690M9 0t0q0F0P1{0O8D4{329$2-6}9}9@8{0E0v2O0$2m2i1L2m0u0W0D7zaD8!3=6Tao375N9.9:aN9,aP0Q9e7#0^7%7Q8I9RaX3U6F020F9,a!3^8U8{7E8G9J3#8%9!7F7~9e6kaU9C9w5Z8q8`7La.8 a:a+928l9O6Z5Y8sa*1;0p5Y2Q0Lbc5n6@7i9S7Oa^6Q816~9a9C0O9Ebm9H8Q8jb09F8v6Zb39G9n6*9Mbi659Q1K9dbp6la{5`5_887 3}bq7!a 9La?a/bF8$b6bJ017d9mb%a9bB9xbx89bzaZa?8xbObQ0(bw5W5IbU3b81a{aWb,7RbAb}5#b#bCbs93b)beaV8;b86-bf9+b)7`blbTa_8za 9DaEc896b=a?8db1b!bEcbbG94b$cw9N2;9fb5b@b41;b_7Z8+6J5RbRcv3ub cqcRbsbZcN1Ocab:cEce0^7?cJ9Pb.cV8Pcxc$bKcMcGcW9U3B0n5j0D2t2Ud0531s552w2z2u0S1Jd30n540`dd0!0$0(04.