Aller au contenu

Reconstruction

Arbre binaire presque complet à gauche

Il est possible de travailler avec un arbre binaire presque complet à gauche avec uniquement la liste donnée par le parcours en largeur, comme on l'a vu dans le cours.

Objectif
étant donné un autre parcours, retrouver le parcours en largeur de l'arbre.

Faire quelques expériences sur feuilles dans un premier temps.

Exemple 1

graph TB
    N0("7")
    N0 --> N00("2")
    N0 --> N01("1")
    N00 --> N000("0")
    N00 --> N001("4")
    N01 --> N010("6")
    N01 --> N011(" ")
🐍 Script Python
# arbre correspond au parcours en largeur
arbre   = [7, 2, 1, 0, 4, 6]

préfixe = [7, 2, 0, 4, 1, 6]
infixe  = [0, 2, 4, 7, 6, 1]
suffixe = [0, 4, 2, 6, 1, 7]

Exemple 2

graph TB
    N0("13")
    N0 --> N00("17")
    N0 --> N01("41")
    N00 --> N000("71")
    N00 --> N001("19")
    N01 --> N010("53")
    N01 --> N011("11")
    N000 --> N0000("23")
    N000 --> N0001("37")
    N001 --> N0010("73")
    N001 --> N0011(" ")
    N010 --> N1000(" ")
    N010 --> N1001(" ")
    N011 --> N1010(" ")
    N011 --> N1011(" ")
🐍 Script Python
# arbre correspond au parcours en largeur
arbre = [13, 17, 41, 71, 19, 53, 11, 23, 37, 73]

préfixe = [13, 17, 71, 23, 37, 19, 73, 41, 53, 11]
infixe = [23, 71, 37, 17, 73, 19 ,13, 53, 41, 11]
suffixe = [23, 37, 71, 73, 19, 17, 53, 11, 41, 13]

Exercice

Coder une fonction reconstruction qui prend en paramètres une liste parcours d'étiquettes et une chaine de caractères parmi ("préfixe", "infixe", "suffixe") et qui renvoie l'arbre binaire presque complet à gauche associé, sous la forme d'une liste obtenue avec son parcours en largeur.

👍 Il sera autorisé, pour cet exercice, de faire muter le paramètre parcours. Il peut être détruit à la fin du traitement.

Indices
  1. Commencer par faire de nombreux tests sur feuille.
  2. Commencer par écrire la version "préfixe"
  3. On pourra commencer par
    • initialiser la taille de l'arbre
    • inverser la liste du parcours, pour la considérer comme une pile ensuite
    • initialiser un arbre, avec une liste remplie de None
  4. On pourra créer une fonction récursive travaille qui réalise le parcours demandé, mais au lieu de construire la liste l'épuisera pour compléter les étiquettes des nœuds.
Guide
🐍 Script Python
def reconstruction(parcours, ordre):
    "Renvoie la reconstruction un arbre presque complet à gauche"
    n = len(parcours)
    parcours.reverse()
    arbre = [None for _ in range(n)]

    def travaille(i):
        "Complète l'arbre à partir de l'indice i du parcours"
        ...

    travaille(0)
    return arbre
