Aller au contenu

Somme des valeurs d'un arbre étiqueté

Le cadre

Cet exercice porte sur les arbres d'arité étiquetés 🏷️.

Une modélisation Python est de donner une liste à 2 éléments :

  • le premier élément est l'étiquette du nœud racine,
  • le second élément est la liste, éventuellement vide, des enfants qui sont des sous-arbres.

Cette structure est donc de nature récursive.

Il n'y a pas d'arbre vide !

On pourra ainsi dépaqueter un arbre et parcourir chaque sous_arbre :

🐍 Script Python
racine, enfants = arbre
...
for sous_arbre in enfants:
    ...

Exemple : Un arbre à six nœuds

graph TB
    A(6)
    B(5)
    C(4)
    D(2)
    E(3)
    F(1)
    A --- B
    A --- C
    A --- D
    B --- E
    B --- F
🐍 Script Python
T = [6, [
        [5, [
            [3, []],
            [1, []],
        ]],
        [4, []],
        [2, []],
    ]]

T est constitué d'une liste à deux éléments :

  • l'étiquette 6,
  • la liste de ses enfants, il y en a 3 :
    • un nœud qui porte 5 et une liste de 2 enfants :
      • un nœud qui porte 3 et une liste vide
      • un nœud qui porte 1 et une liste vide
    • un nœud qui porte 4 et une liste vide
    • un nœud qui porte 2 et une liste vide

La somme des valeurs de cet arbre est \(6+5+3+1+4+2 = 21\)

Exercice

Coder une fonction somme qui renvoie la somme des valeurs d'un arbre passé en paramètre.

👍 Toutes les étiquettes sont des entiers.

