Aller au contenu

Largeurs d'un arbre

😀 On considère ici des arbres non étiquetés.

Définition des largeurs d'un arbre

Les largeurs d'un arbre constituent la liste des nombres de nœuds qui sont situés à la même profondeur.

Exemple

graph TB
    R{ } --> N1{ }
    R    --> N3{ }
    N1   --> N4{ }
    N1   --> N5{ }
    N3   --> N6{ }
    N3   --> N7{ }
    N3   --> N8{ }
    N4   --> N9{ }
    N6 --> N10{ }
    N6 --> N11{ }
    N6 --> N12{ }
    N6 --> N13{ }

Les largeurs de cet arbre constituent la liste [1, 2, 5, 5].

La modélisation de cet arbre est :

🐍 Script Python
L_5 = [
        [
            [
                [],
            ],
            [],
        ],
        [
            [
                [],
                [],
                [],
                [],
            ],
            [],
            [],
        ]
]

# variante à plat
L_5 = [[[[]], []], [[[], [], [], []], [], []]]

Exercice

Coder une fonction largeurs qui prend un arbre non étiqueté en paramètre et qui renvoie la liste de ses largeurs.

Indice

On peut coder cette fonction, au choix,

  • de manière récursive,
  • ou alors avec un parcours en largeur.
