Cheminement dans un arbre 2
On considère dans cet exercice des arbres enracinés dans lesquels chaque nœud a soit deux enfants (c'est un nœud interne), soit aucun (c'est un nœud externe).
L'illustration ci-dessous présente un tel arbre. Les nœuds internes sont représentés par des cercles, les nœuds externes par des carrés.
Afin de représenter les arbres en machine on numérote les nœuds dans un ordre quelconque. Cette étape étant réalisée, on peut représenter les arbres en machine par des listes d'adjacences (des dictionnaires avec Python) dont les clés sont les numéros des nœuds internes et les valeurs associées une liste contenant les numéros de leurs deux enfants.
L'arbre dessiné ci-dessus est représenté par le dictionnaire {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]}. Les nœuds externes de numéros 4, 5, 6, 7 et 8 ne sont pas des clés du dictionnaire.
Pour calculer les longueurs présentées dans la suite, on utilise des parcours en profondeur.
1. Longueur de cheminement interne
On s'intéresse à la longueur de cheminement interne qui est la somme des longueurs de tous les chemins allant de la racine à un nœud interne. Pour l'arbre dessiné plus haut, cette longueur vaut \(1+1+2=4\).
Écrire une fonction itérative longueur_ci qui prend en paramètre un dictionnaire représentant un arbre et renvoie la longueur de cheminement interne de l'arbre considéré.
Exemples
>>> arbre = {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]}
>>> longueur_ci(arbre, 0, 0)
4
>>> arbre = {2: [0, 1]}
>>> longueur_ci(arbre)
0
>>> arbre = {3: [0, 1], 4: [2, 3]}
>>> longueur_ci(arbre)
1
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
.128013 s3o_;8bcdufvgx/0lyq n7apS.r1Lmeh,(P2=4:}+Ntwki9][5RE{)é6 050j0F0R0x0U0r0b0u0i0r0x0b0b0L010R0U0y010406050b0k0E0E0x0B0s040z0d0r0k0|0d0v0u020x0E0y0f0u0Z0F160B0t0k0F0b050p13151719110y041x1E051H0p1H1J1E110j0U0m0;0?0^0`0G0U0n0G0r1X0G0R0 050,0h0r0F1S0@0_011W1Y1!1Y0R1*1,1(0R0h0d0j191)0B1F0R0G0;1c0b0y0x0v0`0K011.1U010l0.0F0v1k0F1(292b2g1:2j1,2m0E2o040a0u0J0B0d0y0d0b0U1f1h0*270B0B0F0i2J1x2q0v1F0p252V0R2322240j2s0`1!0v2l2G1(1P1R0=1/2)0U2+0v1 1Q1(0y2O1F2T2V30122a1h2;2h2_0B160r0 0u0C2S3410332r361:383a3c0K3f2b3h2T2(013m0x3b040u0c3q2U113t3k0`3w3y0u0M3C3s343u3I3c0Y3M3E3O3G3v0d393x3c0(3T3i351T3l3Y3n3z0w3%3F3*3H3,3!3z0g3:3V3=3X3Z3J0V3{3j3}3Q040C0q3M1G2~1x2/2Y0j2$3u0i1 2y0)1Q1F2}0F2 3g494i0*4q432=010T0 0*0l493;4x0S3c4D3|4x0v0l0 0r1g0n1u0k0B0e0i0U4I4w2h0~040I4X3)4K0 170h2O4%3u4!0$0N3T0u4@0u3(3P0 2l0l2b0R0b0e2@0R0F0B2+1w1y3g4_4E2h0d0 0L3M5b4J4Z0 0#4.3W0v0 0v5n3}4!4=593r5i4Y3l0 0B5h4`3W4z040l3Y5D5c5A045C5w2U5y4(5d4G042@5K5j5M4+4-5P3z5E3}5G5I5O305R4{045r5$5.3W0d5U5W5=5(4)045!0F5s4x4!0X61375B651:4!0W5X5z0`5G0U4C5{5L3H5q6c5S1:5^0 5`5-5|665~0B4,605$6t690 0O4?4^6A6k044O0v4Q0F4S6m3u5e045g6i5Y0`0E0U0 485$064^5?5)0 5+6O5o6l6T6d016p5V5;6s6j3v4|4L4 51535557680`5u6E6$4@6G6_042}0d5I0v0*6N6.6n0`6Q6S6@6U016W0 3e6!756F6^5G0S1W1,6+446`4~0v50527D6 1v7101637J5p5:7J6a7z4x6;6r5a777N4}6|7F54567I6z6^737r7s757W0 7a7c7e5,7V6^7j7R6u7:1g7=7`6o0 0P7 6V6X46747,766^7N6?7@7m7_7g5/7Y7D6}7G7$58327)0 647(7m8b7P0 6b7+7s7.6I4P4R7?5x778f7l6/7N6J6L7f8I7h6:8183787|7d6M8E3D6$775G2O0R4S8c8F8a4N8C8W3%0p4t4p4a8=0p4d1x0R4f8`2!2W1~202Y0x1+8@4d1D4v8P2O0E0e4~0T0F0e0G0c0 1p1r1t1v0u5v321K3h1E0D0x0u7c2Q0U1g0u0j1g0v0%1-0j2b0:1,2M0B1X0%0u1v0R0u2H1l9K160U0:0y6M9P0l2j0i0x0i0F0A1G9s040J0d4S0u0%0i9M2O0u0k2+0u0m552H9A0F9$0U9(9*0H0u9A4i152l9*0u2a0B9B0%7#6W2+ah0?0u0B9)2@1-0y0k9Xa91ha30l2P8%1-9|af174i4S0:2L0r005 9,9r970!0o1q0y9K0x9 0i9{1hagaH0B0:2laf2D7;8W5v1N4l2:3}1=1Z1#1%983u2u2l2n0 2A0z9^0}9R0J0s251g494o98314r8;a`5F4Aa37J5U4_8s8J4M8B6K8D4U4Wbm8P4!4$bu5/5 8v044;878Aaq4V2+8S8H8d6/0T0i0 0Q1g6y306#7t8t7B7Z6~8mbJ5f8S4!5mby6,7Ob*5t0 9pbL8P7N8X5%7u6)5J8gb+b@6%7S5_8)5Q8AbAb|6(5Hb{8O5/c2b^8ec18S7Nc58o7m7Lb-5}b@777Qc64x6f6hcab+ccb 5T6qcxc46w5#cj6/4!6D8ycy1:5*c9b;cbbJcfcr6uci4r8p04b:3rbU8zb_5VcucOcwcQ5q0d0Rc+6=cgbX8j7!7H8ncVckb/8788bFarbIcS806Rc;b,bT8Zc$6gd5bGasc/9X8SbNbPbRbBcY8Y7,8!5B0+8(8S7o046Zd7bV8J8,bq8.d27ib$dC7n85dv3gc!cK6H0y2kb#d4dF63bxcFb=5Bd0bSc`cG0 0HdsdHbB0$8xdw897m7v7xdY8*bW79dOcm5kcXc}dxdV5:0d6M0jbBd$dF7N8U7~dFbKd=dyd@7yd_d3aOdU5/2F0ybB0I0$d|d-bM6qc(ebd~2_e1decB8+6v6xdkep7-eA8L8DdP7kc)7Abp8Mb~8G8Re57/a+7}dB5-4^dKc~c$6*eS048ic.e9cRcveMcU3rcp8q7Mc,exef728wdl1088e!d?dNeeei5@0 ehdZd~0x0y9Z7demdTf78h6{7De3d5e7eWfff40482e_dG7pd)eocJdo5Ndq56d5eHfmcZ1xbe8?2V964c0+0-0/04.
2. Longueur de cheminement externe
On s'intéresse à la longueur de cheminement externe qui est la somme des longueurs de tous les chemins allant de la racine à un nœud externe. Pour l'arbre dessiné plus haut, cette longueur vaut \(2+2+2+3+3=12\).
Écrire une fonction itérative longueur_ce qui prend en paramètre un dictionnaire représentant un arbre et renvoie la longueur de cheminement externe de l'arbre considéré.
Exemples
>>> arbre = {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]}
>>> longueur_ce(arbre, 0, 0)
12
>>> arbre = {2: [0, 1]}
>>> longueur_ce(arbre)
2
>>> arbre = {3: [0, 1], 4: [2, 3]}
>>> longueur_ce(arbre)
5
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 s3o_;8bcdufvg/0lyq n7apS.r1Lmeh,(P2=4:}+Ntwk{i9][5REx)é6 050j0E0Q0w0U0q0b0t0i0q0w0b0b0K010Q0U0x010406050b0k0D0D0w0A0r040y0d0q0k0|0d0u0t020w0D0x0f0t0Z0E160A0s0k0E0b050o13151719110x041x1E051H0o1H1J1E110j0U0m0;0?0^0`0F0U0n0F0q1X0F0Q0 050,0h0q0E1S0@0_011W1Y1!1Y0Q1*1,1(0Q0h0d0j191)0A1F0Q0F0;1c0b0x0w0u0`0J011.1U010l0.0E0u1k0E1(292b2g1:2j1,2m0D2o040a0t0I0A0d0x0d0b0U1f1h0*270A0A0E0i2J1x2q0u1F0o252V0Q2322240j2s0`1!0u2l2G1(1P1R0=1/2)0U2+0u1 1Q1(0x2O1F2T2V30122a1h2;2h2_0A160q0 0t0B2S3410332r361:383a3c0J3f2b3h2T2(013m0w3b040t0c3q2U113t3k0`3w3y0t0L3C3s343u3I3c0Y3M3E3O3G3v0d393x3c0(3T3i351T3l3Y3n3z0v3%3F3*3H3,3!3z0g3:3V3=3X3Z3J0V3{3j3}3Q040B0p423)2=3~3-0B3e1y3g3U434b450B3p4g3r4i4a373@3y0B3B4o3D3(3P4t0 0B3L4x2V2}0E2V2/2Y0j2$3u0i1 2y0)1Q1F4H2 3g3M054P0*4W4j2h0S0 0*0l4Y3;4b0R3c4-3|4k0l0 0q1g0n1u0k0A0e0i0E4=4%1:0~040H534r3l0 170h2O593u560$0M3T0t5m0t4z3W0u0 0E0#0Q0E0A2+1w4F5o4.2h0d0 0K3M5B4?2h560T5g5q0 0u5N3}565k5A5p440 0A5H5W4b4)040l3Y5!5C5b045Z5V5,0`0d4:042@5+5J5-5d5f5:5{0`5%5)5/305I543H5P5`67015?0 5_5 6b5r045}524F5#5K0 0X5R4k5Y6r6o040W6a5a616e4,6g6z3v696D3u6d042_0Q6y6I5@6f656n5|0A5e6l325;01560N5l5n6S685^0u5v5x1v6N3W5E045G6H3W5L6u5-5Q6m6Y5T6/5X5.705$0 6373376t6@3}6J6Q3g666E6i6k771:625*7a6s6K7j5=6P6|6R6Y7h6U5~6X606Z6p6`6)644X6~0 6x7n4(6B7q6F7p7K1:7c7t7e6(7O7i6}7A6!6$5m7V6i4`0u4|0E4~7N6;6?7u7A0D0U0 484F065n7f3u7l7F3r7}5O7P7;6b7S7N6i5t6,5y7D7B045U307{7|6%7v6G856E7/885s5u5w8c7Y6b566q8v7g8m7G7Z7I7#8j7%0 2}0d5)0u0*7-7Q5=5F7N7?4C8F7|7V5%0U6C8n3P8B817V878P7O2@8b6.8z5h0 8g4h8j8^823}5%0R1W1,8q6*8.5z7z8w7C8:837T3r7V567J8#6:7s908-8t8/946E6 7`8_9p8`7o992U9r5D8R8+6i9i6-938C95048y9l8$849D9m8E9o9q8^8H048J8L8N809u8)9x9e719S1g9U7.0 0O8S7@468V8_9Q9#8M7,9V3z9X6=909;9%8+6;9*8+8T9-9N9P8l047)7+8O9Z4b8p9y4_4{4}9@9v7R9)9{2D9T9?8F8X5Y0+4~9t9^a6a8ah3%0o4!4I1G2~1x4K1x0Q4MaI2!2W1~202Y0w1+aD0o4K1D4$6E2O0D0e0l0w0S0E0e0F0c0 1p1r1t1v0t8?9a1K3h1E0C0w0t8L2Q0U1g0t0j1g0u0%1-0j2b0:1,2M0A1X0%0t1v0Q0t2H1lbb160U0:0x7,bg0l2j0i0w510z1Ga_040I0d4~0t0%0ibd2O0t0k2+0t0m5w2Hb10Ebt0Ubv510G0tb14P152l510t2a0Ab20%6,7?2+b*0?0t0Abw2@1-0x0kbobY1hbS0l2P0Q1ubK1hb)4P4~0:2L0q006kbya^aW0!0#1q0xbb0wbO0ic4b(17c70A0:2lb(an9$9?5U1N4S2:3}1=1Z1#1%aX3u2u2l2n0 2A0ybH0}bi0I0r251g4Y4V3(314XaCcJ3W5%4+8d5@5o97444^a7ag9?506W9K8;578d7w6V8d5ia?3D8Wa6b?0ib^9(9`8+0S0i0 0P1gc_4pd47A890ua$6+0b0e9A8uab9wdadt550 5Mc/9sd08=90aiar5(7mdw7E7.9gae6j7xdh9W6Y7 90avaj7r6edV9Q7X9H6^96d$719@9b9MdJ018Y8!7Ua6dZ6Y8*d.c~7yc`d%046#a4dWd/75dId=dk8%dR7Ad_e66h5cdPdC8f9.7$dS7MdNd@ea5@6LdLdY902ldn0Qdpdr9kd}5SdDe19p9Qd6d89~9Yec8A9Jdi8k7Ad:dEb@2+er5^9C8(dSdd04dfeTdA6vd210eEek5.at5x9+7^aqaxc?aaeK6IeJeX7=9,7_8hdjed9R2kd97:e_d~0X58e%5-eGe$d)4b560Ge:04e eAfg0 0$9d8@eO6b8|8~dQawe7f38 fb0`9nf09/d?0d7,0jegfidN9|apeIdvf79!f4fB6c0 ceff789R2Eeg0H0$eie2eQemfH0kfJ9~dMd`eec fUfD7e5m8i9OdG76dNeu2b6Mf:esdNd#fm6v9Gg86{f-f/fYdx6we)f|9OfseL0xfTgf8Q04fXgb6)0w0xbq8Mf$fagp7Og16+fKam8Kcye^9ad^alfUa24fgB5if(eDgl7~5s0/fwd,ehgTa5fyayfOd.adf=c=7*azfPa0g,fNgJd3gUc)asc2e/dNg(g@3haB4Q4GaFaU4T11aU0+0-0/04.
3. Longueur de cheminement externe pondérée
On affecte désormais un poids à chaque nœud externe. Les différents poids sont donnés par un dictionnaire {numéro_du_noeud_externe: poids}.
On s'intéresse à la longueur de cheminement externe pondérée qui est la somme des longueurs de tous les chemins allant de la racine à un nœud externe, chaque chemin étant pondéré (multiplié) par le poids affecté au nœud externe correspondant.
Considérons par exemple les deux arbres ci-dessous :
Pour l'arbre à gauche, on obtient \(2\times4 +2\times1+2\times9+2\times2= 32\). Pour celui à droite \(1\times9+2\times4+3\times1 +3\times2=26\) .
Écrire une fonction itérative longueur_ce_ponderee qui prend en paramètres un dictionnaire représentant un arbre et un dictionnaire donnant les poids des nœuds externes et qui renvoie la longueur de cheminement externe pondérée de l'arbre considéré.
Exemples
>>> arbre = {0: [1, 2], 1: [3, 4], 2: [5, 6]}
>>> poids = {3: 4, 4: 1, 5: 9, 6: 2}
>>> longueur_ce_ponderee(arbre, poids, 0, 0)
32
>>> arbre = {2: [0, 1]}
>>> poids = {0: 4, 1: 7}
>>> longueur_ce_ponderee(arbre, poids)
11
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 sH3_8ufvy n7aS1me(P24:twi][hE*)6o;bcdgx/0lqp.rL,}=+Nk95R{é 050L0r0x0n0z0Q0b0k0K0Q0n0b0b0Y010x0z0S010406050b0g0q0q0n0U0j040o0H0Q0g0~0H0l0k020n0q0S0I0k0(0r180U0R0g0r0b050O1517191b130S041z1G051J0O1J1L1G130L0z0i0?0^0`0|0C0z0M0C0Q1Z0C0x11050.0J0Q0r1U0_0{011Y1!1$1!0x1,1.1*0x0J0H0L1b1+0U1H0x0C0?1e0b0S0n0l0|0u011:1W010h0:0r0l1m0r1*2b2d2i1=2l1.2o0q2q040a0k0t0U0H0S0H0b0z1h1j0,290U0U0r0K2L1z2s0l1H0O272X0x2524260L2u0|1$0l2n2I1*1R1T0@1;2+0z2-0l211S1*0S2Q1H2V2X32142c1j2?2j2{0U180Q110k0p2U3612352t381=3a3c3e0u3h2d3j2V2*013o0n3d040k0d3s2W133v3m0|3y3A0k0v3E3u363w3K3e0%3O3G3Q3I3x0H3b3z3e0G3V3k371V3n3!3p3B0m3)3H3,3J3.3$3B0f3=3X3@3Z3#3L0$3}3l3 3S040p0P443+2@403/0p3g1A3i3W454d470p3r4i3t4k4c393_3A0p3D4q3F3*3R4v110p3N4z3P4l4u414E3U4H1I301z2;2!0L2(3w0K212A0+1S1H2 0r313i3O054X0,4)4J1=0#110,0h4+3?4d0y3e4_3~4m0h110Q1i0M1w0g0U0e0K0r0e2H0l0,2Q0r4~4:0|10040s5i4t3n11190J2Q5o3w5l0W3O0k4B3Y0l112H0z0L1y4O4`2j5l0F0w3V0k5Q5A5K5q040r0N0x0r0U2-5I325S4 2j0H110Y5z5B3 5l0)5v5C110l5?5:115O4H5(5j3x110U5.5T0|4=040h3!645)5U635~5/4d0H4|042_6b605D045s5u6f650167696e5%6g395^6m5p0|6i116l6s6c3J5r0U5t5h5J6J015l0B5`4m626U5L110A6C3w670z4^6I6n6B6*6D016F042{0x6#3Y6:6H6y6t6o6q6O346t5l0X5P5R6z5U2_5Y5!1x6@3 5+045-6-5w115=6P6+6;6X1=5l5}6{6Q6o6x3i5 6.6v6a7h5@047v3t7x3w6_5_7B466L6N7c4d7z7E2W7G7C7J7s607I7O6A6p6M6r706Q6S7o6K7D7+6R6Z7Z4;6G6)7W6.6o7V7w766E6j6`7|6|7M7%4*7111734H065R7T7L04530l550r577;6E5,8k010q0z114a898b7}6u116w8n7`8n7Y7K6V5V5X5Z5#7.7q748b5Q8v7`0H8i0L0e5W792-8B8m8D7!7{4r8M75827n8Z1=7e7g7^3R118U8H7b7l6.7*8^8:8*7(605l6!8t8%8c8E2 0H695e8i7R3B8v8-8n8p4E8L8M8v6%7@817t6,8/6^7 8#7S8O6G0l8V8@8~8_5|9i93942j670y1Y1.8z9w9y5$857)116T8{7U8J7:8+7~9w9L6k9x8?9O3t8v8K929E8%9v8}9n7X8Y9q8d789%9V049S9A8|9t4/9B0491328a9-9.8)96980,8j9X6/9?9;7_5E2Fab9a8X040Z9f8q489D939/aa1iac9b9F8,ag7Favakaxamae7eapae9gas9,9j8)8f8had9@6haC9uaQ5456az9d11aKaU7!aw99aTah7H110E9!5F5H9{9}9P7m2{8R8T8G7a9{a44j8u6t672Q0x57a0aA7,aRa!3)0O4-4(4Pbi0O4S1z0x4Ubn2$2Y20222!0n1-bk4S1Fa13w2Q0q0e0h0n0#5b0C0d111r1t1v1x0k7r4*1M3j1G0V0n0k982S0z1i0k0L1i0l0*1/0L2d0=1.2O0U1Z0*0k1x0x0k2J1nb;180z0=0S8ib_0h2l0K0n5a0T1IbV040t0H570k0*0Kb?2Q0k0g2-0k0i5Z2Jb%0rc60zc85a0W0kb%4X172n5a0k2c0Ub(0*798p2-cJ0^0k0Uc92_1/0S0gc1cB1jcv0h2Rb81/cocH194X570=2N0Q006~cbbUbA0D0N1s0Sb;0ncr0Kcn1jcIc-0U0=2ncHaFa,0U5}1P4!2=3 1@1#1%1)bB3Y2w2n2p112C0ock0 b{0t0j271i4+4%a1334*bhdm3 674@7.6j5A9T46518eaZ9a595b5d5f0r6 a`a25ndO8E6~9{5yae6oa?9(2W9*115N9i9/cS0KcUan8.a.3Y0#0K110!1idZ8$8(9o5V0lbG9x0b0e9_7ad/9c6t9eae5;7.8Ad%6Y04bSaD8)a#b58x7Aa)6d8B9s9!d)ae7Q9!ba9deCd,83e5d:869|en6Wep7p9Wez667?eHeB9ZeL7#7NeT5k87d@ew68eyd~8deIejeKeW61e%849)ePes3F9E9keYe$e=6Q6:6=e!9#9!2neb0xedef8Ie)7/erata8e8d_d{aIaWeie8a0a68Ne-6(9!fn8WaI7 ehbb6ue104e3fA9~3Y9+a5f0e-b7b9aq8re,e8bdaHe^eke^aM8sfNe77m0S2md|8n6Sd$fK8dfzeNdH4d5xfS04f$d!7i040Fb2e6fv6Q9H9Jf?fEd-f+fhfMb3au8)a|0g0Ld*a=daayf,e$f*9Kfh7ec@f:952G9{0s0FfkfE9leH8Qghf880ete8eEgueqe~3B5Qfu9-f1e.eve8fb2d6?fBe#e^6}7$f?d;eQfh8P8Rb1gNgQa7g3f)gagLaB04gtf}7C0n0Sc35egxf/g|8dgW9xgjgoglfXh4aVao7.aM4hg^e*f gzaOb4g48;0;g(e}gAhn7mfWa-gI9=7f9!hwgUhza(e:95hahxaXf5a:a=0H5Gehg)a_e|fsgEgigbeVgdg=7y620-fRe$hCbfdGbj2Xbz1K040Vc=0Q0M3!2K0C2zb(1/0c0gc6180ld35Z2zb{2N2#cgcrcJc*6~0k1v0z0kbYcQhCh}0?0C1s2_d7a cpdW0*0Ub,0kcN0z3c0rc@debl0-0/0;04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)