###(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 : ∞/∞
.339.9888.128013x/.Tr;nbOylaeêu)dV63Hm(P+02è-W@],5fq!7 _o=pcwgv41kRéhtsSàj[i:E050t0p0(0o0.0n0)0P0U0n0o0)0)0S010(0.0T010406050)0r0y0y0o0h0m040*0R0n0r140R0j0P020o0y0T0i0P0#0p1e0h0M0r0p0)050e1b1d1f1h190T04051M1F1P0e1M190t0.0X0|0~10120%0.0W0%0n1%0%0(17050@0k0n0p1Y0 11011$1(1*1(0(1:1=1.0(0h1N0(0%1@1!010L0_0p0j1s0p010|1k0)0T0o0j120D1.2k2m281_2b1=2e0y2g040c0P0A0h0R0T0R0)0.1n1p0=2i0h0h0p0U2K1F2r0j1N0e262W2325241/0t2t121*0j2d2H1.1V1X0}1^2*0.2,0j0R2:1.0T2P1N2U2W311a2l1p2=292`0h1e0n170Z2T3518342s371_393b170D3f2m3h2U2)013m0o3c040w3q2V193t3k123w3y0Y3B3s353u3H170K3K3D3M3F3v0R3a3x170v3R3i361Z3l3W3n040O3K1Q2 1F2:2Z0t252(3U0U2{2z0;1W1N2~0p303g3.3{0=433j3(120!170=0L3.3E4a010V170P4g3T4i0j0L170)0R1d0p4n492?0116040z4x3%4z0j171f0k2P4E3u4B0s0/3R0P4S4m4h4z0)2p04011x0j0X0R0.1?0~0P4t4v0P0=0{0X3x0p0r0h0{4:0P0j0a0r0t4`4*004J2P014R4T3$3N170h0o0U2^4w1G444V294B0J3K4U4o4G172d0L2m0(1E5h3r5o4y290R170S5n593U4H04545g31064T5z4F384s4u2y0Q0(0R0@1=5F5j1_5C045E5x2V5P5a045c5e2,574S5G4i4c040L3W5!5p5R044t0r0)0Q5K5}5A5$4k042^665Q3l5r4q5u5w335#124B4Q5*185O5O5@5q605T0p5V5X4?6c3u5%0B5)315,5H5S4v4M3U4B4D6o6s5 6163656O6k4A170s5=6G5^5b0?4^0j6A6H6u4v6x5Y5L3g190e46423/6^0e3=1F0(3@6}2$2X0o1;6`3=1L486d122P0y0Q5t0!6w0%0w171x1z1B1D0P6n331S3h2:3u0o0t0y1o2J0.1o0P144B1L7u7w7y2K0F140(211i0(0m1=0P0r1p0T4@0P5{0j2R7A0j2,0n1Q7s1W3u1{1)1+1-783u2v2d2f172B0*0U0h150(2C0m261o3.417832446@7;3U5_4e6K4i694m6U5~3l4r6,2y8e4z6M8o5 6T6j8j6l6X7p6;6r6V4X174!2d4%4)0P4+4-2y4/7n4=1=4^510{4}4 518I530h4K2g6Z6P6e5.5d5f8r1_5l6*4p6f5t0j5v8.4z5%6E3g6!6t8t8z586V5_2P0(6(8@5 5/8*6o8|5B170B963l0k4s1c8+8w4C9k3v6I8n8i679l6N8u9s9o6u62648Y4L9r796W046Y9a8$4b175{0h9f3G5S9z8~5y9J010R696b9I6V5I5s6h9n4O3#6?3|2W853;3 770:7 0o0X2Q4m891e0T1F897)1U7+3U7-1}1,2q8v2a2c2x2z7`7|7~80826)6O9.7q339 914d0p4f9D3u8g9n4q9p6:3r9U8qas6+9S2VaA8x8#8B4Y8E4$4(4*0o4,6v8M4;4?8QaS4|4~508M8W5K566o5N90a85I985;aC4i8-9Za+8:9%a=9w8_9O9xaE6pa*9w926%0hai6F9Ua,8)a.b66V6Ca|0j9h609ja/8p179u5ia+bg9|9(blavaxbr045ma_9E9#6g8=6ibn9w4O9H5M9~9,6_2W769/0X7s0?0^0`3u0t2m0W0p0h173D1c1z1h0ubY2I1o0{0p0d230q2y6ib$1J3h1P0.0y0W0P3x0(120b2h3U0(0V1y0R0,0.2h0)0h0U1#1 0T0)0/0e6?0t0j0f0,0)0=1*0X0h0f2,0(0e1(0e0,0=0U7f0t2Xc67xc90H0Z0K0f0Z0f0C0e1^0?0)1G0X0W0e0D0v0o0C0f0)cW2h7L1=120/0V1f0j2^0W0/010e042C0R4^8I7nb.7V0h5v0P0Na03~2;4ia47/a79w7?ab7_0P7{7}0T7 0A810%83aj3:al88bKao048dbj29audy8kbudB9tbt5J9BayaF6V4O8y3ra)5?aJ8D4#8GaOaQ4.4{8O4@4_aW8TaZ2M0n8X8Za%5M8Aa?8(5:dJ8aa:17bxbbd:9$bCa|a{by5-a~dP9b1_b294b4bebg1HbvbmdO6qb09EaB9vbzdDek4NbsdE9x6R9A8ZbvbH8{9U5_9Mbe9Q6SdId 9Xb5ex9!a@d~eq4Od`8 egb74s0@d29ne0en6+a-d?e4aG9G9*9 1S3:6{9:1O1Nb{b}b c1c34ic5c7c9cbcdcf0(chcjclcncpcr1Wcucwcy0%cAcCcEcGe`0.cKcMcOcQcS5vcVcXcZc#c%c)7C2Jc,01c.c:c=c@c_0P0l1p2`0(bYaPd*0o0,c|7 2M2l2P8=0%0E0)7n0o1mc|0ha!4+3{1t0h0$0%2db+1pd57r77fDft2Pb~4=8=0obX4/0r0PfP1s0E231?fP4/0$5t1m9`9,0)eT0(bJ474,0r1W5u8IaP0t0R0U1c2d0@2Ka!dmah7od67ta31+a57:9Ude7^04020W0(0igHgJgL1vf*0n0T0z1Hewazak446O890x0pgQ0P7B0kgh0n0(0F2^7X7T7!7B1H0Pg.7x0t0r7Rg)0_140jci06061H0z2JfH740J0P0eh9gb1fc00C0se41xe81p261?g?0R0Lb~0P00hdd2000P8O1C0P0z4efWg+0/0Phge45O0T1l0{2sh65c74g%hq0j1c0kb*h25O0Gf*hlf*g@fGhP7R0.b-1t7Ph9936(7Ch$hu7 hy0p0fe40g1$0{0Lg:gsh+g@8=2d0=2(2k2Q0.2b0U3x0n0m7X3W7SfU0P0V2J27hT2y7}0Uhx3x1C0)e42m2(1eig2P0,2Q7 2`0j0FipbY0.is7P7V0)h{ge6`9.e,bP770AfY0|4@0d0P1B0.0P1e2J7}fU8=c~4,7P7R7Yg;7$g#f@9_4+i?gs059{0o9}9+47gxa2d9gAdbd@4zgE2ydgdiafgudoeHgVdrgXamdua88caq9ndAeX4p8l8Kd?e$eedKd:a~e$4PaIa88C4ZdTaNgkdW8LdYaUd#4{d%8VfJdId-ePe59Pd;99jubkbweB04d}8?e13UeWeIjCeEa(d/b16$hkea9i0yedavbpj1j eq5IjxbveO9TeJj+bBj-j%5k6Xk85+eR60gceV5DdGeZeve(bKe*75e-g{3h1*1Nj0j289b~0ThK0.7mjMi}7#g947k6j3420P0+0|0%0okH6R0F5Kf!fIh+fGkL42j,5we)ky19ky0U1?i%f~2Eg`2J7S1p2J0$5cfG4^bxk,05kygmi.7B5tk^8JaR9@9_i gabikC2^7z3xh+0$1?lbisldkMgc0SkpkO040f1Fl10ekw77b)4_7#0{kR2~2Haef?2dk=2{0ri@d4j5d84zda1~dc9Ejcacdhaedkagji84jlazgYjo9w0U0Z1703c{c}7R0tg60.h97Thn4@7R1}2,hA0U001D7 7Vf}f$2~f)f+0.hQ0NmggU3Ceyaparke1_jtbEbzjw6vk3mnj!jDdLaHj.6#5.b3jjki9!ebbimv9FjAja38k1j2mJejmq5-kNmQd_j*mxa84B0-9n0yca043eeM170I0skhc`kjh@km5(dGmYbF17m#eqm%170Cbvm-3R3Sl.l:04l=iXl@7n0W1k0Ld!0{0zm4m6g@0n1*2Imfmh3#kamUmSj/kneq5_0~0y0kbVmXbvdNmFboj}munt4pmOnIaznrmtm+j)mA8}bvm|mJm~m)n1m.j*m=eqj:nNjCnUm$m(n0nQn2a(iR9-e+bN6{bR0_0)3hn_0@n{04.