###(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.q78r;nb N_o=ylaepcwgu)vd*4613kRméhtsP(S0à+2Cè[i:050G0y0R0x0%0w0S0q0A0w0x0S0S0u010R0%0z010406050S0D0O0O0x0m0v040V0t0w0D0|0t0o050g13151719110z04051p1i1s0g1p110G0%0F0;0?0^0`0Q0%0C0Q0w1G0Q0R0 050,0p0w0y1B0@0_011F1H1J1H0R1P1R1N0R0m1q0R0Q1T1D010h0.0y0o0x0O0y010;1c0S0z0x0o0`0Z1N1~201.1V1;1R1@1_0 0a0q0T0m0t0z0t0S0%1f0o0q0*1|0m0m0y0A2n1i250o1q0g1,2A1)1+1*1O0G270`1J0o1?2k1N1y1A0=1U2K0%2M0o0t2Q1N0z2t1q2y2A2(121 2o2S1/2X0m160w0 0q0K2x2,102+262.1V2:2=2@0Z2`202|2y2J01310x2?040q0L352z11382 0`3b3d0q0I3h372,393n2@0e3r3j3t3l3a0t2;3c2@0J3y2}2-1C303D323e0k3I3k3L3m3N3F3e0l3R3A3T3C3E3o0f3Z2~3#3v040K0W3*3K2T3$3O0K2_1j2{3z3+3?3-0K343{363}3=2/3V3d0K3g433i3J3u480 0K3q4c3s3~473%4h3x4k454f4o3.3H4r4e3B403Q4x3S3 4g3.3Y4C3!4E4u0K3)4I4m3M4u0Z3:4k1t2$1i2Q2D0G1+2I3B0A2Y1`1q4Y1r4W2*4U4(0*2%4J1/0M0 0*0h3r4y3#0B2@4}4D2/0h0 2t4(0o0S1)0D2v0%1g524@1V0~040U5g4P3m0 1 0m4(0D0m0S5m465i0 0d3r0q4~3 0 3D0G2t5w395j0E0(3y0q5P5C531V0S2304010N1?0F0t0%1S0?0q571g5a0m5c2n0q0D2o170p2t0q2#0y0S0j0D1S4(0O0z1R0R0q0X0q0C0x5c0Q1`5O5Q5D2/0 1h4k5R5h0`0t0 0u5B6f300p0 2a5J3B5j5l4U5S5o045q5s5u6w3#5L6d5P6r6C6E0t5t5v6A6l016n040i6H5E042t0F0y5u0y6Y1/6y0E6K6k5n3a0 5?5I6j6M6U6o6q6B015j0$6*1V0M0A0 0r1g6)6^6}4_040h3D6|6T0o0 0s7f6:0t50042V7k5x3m6t6!200C782*6}6y716C6i7y6T5L0b3y065Q6/7r017b4{7B017n5C6S6:0o55041)0x0F0-0w1R7Q7A7U7M7h7o7)0 5M6.7K6_5U0 010!0t610w0#0R5%006?1S665q0|0m2p812V1y0A1S0%2p0D5_176F0S017=6e7a0 0%4|797g8q7q396V020w0R0n8w4z6h7/045N4r7K8K8o6T7b8r8D3,5F0m5H7x2{7L8x6o6p8t6:7^5W2#0P1;0c6c7+5K0 8I2(7J8L8@6L6}7-838G708.8E7.8 6I0 7H8#7M6V8!2(8X906O6Q7Q6V6X926Z2j0z8G0U6-8J8^8M7V0 7Z7#0.7(9i6+0 6z7E6:0O0%0 429a6_6V0H8Q6Z0%9M1/6V0Y9P1V9E4h8G9o8=9q9r7M8O8s9I8`8S8U9T6m8Z9-018%012V8+8-9C7M5j8;3|9!8L6_8{0m5@8V366_6 7Q7-9O9y5y04959)6T989:7-9d6Gac9.6Wa95p2i9m9Y9~9 a19t0m7!7$9x9`8/5k7Q9V049H8W9J0 9L963u8vaO3B9R9:aHaJa67z7:8na08p7o9(aK9*045G6@ag7l9/aR3#9=130h9^8man6~8:a!9qax048|a{a8a{aa8Gafa)ah6{a;9j8j6PamaDaS0 9hbh8R6Dasb39Aau448?8_8u7Yaz9v7%a52za79AaG9F044Tbl3?6J9pbu6:7b2t0R5t7Db99sb1a3a-3|1i4;0y2A5`2A4,2B4!1i2Eb,0x1Qb#4X1z2|0g0*0,0.0S04.