Aller au contenu

Reconstruction d'arbres binaires de recherche

Exemple d'ABR

graph TB
    A("8")
    B("3")
    C("15")
    D("2")
    E((" "))
    F("12")
    G("23")
    H((" "))
    I((" "))
    J((" "))
    K((" "))
    L((" "))
    M((" "))
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> H
    D --> I
    F --> J
    F --> K
    G --> L
    G --> M

Parcours

🐍 Script Python
préfixe = [8, 3, 2, 15, 12, 23]
infixe = [2, 3, 8, 12, 15, 23]
suffixe = [2, 3, 12, 23, 15, 8]
Objectif
On donne seulement le parcours suffixe, retrouver le parcours préfixe !

Exercice

Coder une fonction retrouve_préfixe qui prend en paramètre la liste donnant le parcours suffixe d'un ABR et qui renvoie la liste donnant son parcours préfixe.

👍 On garantit que l'ABR est sans doublon et qu'on peut le reconstruire en temps raisonnable.

👍 On pourra modifier la liste suffixe à loisir.

###(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 : ∞/∞
.128013]x,59/f.7B8rnb _o=ylaepcwgu)vd4613kRAméhtsP(S02è[i:050E0w0P0v0Y0u0Q0p0y0u0v0Q0Q0s010P0Y0x010406050Q0B0M0M0v0m0t040T0r0u0B0@0r0n050g0~1012140|0x04051k1d1n0g1k0|0E0Y0D0,0.0:0=0O0Y0A0O0u1B0O0P0`050%0o0u0w1w0/0;011A1C1E1C0P1K1M1I0P0m1l0P0O1O1y010h0)0w0n0v0M0w010,170Q0x0v0n0=0V1I1_1{1)1Q1,1M1/1;0`0a0p0R0m0r0x0r0Q0Y1a0n0p0#1@0m0m0w0y2i1d200n1l0g1%2v1!1$1#1J0E220=1E0n1.2f1I1t1v0-1P2F0Y2H0n0r2L1I0x2o1l2t2v2Z0}1`2j2N1*2S0m110u0`0p0H2s2%0{2$212)1Q2+2-2/0V2=1{2@2t2E012|0v2.040p0I302u0|332`0=36380p0F3c322%343i2/0e3m3e3o3g350r2,372/0G3t2^2(1x2{3y2}390j3D3f3G3h3I3A390l3M3v3O3x3z3j0f3U2_3W3q040H0U3#3F2O3X3J0H2;1e2?3u3$3.3(0H2 3?313^3-2*3Q380H3b3~3d3E3p430`0H3l473n3_423Y4c3s4f1o2X1d2L2y0E1$2D3w0y2T1=1l4q1m4o2#4m4w0#2Y3V3.0J0`0#0h3m493w0z2/4O3N3`0h0`2o1!0r0B0D0w0q2W0N1,0c0w4T4I1*0_040S4.4h2{0`0~0h4+4-4m4U4:0`0C0Z3t0p560p4P3W0Q1~04010K1.0D0r0Y1N0u00120o2o0p0o2Q0(5p2l2o0y0O0w0m5x1N0E1b0P0p1M0p1`5A4!0m0+4{4}0p0w0Q5F5D0n0n0N015557593`0`0v5o3m58501Q0r0`0s5*5#2*0`0L0k0K4@411Q4;0S0C5Z565=1Q4K040z1A1M5;5,3h4`0B4|0Y4,5{344;544f06576o5+4/4_045(0m6i3w5.040i6w3%0`2Q0Q0W2o6B3.5~6I5?045O6g4~2#6b016y6A4 6r6c042e0x6L5}0`5 606m6n5!6S0n0`4)4}6a6X6T5/6?4^0=4;0X0b616q6{01654M6$0=4R3976354W6Z124w0B5M7a6K6W726/6t5)7k5|6|0`0d6`7q356:0m4*6P7i526l2Z6,6p717v650Y4N4f7H340r782S0P7u3p5%7o6R6@6U7a7m5R0P0q0D0Y0#7B4=53707G626.7x7z6h7p7O0`6V7X7l5%0x0x1.0E7,4?7_3w7m6u7a7Z866C040D370w7g7,6*7E7:6p636Y5J7f7h8c6J6(7!7V6v8t1*8b7}7v7m0A0v0B5B7,7t7M8o7w6Z7y6=8z6%048k3@8m6o8M7m8q5L0Q848w7n8y8C7`6z8(0E2c2h6Q2?8M4;8K2Z7N877?8Q8+3w4;8U3 7F8{8d8!7g8$8R7r4=8(899a018^7T8|8O7@8=318@52708M654Y7g1c8L7=9k8~3@1d4F0w2v2W9D4p1u4r2y2B2w5(1M2v4q0|0g0#0%0)0Q04.