Copie profonde d'arbre

🏷️ On considère ici des arbres étiquetés.

Une mauvaise copie

On considère le code suivant

🐍 Script Python

A = [1, [[2, []], [3, []] ]]
B = A  # copie superficielle

A[0] = 9  # on modifie A
assert A == [9, [[2, []], [3, []] ]]
# Aucune erreur, c'est normal !!!
assert B == A
# Aucune erreur, ça peut choquer !!!

Ce code ne provoque aucune erreur, alors qu'on a modifié l'arbre A... En effet, les arbres A et B possèdent la même référence vers une liste (qui contient elle-même des références à des listes). Modifier une racine ou un sous-arbre de l'un aura un impact sur l'autre ! A et B représentent le même objet en Python, deux variables pointent vers le même objet.

C'est un phénomène bien connu ; la copie est superficielle. Même si on créait une nouvelle liste pour la racine, il faudrait aussi créer de nouvelles listes pour chaque branche !

Copie profonde

On souhaite avoir une copie profonde, réellement pour chaque branche, et donc indépendante de l'originale.

Exercice

Coder une fonction copie qui prend un arbre étiqueté en paramètre et qui renvoie un arbre de structure identique, avec les mêmes étiquettes. Cette copie doit être profonde, afin d'assurer l'indépendance totale des deux objets.

Évaluations restantes : ∞/∞