###(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/.r;nbylaeu)dV63m(P+02-],59fq78 _o=pcwgv4F1kRéhtsSC[i:E050o0l0X0k0$0j0Y0H0M0j0k0Y0Y0K010X0$0L010406050Y0m0s0s0k0e0i040Z0J0j0m0|0J0g0H020k0s0L0f0H0U0l160e0E0m0l0Y050c13151719110L04051E1x1H0c1E110o0$0P0;0?0^0`0W0$0O0W0j1V0W0X0 050,0h0j0l1Q0@0_011U1W1Y1W0X1(1*1$0X0e1F0X0W1,1S010D0.0l0g1k0l010;1c0Y0L0k0g0`0x1$2c2e201.231*260s28040a0H0u0e0J0L0J0Y0$1f1h0*2a0e0e0l0M2C1x2j0g1F0c1~2O1{1}1|1%0o2l0`1Y0g252z1$1N1P0=1-2Y0$2!0g0J2(1$0L2H1F2M2O2_122d1h2*212/0e160j0 0H0S2L2}102|2k2 1.3133350x382e3a2M2X013f0k34040H0r3j2N113m3d0`3p3r0H0Q3v3l2}3n3B350B3F3x3H3z3o0J323q350q3M3b2~1R3e3R3g3s0F3W3y3Z3A3#3T3s0G3)3O3+3Q3S3C0C3;3c3?3J040S0w3{3Y2+3@3$0S371y393N3|443~0S3i493k4b43303-3r0S3u4h3w3X3I4m0 0S3E4q3G4c4l3^4v3L4y1I2@1x2(2R0o1}2W3P0M2:2r0)1O1F2?0l2^393F054P0*4X4A1.0T0 0*0D4Z3*440N354.3=4d0D0 0?0e0O0l0m0e1w4F4/210~040t4?4(3A0 170h2H584k1.550n0%3F0H0H4s4O0S0 030H0P0l500$1g0H0e0V0M4 2A5u423n4;3s5m5n524@210Y0o0 015S1o250P0J0$1+0?0H1Y0Y0X1+0*0:4{4}5D0H2E0j005c5e4y4j3n5P355K250H0D1g2J5x2D5Z0k0H2?0J600g0*4 5G3P5{5J5m5S013M5K5n533e0 250D2e0X512_6n5N1.0J0 0K5l5o3}5b0e5d0l6l5K6E4d4`0$5%6J4y6x59016A046C6S6M540 0#5f3n0s0$4v6(3P550z6K5m6!4)0 600e6D6o5a040Y0J0m0Y0I5?6R6w6?0`0J5I2-6{6y6}6r6t6v4Y6|01555k5^6m6m773o6O6Q0I7f0g0X7c6U6W6Y767j0g4`175-506-3?55575M6U7E6~7072747J445i6;7o7q7P0g7y5g786B7$3I0h4`257U6#567/6p045$5(7u0g6s7w7=0`7W7n7o6=7j4*046_7*3P7P0$883?790 7b6Z7D7,040e2e4}7~7k0 7M2{7D0 7#7N7%8p045j7X82837d01850$4-8h8E8a8c446W0v8M216*6,8J7z0 020j0X0f8Q3e8j2o8o7L8o7P7^757i8E5i7m2_068C8^6T8x8,6P5(8)6$8+8f8#7(048P8U8x8S3 8 046:973n8O7B398`3I7s7_7v7x8w3n556%9p89929t7K0 9d8?8_6L846q0/8.3k7q7l8B9B9j9u7@8}9G2N7q6W0d91040k0L0L250o9b8r8/7O9l0l7`7|9o8s8:909w6N048b9=7:0z0n7X7q852H0X4 8v7C8K9*3W0c4#4W4Gaa0c4J1x0X4Laf2U2P0k1)ac4J1D4%8x2H0s0I6s0T9+0W0r0 1p1r1t1v0H8=4Y1K3a2(3n0k0o0s1g2B635/8m5v0 1DaLaNaP2C0y0|0X1_040p5v2A5y0k5u0M67174P5.5~5,4~6`aI1M1O3n1:1X1Z1#aq3n2n25270 2t0Z0M0e0}0X2u0i1~1g4Z4Vaq2`4Ya9b43P0T7P0D2w0s8o5I5L9/7O7P4P0j1*621g7h9H7jby8obs8f1l3R9.9i7Z4+0laD3M5_br0 3dbx4=9_3e0M0 0R249baG4i7p7j0Y2h04010!3Z1+b,1*0Ha.2I0H0m2!5/bV1u0H0l0D230M0k0M5)1+0ubh0W1g0y020O8ZbDbF2C0Y6k818D6U854,b$3s8o0D0s0 0I0I2-2BcF9$8o0h550Y0l0j8IbA8x8;9Kcv8xcM0 cOcQ8o9T9V0o0k0,936V7)9e9N0*bWb(7 8q9|5^8@9C8Ecxc9czbz9(8{4_041v0X0I0P0$0*cKc?01cY6~cPcRd29q0 8Acu7Y9D8k0+a2c,dfc!dibJ8Ec%dd7Pc)c+c/8d6B9h3k9M6F04c;1u9$c_8?c{cW3nc~dw9RbKb%cS3Id46rb-dd8*dddudh9b0Ac,7P0b9bdm9A8C7qd+c#dddzdZc:c*0kc$0 9UdA5b9Y9!dcd~dKd;d(dlbXb;c}bUdVbq3?bLdAd40o0Vb6e9dj3Pd`ej9Idlb/3w8^9~8fejdJ44eve204e4ea9?d6d8da9Qek7Vc^ez109LeF219 0-cOd/2r0p3q1u0(2G3Resdx6Ub?5Rb}1+d90*cteL7:dP4aeBdpa0dsdEeGcNd,d|e3c(e0eIeKetdK2y0L1*0DbRe/cTc^bXeCdLc ddeme{3ed4a_5De.dWa59W6H5@ftc@8zeUdReX7?8-c,7Ac,9r8o9941ed9c9}8t040P71fMc.a49)04e?dOfVfA0L732J1u0jf!6Xc,fR5lfJ0`0M5q045s5!686a6c0ec55#668l0M2-eQfIbTfXfZf7eJ9Vd$1*9$9%fk9kfB6Id-d/0 f-cda1cPd=e}b:c|cw0 0N1Ugkf3218e042/fj2Nf`7rgebIfz8Vghe5d55%eOdbfT0td?e~d^fW2/4~9#fTd.gH7?0Lf=dHgNgdfYgReRgIf8gVeperg!gzeAg(fA9ng`gOfNg/6}g*0mg,d@82fo8Hgs04g;hac-6Xg?cAfWguf/gxfTfHeWgdfLfT9sfEhn0yfQ6+9afT9zbS7j9gf@hG48hfdoehd59Fb.cVhRf%hzhCd}fd9?9X9Z6bfyg{1.99hPh$e|hWegf%hsgwf;hmhMhmh.hWfo87hm7P6 7173fCeQh87aa3hKh57{7ghVdne fAg_fbgi7{d%hC7LgmgS8{cZ7Ri6gqg-hjhlf$8x8OhN8Tipdlh2eVgB8x9 dr0eibdIhy9Pa7bpab2Oao4I4T11ad0+0-0/04.