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

.128013kg: r);SĂ©/q(N.lo4y,6b=ac15ud3t2!8_Pw7evp-fh09mnAis050C0M0E0x0X0p0Y0e0y0p0x0Y0Y0w010E0X0O010406050Y0B0U0U0x0f0s040i0q0p0B0?0q0V050k0}0 11130{0O04051j1c1m0k1j0{0C0X0N0+0-0/0;0-0V0c0B0x0c0M0P0O0s0E0R1a0e0R0X0c0R0p1O0R0E0_050$0v0p0M1v0.0:011N1P1R1P0E1X1Z1V0E0f1k1J0+160Y0O0x0V0;0F011#1x010Q0(0M0V0x0U0M1V1`1|211%241Z27290_0a0e0J0f0q0O0q0Y0X190V0e0!1^0f0f0M0y2u1c2c0V1k0k1J2H1;1?1=1W0C2e1y0X0V262r1V1s1u0,1$2R2T0V0q2X1V0O2A1k2F2H2.0|1{2v2Z222%0f100p1V0x1M2A0Q0;030I0I0y2(0M1R2$0q0P0z3c0_0e0z1c0x2/2=0`2;2d2@1%2_2{2}2 0M3101333537392U3c0P1 040e0F3i3k1|3m2F2Q013r0x2|1k2~0R303234360!3B2%3D0D3f0D3J2E3l0{3N3p0;3Q3S053U3W3x3Y3A2S3C3d0r3f0r3+1d3-3n2?1w3q0q2`3R3t3V3v3X3z3!3}3$3d0A3f0A432.3.2=3O3=4d3_3y3Z384j3b3d0u3f0u4p453/483;4a3s3T3u3w4x3|3a3D0L3f0L4G3L4r3o4J3P4L4c4N4e4P3{4i4S3d0H3f0H4X2G4Z472!4$4b3?3^4f3`4h4z4.0P0T3f0T4?3M4s3:4{4M3@4O4g4y3#4B3c0S0_0z0S584^4t4%4}5f505h4A3D0z0z5m3h0k3j3,4Y465r4|4v4 4Q4-3~3c3F0z3I5D3K4@5H5b4u4)4w4,525O0z3(045(5p5W4#5Y5e4*5g4R5%405*425T5F5V4I4`5/4~4+515i5y4m5*4o5{445G5~2^5s5K625w530z4D5*4F694q5-5 6e5Z5L5#643d0z4U5*4W6n4H5a5.6r5:5!635x6w4:5*4=6B6b6D6q5J6s6g5?4k3c555*576O5}6Q6d6S6G6t6I530F5l046.5,6c496)615=5N6W0F5A6:5C5E6a6$4!6R5d6_5v6V5j0F3F7b6=6%6@765u5M5$6|5)0F3*6#59746(7h5;786{7a5^0F5`716o6?4K6^7i6u6J3E660F687B6C7r7g4(6*6U7w3D0F6k7W7e7P7E7t6H6h5O0F6y7*581n2,1c2X2K0C1?2P5b4y2W1t1k2+0M2-3l5|1k4y802d0X0C0;342F5y3t87896,5%202i0M8f7(6W6~3+7D010b0_3p820e6p2^0y0_0W0f0v2A828x1%0^040d820{72852v8e018a2=7V8d888R8g6|8i288k8X8m7a1V5T0e8,8w8q8s040!0Q8v8G0;0Q0U0_342S2t348F8q8I0m917f0;0v8I0Y388?8N8^018I0t8@8q0V0_0#0X0l0B0#0E0M957!9f0_0g8K8N8M2:3N8Q8S1|3%8V8l799G0e8j9I7U3d5)3J8-9S8.9601980_9a0p9c9B9V0q0_0o9t4_2^0_0N9i9%0_0w9:9u9k049m9o9q9s9z9+0e9D0I8b3 9H8%9Ja59L8#9N7k5j5^9R9T8,9e9X049Z9#818q9(049*9d9j0_0Q0c9@9,1%aq9?8N9U9u0b8z040n1a9~6oat4sa2a40P665ea28(3D4maa29ac6vaR8*3jahai8qakama05baqas9$9^av0Cay3OaBa_5baG0_aJ2T8La0aP8T4Ca67H534DaY8$b85O6k3J9AaoaO8W9E0V4Tb78Y5j4Ubba!7I6y8p9V8:8=a|5.0Q0_1{0f360B0f0Ya.4#93bK5 0_118DaLbi9u9gbAbO041R0Y9rbN228I9xb2aN86bka3b50P6LaTb-aV4/8!aZa79Ob:a%3G8-9e8:0Xan3LaEaz3;bP8C8EaD9eaq0GaC2.c63Oa~aIaKb$8H0_9yaMa=8Pb-aQ6Yb=bt5355bsb{ad3Dcw8+a)9e9_bEbGbIcn0;bMb+c73Pc9bRcN01a:cV9_awcVbVccaubY0Xb!bS3L9eb(b*csa1cub/5nbob@5kb_bcbp5y6/agahcI0_bZb#cQa`9)cYbP0O0O26a^d75bcPc;5XcTcbdj4#cXdg5.9.c#9wc:bTct8faQ5zc_a83c5AcBbd8n8ocGd2c(cK0qbHbJdq4`didw4tdlc,2Gcdd9dQ9-040QdfdndR0_9hc%9V9_d5dW8O3Oc/9 d7b49F6w3FcxcCa#5Rc|cy5%d}dJcia}0_2A0EbH1bd-a?c)c+dvc-9Cc?d{3c9Q2~aUdC5(e2d 7Ies2H3jbhejbjdyc@afepb?er40dFc~6waf5{8/0_bzeecR0VbC042S9admdTdh0_94d!3qdVdt04d,chd3040,d;c.9wcq45d_elbm6waSeFe38naX9Meu6iaSeN9V0K3fc0e%0;0Y0C0_029o0q0E0hfg0Bfifkfhfj0ebQ2A0e0Mb!0e0B2Ta10Vb!1|0y1!2x0-2e1!8BbR0e9o0Xa10U0O0p0j290Vd6crdTd`e{3cbfe~f35%baf2dG5j6jb~9efdf9ahfyfrca1!0v2S0%ft2x2A0y0R0MbFg2a;e^c;fZ5ybvf%f,gaetgd6wbvf69uf;b 8,flfngofjgq0heidXekeCem0zb;gceK3c4:eJc`gzb~9Sc10_c3bWd#e:gNaAff0pfjgQc804fse;apdZd)d#9/fb9v8Jgud=g96wcwgBgGcAf+gC0zcFa(cHeOeVc42Ge7drgXf_cVdpg$e(d$axeRa`f8eVdPe-aphd2%0EgV8raHb0gZ9V8Ie@5Ge_gxf!6.dBb|hxgFdChxexgma)a*d.gLfBg3hpbUe#dah3cUg)h6eZh2c!g)c$hghIe/1Ze*0gg,5Hg.3E8og;hCdEg@c`6}gIg|bx9l0)hMcRhrh)gw8XaQ7bhycD3di3hBhze5g{hGhHefgYh5g#hUbXhWhZ9ua{hbdk04fKeYeAhN04e$h7gWgPhXdud^g8e`7Veoc=e 7a3(i8i53E9Qe6gK9`h{e*hs5Vhui1b/7zi4a#iZiLi#eMib9TiQgMioh2ifhSihiteSa@hl0qhdc*i_hifihlckhoiTh eBiXem7Li!7Ij8i%jaf5i*hGe.eWhLe*iwiid#i:ixcWi=gvh!d%e*e,3lh1bXizjpd@fXi?iHj6hwf$jFgg3Ef*abf(6|bfe6gJg}389aj3iCfYiEi6gbjJgC7*gfj%gijfh^ieh4i;arhPjui.4`inili@iqj/jBhOg)9_jAjmco04h(jXc-0k847.7 7:7|1c0E7?kf2N2I0x1Ykc0k7;8M0!0$0(0Y04.