Cheminement dans un arbre 1

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 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 récursive longueur_ce qui prend en paramètres un dictionnaire représentant un arbre et deux entiers désignant un nœud et une longueur. Cette fonction renvoie la longueur de cheminement externe de l'arbre considéré.

Pour l'appel initial, les arguments passés à la fonction sont l'arbre dont on veut obtenir la longueur de cheminement externe, le numéro du nœud racine et 0 pour la longueur.

Exemples

>>> arbre  = {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]}
>>> longueur_ce(arbre, 0, 0)
12

Évaluations restantes : 10/10

.1280135[tf4)+2r3,sao iug08m1]P6pnl7he=cy:v(wS/b_dk050R0F0d0n0q0C0m0p0H0C0n0m0m0G010d0q0A010406050m0r0v0v0n0j0I040N0o0C0r0-0o0B050O0@0_0{0}0=0A04161d051g0O1g1i1d0=0R0q0K0#0%0)0+0E0q0s0E0C1w0E0d0:050W0P0C0F1r0(0*011v1x1z1x0d1F1H1D0d0P0o0R0}1E0j1e0d0E0#100m0A0n0B0+0i011J1t010e0Y0F0B0n0v0F1D1+1-1=1L1^1H1{1}0:0a0p0y0j0o0A0o0m0q130B0p0U1)0j0j0F0H2i16200B1e0O1%2v0d1#1!1$0R220+1z0B1`2f1D1o1q0$1K2F0q2H0B1X1p1D0A2o1e2t2v2Z0?1,2j2N1?2S0j0`0C0:0w2s2%0;2$212)1L2+2-0:0i2;1-2?2t2E012{0n2.040k2 2u0=322_0+35370f3a312%333g0:0b3j3c3l3e340o2,360:0z3q2@2(1s2`3v2|040D3A3d3D3f3F3x040u3j1f2X162L2y0R2C330H1X1~1e3V1h3T2#172=053!0U2Y3s3L010S0:0U0e3R3K2O010M0:0p3|3=3~0B0e0:0C140s0r0F0r0j0Q0H0F432^3?0/040L4j3C450:0{0P2o4p334m0l3j423}2*0:2S4d0R4w3t4y4A3B3m484a4c4e4I4l0:0g0J3q0p4Y4B441?3^040q3{3,304!4k4r044F0r4H4+2u4-4q1?0o404(154@044_4N044t4v504M4J0:4W50064Z5e523t0B4E0^0Q0t4S3~4K505g3?5i4:5k2:5q583?0o0:0G4L4C2`4s0j4u4i575E0+4m0c5n4D4:0o4G5P1L4m0x4X5f4Y5y4/490B4b4d4f5m5x5L015A045C5-4#5F045%5)4e4g5J2#5.4m4o5K5@3f5G5I5U5M0:4z5?4.5Q0B5k5,5 64015p2Z5r5$4P5*5D6j5:0h6r6d1L0v0q2/686k4U5Y5Z5#5Q5`4Q4f5w6m6G1L5:5=6M5.5t6I5*5}6B616B5t555~3-606a6v4`5^6f0v0Q6L6%6j6l2=6n6H6p4R6c6+0+6t6*336y6A636w69040g6E5f6N0+4%2o0d4e4 6R6j6T6`5+703t6 6|536U5|6:305d4Z7b3@0:0F0Z6$307y4m5b2Z7w6F5.7d0V7g7n5s4O5(6J3A0O3/0F2v2W7X3U1p3W2y2A2w1W1Y2y0n1G7!0O3V0=7;0V0X0Z04.

2. 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 récursive longueur_ce_ponderee qui prend en paramètres un dictionnaire représentant un arbre, un autre donnant les poids des nœuds externes et deux entiers donnant le numéro du nœud racine et une longueur. Cette fonction 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

Évaluations restantes : 10/10

.1280135[tf4)+2rR3,sao iug0x8m1]P6p*nl7h.e=cLéy:v(Hwq;S/b_dk050!0J0d0o0r0F0n0q0L0F0o0n0n0K010d0r0C010406050n0s0x0x0o0j0O040W0p0F0s0_0p0E0q020o0x0C0V0q0k0J130j0U0s0J0n050X101214160~0C041u1B051E0X1E1G1B0~0!0r0Q0.0:0=0@0H0r0t0H0F1U0H0d0|050)0Y0F0J1P0;0?011T1V1X1V0d1%1)1#0d0Y0p0!161$0j1C0d0H0.190n0C0o0E0@0i011+1R010e0+0J0E1h0J1#26282d1-2g1)2j0x2l040a0q0A0j0p0C0p0n0r1c1e0%240j0j0J0L2G1u2n0E1C0X222S0d201 210!2p0@1X0E2i2D1#1M1O0/1,2$0r2(0E1|1N1#0C2L1C2Q2S2}0 271e2.2e2?0j130F0|0y2P310}302o331-35370|0i3b283d2Q2#013i0o38040l3m2R0~3p3g0@3s3u0f3x3o313q3D0|0b3G3z3I3B3r0p363t0|0B3N3e321Q3h3S3j040G3X3A3!3C3$3U040w3G1D2{1u2,2V0!2Z3q0L1|2v0$1N1C2`0J2|3c3=3~0%463f3,010#0|0%0e3=3+2/010T0|0q4j3P4d0E0e0|0F1d0t1r0s0j0Z0L0J0Z2C0E0%2L0J4q4c4l0{040R4L3Z4l0E0|140Y2L4R3q4O0m3G4p4k340|2C0r0!1t1v474)1-4#4%3Y3J0|2?0J0s0!4Z3Q4@4:3n4(4r4T4v4x4z0j504d4O0g0P3N0q5i554M2e4f040r4i532R5k4S4*044|4~4^4=0@0p4n5o0E5z565v4W4Y5r4b5u4?0|5g5L065j5T5t4`5w110Z0u5c4N0|4$5L5V3Q4U5X0x0Z3a5)4_3Q0p0|0K5G5l3h4V0j4X4K5L5=5d0|0c5#5v5x4 615A014O0z5h5U5i6257044w0E4y4}4B5!5;6b5@045_6r5H5|6k596o4C4E4G4I0J602 6b4O4Q6a6x3C5}5 665O045(2}5*4s4+0p4-4/6I6N6c5%5`5N6O5-5Z6R0@526V6i5v6l6n4A6*3q6t0h6{3Q0x0r396/6(040g6f6g6?6y6^5a5/6 4d6t6v6=6b5,7c6B4D4F1d6F6H4;6%6K745,5J7s3n7a6:6)6w5{6,4,4.746;3c6W6j0E5Y5:6$7F756U7L7B3r586m5a7f4l6}7#2e71736M7S5e785U7W5n2L0d4A5F7E6+7X6z7Z6B6q7j6%7%7`5W7m4A7e5R5T7;0|0J0,7z2R7W4O5Q2}5S6g7M5m0|7?7^7(7b6A6`845?0|0D8s7G6Z7I7,7{4O658E5W687J0|6e5R1u49453?8R0X3_1u0d3{8W2X2T1{1}2V0o1(8T3_1A5M3q2L5.0e0o0#4E0H0l0|1m1o1q1s0q8j471H3d1B0M003t0t3S2F0H2u0q2I0S0s0e0e130E1e0C0J360(9e1*2W0p0s0Q9o0q0s1e7y0q1q0r0q0o0q0:9H8u0j9r0.0H1n2;0-0J0v0d9o2(0q6E0N0j0N1*710E0r370J0I1D3d8U0(0*0,04.