.128013]x,5/f.q!7r;nb _o=ylaeêpcwgu)vdV4613kRAméhtsP(Sà02è[-i:050F0w0R0v0$0u0S0p0z0u0v0S0S0s010R0$0y010406050S0C0O0O0v0l0t040V0r0u0C0{0r0n0p020v0O0y0m0p0M0w150l0i0C0w0S050f12141618100y04051D1w1G0f1D100F0$0E0:0=0@0_0Q0$0B0Q0u1U0Q0R0~050+0o0u0w1P0?0^011T1V1X1V0R1%1)1#0R0l1E0R0Q1+1R010g0-0w0n1j0w010:1b0S0y0v0n0_0Y1#2b2d1 1-221)250O27040a0p0T0l0r0y0r0S0$1e1g0)290l0l0w0z2B1w2i0n1E0f1}2N1`1|1{1$0F2k0_1X0n242y1#1M1O0;1,2X0$2Z0n0r2%1#0y2G1E2L2N2^112c1g2)202.0l150u0~0J2K2|0 2{2j2~1-30320~0Y362d382L2W013d0v33040K3h2M103k3b0_3n3p0H3s3j2|3l3y0~0e3B3u3D3w3m0r313o0~0I3I392}1Q3c3N3e040k3B1H2?1w2%2Q0F1|2V3L0z2/2q0(1N1E2=0w2@373#3/0)3`3a3V0_0L0~0)0g3#3v41010A0~0p473K490n0g0~3/0y0$0w4e402*010}040U4o3U4q0n0~160o2G4v3l4s0D0%3I0p4J4d484q0S2g04011o0n0E0r4m0p0C1g2.0C0E0w0u0p4A2G0d0p0S0v294l1*2=0r0g1f0)014I4K3T3E0~0l0v0z2,4n1x3{4M204s0d3B4L4f4x0~240g2d0R1v563i5d4p200r0~0s5c4~3L4y044*552^064K5o4w2 0~4!4$0v0C0c5u581-5r045t5m2M5E4E0~0!0b4|4J5v4943044^0l5N5e5G040S0r0C0S0q5z5,5p5P4b042,5_5F3c5g4h5j5l2`5O0_4s4H5T0 5D5D5$5f045I0w5K5M6b6f5q0~0h4D5w4z0y0y240F6r494s4u6m673m4j2w4m6y4q6A6I5.5:5=5@0l4B5A575-1-4F0D5!5V3L5(2G0R0C0l0n5 5W040!6L610451532Z6/680~5b6b6Z4g5H5;5J5L6^4r0~5Z6b100f3}3_3$7b0f3)1w0R3+7g2T2O0v1(7d3)1C3 600_2G0O0q5i0L0w0q0Q0K0~1o1q1s1u0p6a2`1J382%3l0v0F0O1f2A0$1f0p0{4s1C7O7Q7S2B0#0{0R1^190R0t1)4X1g6v0C0p4^0n2I7U0n2Z0u1H381D0N4$0z7:1*1X0S0R1*24291k0l0P0Q242z1f4,0z001u0R7W0l0Z0/2)0$0l0p0*0p2G3/1z0n0F0P6q7L1L1N3l1/1W1Y1!7r3l2m24260~2s0V0z0l0|8o0T0t1}1f3#3^7r2_3{7a8O6!440w466C6U0_5|4d8?5`3x4i044k6H8{7s744t735x5^926,4G6Y6n1-4O0~4R244U4W4Y0p6i4(5z4,4.4:4W4?7^4`9c6D5x6=54735a6+6s045h649E495Q5S2^6}6g985B6e6D6#0*6(6*6|9d6_6-9650529B993L9D9Y6D4s6.776d4}9y6F4;9C0~6B668@6E5/5;5?9Q6T8|946X9-9~5(5*9J6g6Na26Q4Ca8a50r5|5~ai935x9H0n5k9x9~4s0b765B1w8-7c2N7p3(3?1L0*0,0.3l0F2d0B0w0l0~3u131q180GaO8i1g0w0c1`0x2p2KaS1A80040T5;8v0z0w5L0p1s0$0p152A8X0S248o7/887.1*7^7`1f7}4)830p0=7@1fb51g058-150yaz3:2N1K3=2(498K1;1Z2h9~8Q2o2q8U8W8Y2t8#0Q8%6m8)3T8+3ibgbl9Z015(45738_968~906SbK9.9{9$5yagbW2MbN4F7J375C9?9~9f4Q4S9j864/bV0p2D0u005z4{9;b.a59z9(6@9*6z6`ac5.aqasan3l9Lc96:a33ib-5#9T509V6)cg9!9:9}c29%6?b%8.c7046{9NbN0n0o0~870R9`95c64xcF04bicJ9|a4ao9^91ct939,cC9@9G63ar65cS9a0Daxb,bk3~aBaE0E380C0u381X1Ebh0vbj79bl4)6u1X7Gba4/b42B4d8-bVc.3_0p0W0:0Q0vd4ae0#5zb`b@ba0$881*bL3~cb5laA0fc`10c`a:a?0Ca^4?0FdE8o9l2A0P51896(6{dz05c`d4b|7V1`2d0S5*2p8w1gcH0w8FdR0fc@a+aV0laX0/df4?0SbA2Gd$0pdG0Cbe0p0j7 8Hbp4qbr8Mbua5bw8S2r0p8V8X0y8ZbDbF2`bH7K2`aA6D0z0J0~032ta.ba1*8D224,4Y1*a}c@861U2Z0p0U8l8nd|a;8c2=8f8h0$7ne00j0ja7aycm04bQcL20bSe$3cbU6Gcxb)bZe)3x4zb$cJ9bcd8/6;co9XcZau5Xb!cib(bY9#e:010O0$0~0XcJ0bcB379O2 cNcHcQ96cNcPf66Kf65xdbfoc8e_6~b#6RcJcsc)3Lf834fc0Dc+3I3Ja5eqeseu6(ew0/0B1b0ga;d:eIeK880p0-87eS7/eVeW3Sc!fscWce5s735(0=0O0oaLcq9 0vcJb+5ne.f5f-9Ff{ftg0fB49fD04fbg4fdf_cEcGdqcIg4cRbX9~gecOc}fkfqcUe-f4fef~c!g3g1czfAgka5g835gbfGc,cjdcbm3%7eaF3(aH0-0S387egP0.04.