Reconstruction d'un arbre

Dans cet exercice, on considère des arbres étiquetés avec des étiquettes distinctes. Ainsi, quitte à les numéroter, on peut supposer que les étiquettes d'un arbre sont les entiers de 1 à n où n est la taille de l'arbre.

Reconstruction d'après deux parcours

Pour un arbre enraciné avec des étiquettes distinctes, il est possible de reconstruire l'arbre avec les seules connaissances du parcours en profondeur préfixe et du parcours en profondeur suffixe.

Exemple

graph TB
    R(6)
    S1(5)
    S2(7)
    S3(4)
    R --> S1
    R --> S2
    R --> S3
    T1(2)
    T2(1)
    S2 --> T1
    S2 --> T2
    U(3)
    T2 --> U

• Le parcours préfixe de cet arbre est [6, 5, 7, 2, 1, 3, 4].
• Le parcours suffixe de cet arbre est [5, 2, 3, 1, 7, 4, 6].
• la représentation Python de cet arbre à l'aide de listes est :

🐍 Script Python

arbre = [6, [
    [5, []],
    [7, [
        [2, []],
        [1, [[3, []]]],
    ]],
    [4, []]
]]

Exercice

Coder une fonction reconstruction qui prend deux listes en paramètres : le parcours préfixe puis le parcours suffixe d'un arbre de taille n, étiqueté de 1 à n. Cette fonction renvoie l'arbre représenté avec une structure récursive à base de listes.

Indice

Cet exercice est un défi, aucun indice n'est donné.

###(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

Exécuter le code
(Ctrl+S)Valider
Ctrl+Enter
(Clic droit pour l'historique)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : ∞/∞

.128013]x,5/f.q!Br;nb _o=ylaeêpcwgu)vd*413kRméhtsP(S+02C[-ji:U050F0w0P0v0#0u0Q0p0z0u0v0Q0Q0s010P0#0y010406050Q0C0M0M0v0l0t040T0r0u0C0{0r0n0p020v0M0y0m0p0L0w150l0i0C0w0Q050f12141618100y04051D1w1G0f1D100F0#0E0:0=0@0_0O0#0B0O0u1U0O0P0~050+0o0u0w1P0?0^011T1V1X1V0P1%1)1#0P0l1E0P0O1+1R010g0-0w0n1j0w010:1b0Q0y0v0n0_0W1#2b2d1 1-221)250M27040a0p0R0l0r0y0r0Q0#1e1g0)290l0l0w0z2B1w2i0n1E0f1}2N1`1|1{1$0F2k0_1X0n242y1#1M1O0;1,2X0#2Z0n0r2%1#0y2G1E2L2N2^112c1g2)202.0l150u0~0I2K2|0 2{2j2~1-30320~0W362d382L2W013d0v33040J3h2M103k3b0_3n3p0H3s3j2|3l3y0~0e3B1H2?1w2%2Q0F1|2V3w010z2/2q0(1N1E2=0w2@373I3T0)3#3a1Q1-0K0~0)0g3I3v3,0_0A0~0p3=3D3R0n0g0~2G3T0n0Q1`0C2I0#1f3|3+2*010}040S4b2}3@3m0~2=0N220c0w4i3l4f0d3B3{3?4d0n0~120g4p4r1x3$4y204f0D0$3B060p4P4x3}4k4A040l0v0z2,4F2`4I1-4u4w394j4z0~240g2d0P1v4G3i4R4c200r0~0s4)4$3x4B0C4D0#4q4s3R4{040h564T4m2w5b4d4f0S0D4v4?2M4^4+4J0~0Y0b4N4Q5n3l3.040A1T1)4~4S4,4V4X4Z5C4_1-580j4}5l045v3~4m0l4o544!4H5D5p040Y5f4`0~0Z5$1-0M0#345*0_4f0b4M5O4O5u4Q4*3E4-3 4:4=4#5Y5K0~5a5O5{5R040v0y0y240F5/4e0~4h664 4l4V2H1f450l472J6j625:6h6f4U4n4E6f4(5O5Q5c044C6A6t5J6v040D0D5t5`6k5x2G0P0C0l0n5I5o4%5q6x5S5U556J6Z0_5865616K6l2x0y6B6h5j6Y5|044.5 6@5!0$5?6/6+01585)6*3l5,5.783R5;5s5@1w3(3!3J7j0f3M1w0P3O7o2T2O0v1(7l3M1C3*742G0M0q4/0K0w0q0O0J0~1o1q1s1u0p723$1J381D0k4W0E0r0p2x6V0:1*0F5U0p5T0C0@0#0p0j0p0X1*0n000N0+2A7Z0?0p2z7~0#1k1)7/1H7T040%2Z0p0v1d2G7~1b1d491g1s7.0Q0w4W7Z0w1d0Z0x1`1*0y1c0/3T1k5T0O242z7v851L1N3l1/1W1Y1!7z3l2m24260~2s0T0z0l0|0P2t0t1}4a663Z7z2_3$7i8N3R5x3:6f3_5P6x406m436p6r8h6 6i736{6z5V6 5k2^6E5E6H937c4k4K7Q3i5^4P674k8/0w3;9b4d8=3{9n2 8^8b0c0-0#0,2G8~6$040#946`680!9E6D9i5E0=0l0B8p0l6 4L4N9K209p5_9h9r1-0Q0F0~019(1n247X0#1*0u00160o8d7(220n7.2c0l0p1)0/1`2d0z8B0/9e3t9U9!9$5P9Xab4P924q0Y7.0$0p7.0U9}169O6V0b0p0*7~524E0Y0!7P0paxal9Mao0l7f2^3u6u019#3`ab9(016P9Xa7505F4Y2Z9F4k585N96aR6;5T6I907d6#9ZaS9Da,6g04aF379g5_a#4Ua.a!6k580UaZ3797207a04355@aca_0~aC9PaW4d76b04@a#b4b6aGb86k4U6}0n4;bd5%04bg5ma#4f5raPa^6R0~5z23bs3cbaanbc9Ja}0~020B0P0mbG0_b40V6 a50 ac5ub9040cbS754|b(6ya%9aa)9ca+b/5Ea{5X6:5;bAbmaI4Ubb6V0qb%bLaIaYb+0~2,0E8m8l0q996)b=5Z5#a/4Uc2cf6!a;b(76c6049Hc36:a~b(bjb{abb#bpbra/6-9B6a6c0n6ea/5hcF0C9v1X9y5W3ibx6wcic79Ia|b}0~cscl6L95b1b#b 0lc19R6Ob7bZ9hbncWct74a~bv8?c?04c+c-c:c;b#c#c)bM04a cqc cka?c;c=cZc~bJ6Vco5(c{b2bHdg9N9Pd0blczbC6m6U6Wb(by9B4WaUcR2McT04c(bhc}cB60b^74b`5@a@b#c8ca7GcddDc|c4b*c^4tb;dM795-04bVcK0~a=dIdY040GdycUc$3m0oba249AcV6Gaub.d%a*6Mdjd7cwd)bke2b:e4d!3R0z0I0~039}002,1M0z7?ar45aj0n0;7,bAa#5x0g0r9Qed6Fd4cS6k6CcY6:cjco8=2,b+d`6|0n138m0v0PdWdF8 ea98e0ceeY5Z9Sd1bBdfdS0lcbdV6 chd^eJd,cneBbedZeH744UeD3tdQdu6T6V6Xe_2 0~9u9wcQd}d^bUcXd5aIfee@dHbwbneO2nfce$dnaeeVeF0~6N9T0f8,7k2N7x3L0*0,0.04.