3. Longueur de cheminement interne

On s'intéresse enfin à 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é au début de l'exercice, cette longueur vaut $1+1+2=4$.

Écrire une fonction récursive longueur_ci qui prend en paramètres un dictionnaire représentant un arbre et deux entiers désignant un nœud et une longueur. Cette fonction 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

Évaluations restantes : 10/10

.1280135[tf4)+2r3,sao iug08m1]P6pnl7he=cy:v(wS/b_dk050R0F0d0n0q0C0m0p0H0C0n0m0m0G010d0q0A010406050m0r0v0v0n0j0I040N0o0C0r0-0o0B050O0@0_0{0}0=0A04161d051g0O1g1i1d0=0R0q0K0#0%0)0+0E0q0s0E0C1w0E0d0:050W0P0C0F1r0(0*011v1x1z1x0d1F1H1D0d0P0o0R0}1E0j1e0d0E0#100m0A0n0B0+0i011J1t010e0Y0F0B0n0v0F1D1+1-1=1L1^1H1{1}0:0a0p0y0j0o0A0o0m0q130B0p0U1)0j0j0F0H2i16200B1e0O1%2v0d1#1!1$0R220+1z0B1`2f1D1o1q0$1K2F0q2H0B1X1p1D0A2o1e2t2v2Z0?1,2j2N1?2S0j0`0C0:0w2s2%0;2$212)1L2+2-0:0i2;1-2?2t2E012{0n2.040k2 2u0=322_0+35370f3a312%333g0:0b3j3c3l3e340o2,360:0z3q2@2(1s2`3v2|040D3A3d3D3f3F3x040u3j1f2X162L2y0R2C330H1X1~1e3V1h3T2#172=053!0U2Y3s3L010S0:0U0e3R3K2O010M0:0p3|3=3~0B0e0:0C140s0r0F0r0j0Q0H0q432^3?0/040L4j3C450:0{0P2o4p334m0l3j423}2*0:2S4d0R4w3t4y4A3B3m484a4c4e4I4l0:0g0J3q0p4Y4B441?3^040q3{3,304!4k4r044F0r4H4+2u4-4q1?0o404(154@044_4N044t4v504M4J0:4W50064Z5e523t0B4E0^0Q0t4S3~4K505g3?5i4:5k2:5q583?0o0:0G4L4C2`4s0j4u0F5n1?4m0c5K5F4:0o4G5O0+4m0x4X5f4Y5y4/490B4b4d4f5m5x5E0+5A045C5,4#5P5$5(4e4g4i575-014m4o5}5?3f5G5I5T5 0:4z5=4.4D5u0v5l675p2Z5r5#4P5)5D63015/0h6o6c1L0v0q2/6h4U5X5Y5!6d5^4Q4f5w6j6D1L5/5;6J5~5t6F5)5{6z4n675t555J626u5U696t4`5P0B5v6U6a6O6p6Q6m4R6b6)5.0:6s6@336w6y6!6^68040g6B5f6K0+4%2o0d4e4 6/6#344O5%6G6(336r7k5h7h5_5*7n5z6`7s6l7i6S6I2=5d4Z773@0:0F0Z6Z2#5~4m5b2Z7B6C5~790V7c7v1?6~045+7N163/0F2v2W7$3U1p3W2y2A2w1W1Y2y0n1G7)0O3V0=7_0V0X0Z04.