Aller au contenu

Taille 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

Il y a 6 nœuds au total ; la taille de cet arbre est 6.

Exercice

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

###(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 : ∞/∞
.128013x/.Tr;nbylaeê%u)dV63m(P+02-],5fq!7 _o=pcwgv4F1kRIéhtsSàL[ji:E050r0m0!0l0+0k0#0J0O0k0l0#0#0M010!0+0N010406050#0p0v0v0l0f0j040$0L0k0p110L0h0J020l0v0N0g0J0W0m1b0f0G0p0m0#050c181a1c1e160N04051J1C1M0c1J160r0+0R0_0{0}0 0Z0+0Q0Z0k1!0Z0!14050;0i0k0m1V0|0~011Z1#1%1#0!1-1/1+0!0f1K0!0Z1;1X010F0?0m0h1p0m010_1h0#0N0l0h0 0A1+2h2j251?281/2b0v2d040a0J0x0f0L0N0L0#0+1k1m0/2f0f0f0m0O2H1C2o0h1K0c232T2022211,0r2q0 1%0h2a2E1+1S1U0`1=2%0+2)0h0L2-1+0N2M1K2R2T2~172i1m2/262@0f1b0k140U2Q3215312p341?3638140A3c2j3e2R2$013j0l39040u3n2S163q3h0 3t3v0S3y3p323r3E140E3H3A3J3C3s0L373u140t3O3f331W3i3T3k040I3H1N2|1C2-2W0r222#3R0O2^2w0.1T1K2{0m2}3d3+3^0/403g3#0 0V140/0F3+3B47010P140J4d3Q4f0h0F140;0?1/4k462:0113040w4t3!4v0h141c0i2M4A3r4x0q0,3O0J4O4j4e4v0#2m04011u0h0R0L0+1:0{0J4q0k1/0J2J0k004F2M014N4P3Z3K140f0l0O2=0m4I3R4x0D3H4Q4l4C142a0F2j0!1B1D3d554u260L140M544^3R4D044:4 5e3o064P5g4B354p0=4*0m0K0!0L0;4s5t2S5x3r5j045l5J045L3R0v0+3a4?4O5n4f49040F3T5m4R5z040#0L0p0#0K5r5)565i4h042=5?5h3i584n5b5d305*1?4x4M5Q5v5w4@643D5A4r5D5F5H5s2~5S4f5N0y5P6k5Z57044)5I635@65144z5Q6r5+5-5/5;0f4G6j416c4w140q5X6l4v5#2M0!0p0f0h5|5y5~6t5B1/5E5G3u6J5u1C433 3,6/0c3/1C0!3;6@2Z2U0l1.6;3/1I456Z0 2M0v0K5a0V5D0Z0u141u1w1y1A0J67301P3e2-3r0l0r0v1l2G0+1l4(12141I7o7q7s2H0B110!1~1f0!0j4+0p1m0N0m0p0J5%0h2O7u0h2)0k1N7m1T3r1^1$1(1*723r2s2a2c142y0$0O0f120!2z0j231l3+3~722 416.7+3R5#4b504f5_4j6B6L4n6e5C884v4x6A6w5}6d5q6H4H8c6x0 4K7j3d695Y6L4T144W2a4Z4#0J4%6u1:4-4/8p2d6P6C6!4{4}2)8h26526Y4_0459618X3R5N6p5f8P8n5=685w8+016S0:6V6X5Q6Q265U5W8_8:6n8$4m0i141E8U6y4y968n8I996M988r8m3s945.5:8-8l739d6O8~6L5#5%0f916s6E9k8M9v5^145{9q8s9h8Z600h5c9c4K3Y0c836:2T703.3|1R0:5B0^3R0r2j0Q0m0f7y17191w1e0s9%2F7v0m0b200n2v2Q9+1G7m9W0?9Y4f2=5%9)1E9,040T1l7U7v05831b0N6-3_2 9{1d3e1J0(0l7Ra92H4jad0laf9Oah0J3~0h2#0/0p0b0J1c0Q192a5c0D0J7M1:7Saa1m0:aM1m2G0Y4{6~0d0J0-5C0J2M4Y4!1:7M0JaV4{0!7P0fa-0}7Q8Ka.6}4+18a=1/7g0k8GaoaParao0Y0!0YaF0N0N1%1y0Y1:4z1v04ae1Cbi0q0d7Z710Xb15a1j4(4{0h0#9t2va=9=bc0+4}a:2v9J8G00a`a:6V0J0L0ia:0h7Q2a8G0+0#a:aL2FbO1m0R7P7_aNbVbX1:0Hbp1L040-0b1vbc1:671Q3{2.4f7%1`1)2n9F7-2u2w7;7?7^7`7|8^307 3Z813oacah8:5p2@0v6I628*6L8(9A970)9c8|040S3m9f9n8W9E9gcx0U3xcB4J1453cE9ncx3NcJ51cLct0 cx0AcA9mcK040C3O063P9g860m4ccR894i9c8e5q0*5.a:0K3bc.8i6zc;14cc6K9F8u8O9r4`8?6WcU9Gd13o8`1?90cN3rcGc%8:5#1=9%0!da0h93bj0l0b9Lc~c|35dsbkdy978kd29g5p0lc@1j5Dc{cZcS04cM6q8dd00Lcn2Mcpch6L4K9pdR9F8(8)dd8:cx0ScI2~c(c)9nc+c-dNc/5Rc;4o8ZbX0K2i0+9udC8tdxd^6sdc2S8:d48.6b9F8=6Ud9dh5od0da5N0odacWel5kd)5Kd+5V040zdkdS040f0Y180k0;dpei6m5kdqds1%bXdw9ee6dz14dBeQdDc d}0!d 0=e2eUe4dPdqdTdV1AeO0qd#8wdl4E0}doe)eAeC0peE0leGd$9gcseHc}04cve38;0O140e0f1zeOdQcqeef8a73u0#6+e9dZcTf2260Vfh0Tfjfl844fcDe d=fhfafcf64xc$68ag449Q9T0R3e6=9~0@al040x5.a=0O7PaE1y0+0J1b2G7@fkbIa|7J4+b47V7XaFb%0Ob2ap7Tarci44dB9P7l1R7#3Rb 7)c29gc47/2x0J7=7@0N7_0x7{0Z7}6Bce7k309Pd60487f68ad{8f6vdFcCe5gw8Y9lgzdO4Ld59F8A4V4X8E4$ao8I4,4$8L6I4=ec8y9F5p8R4~fde^8!9JdXetcreJfp6!gB5u8/go6T8@eoevdMfff0140yeK9419eOdEdYgVdAauh0eW9bfEfofz8Yg#9Kh904e.9Nf~ce6=9U05e{3e1%1Katav83babD7gf@f.ab83h8hu0%0_0Z0lhx9x0B5rgOf@eMa:asahhd5df~hq16hqfW0JfZay2B0r0p2GaTa-b8a/a;cMhV05hq0r1l7_7v5ah)4%5-1a0mbo0ch:0cho719.0f9:bx0JhE2{2Ec82M0JbUich%aQ0Jb.f b|7$1(c07*8:g72v7:gac8gdcaghe83}3-gl82cj6L0O0U14032zfU8G8J0Y28aLb*fke{4$1!2)0J0w0O001A7_7O7Q3^1qeB0Z2a2F6~il0H0He/6,gogqe$4gc:f6c=h8i}8jeWg-fmd36N8vd*g:d8iCdecVg@eq04g|g+3Dds95hfh1j7dGh4avj3gyh2dGgufveahag_9ndH9zhff5i}djhf0Chh68d;3riJiLiNbN1/0^0Q1h0Fa;0^i#i%bXa-4*bW0+i=i@i^3Yezj2gCeI5O9c5#0{cn9!e^0leOjag(9FjKhb8%g{g}5,g jpc;jth6j0jzgZjl9Gj jHcwjhjLjNd/fI6;hk9SfO4)0#fN0/kw04.