Aller au contenu

Aplatir un arbre

😀 On considère ici des arbres non étiquetés et ordonnés.

Définition : aplatir

Une structure arborescente prend de la place en mémoire ; pour chaque nœud, il y a une liste d'adresses de ses enfants.

Aplatir correspond à proposer une structure linéaire qui permet de coder l'information contenue.

Voyons comment stocker un arbre non étiqueté dans une simple liste d'entiers.

Transformer un arbre en liste

Une simple feuille sera stockée avec [0], pour indiquer 0 enfant.

graph TB
    N0( )
    N0 --> N1( )
    N0 --> N2( )
    N0 --> N3( )
    N1 --> N4( )
    N2 --> N5( )
    N2 --> N6( )
    N3 --> N7( )
    N3 --> N10( )
    N5 --> N8( )
    N7 --> N9( )

Cet arbre possède trois enfants, on écrit

🐍 Script Python
arbre = [3, ...sa1..., ...sa2..., ...sa3...]

il faut remplacer ...sa1... et les autres par leur version plate !

  • sa1 est un arbre qui possède 1 enfants :
    • donc sa1 correspond à [1, ...] et on remplace ... par le contenu de [0] ; la feuille.
    • ainsi sa1 est [1, 0]
  • sa2 est de la forme [2, ..., ...]
    • rappel, sa1 est de la forme [1, 0]
    • rappel, la feuille en version plate est simplement [0]
    • Ainsi sa2 en version plate est [2, 1, 0, 0], de sorte que pour arbre on peut compléter
🐍 Script Python
arbre = [3,   1, 0,   2, 1, 0, 0,   ...sa3...]

Continuons !

Ce troisième enfant sa3 est identique à sa2, en version plate, c'est [2, 1, 0, 0] de sorte que pour arbre on peut compléter

🐍 Script Python
arbre = [3,   1, 0,   2, 1, 0, 0,   2, 1, 0, 0]

Victoire !

🥚 easter egg

Si vous résolvez cet exercice, vous aurez accès à un exercice caché : reconstruire un arbre à partir de sa version plate.

Exercice

Coder une fonction vers_liste qui prend un arbre non étiqueté en paramètre et qui renvoie une liste qui correspond à la version plate de l'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.129370]x,5/f.q7Br;nb N_o=ylaepcwgu)vdV4613kRméhtsP(Sà2è[-i:050G0y0R0x0#0w0S0q0A0w0x0S0S0u010R0#0z010406050S0D0O0O0x0m0v040V0t0w0D0`0t0o0q020x0O0z0n0q0N0y140m0j0D0y0S050g111315170 0z04051C1v1F0g1C0 0G0#0F0/0;0?0^0Q0#0C0Q0w1T0Q0R0}050*0p0w0y1O0=0@011S1U1W1U0R1$1(1!0R0m1D0R0Q1*1Q010h0,0y0o1i0y010/1a0S0z0x0o0^0X1!2a2c1~1,211(240O26040a0q0T0m0t0z0t0S0#1d1f0(280m0m0y0A2A1v2h0o1D0g1|2M1_1{1`1#0G2j0^1W0o232x1!1L1N0:1+2W0#2Y0o0t2$1!0z2F1D2K2M2@102b1f2(1 2-0m140w0}0K2J2{0~2`2i2}1,2 310}0X352c372K2V013c0x32040L3g2L0 3j3a0^3m3o0I3r3i2{3k3x0}0f3A3t3C3v3l0t303n0}0J3H382|1P3b3M3d040k3A1G2=1v2$2P0G1{2U3K0A2.2p0%1M1D2;0y2?363!3.0(3_393U0^0M0}0(0h3!3u40010B0}0q463J480o0h0}0F0y0m0S0s1W0S0R0y4d3 2)010|040U4s3T4u0o0}150p2F4z3k4w0E0$3H0q4N4c474u0S2f04011n0o0F0t0#1)0D2Y0q4o4q0q1r0#0q2F2;0P0S234*0w004E2F0q230q4j4l0#1e0q0z0;4q014M4O3S3D0}230h2c0R1u1w364P4e4u0t0}0u3A5k4t2~4D0m4F4r5i3h064O5r4A5t04540x4q5q5a3K5n045p5y2L5C4I0}0Z4H3K0o0p0}2m5V484w4y5P3~5D3b5u5w5#4u4J0c584N5K4842040h3M5J4Q5E0S0t0D4m4`5x2@5R5L4a042+5~5l5E5d5f5h2_5 1,4w4L5)5A5B596k3w0}5G5I5)5^5m0}0i5/6f0d4q0o0G6C6l0}5(6j6e5,044 4m4)663`6s4v6K6I6t0461630s656Y6W040E0E5?685_0}2F0R0D0m0o6d5s6O6v6T5z1v3|3^3#720g3(1v0R3*772S2N0x1%743(1B5*3k2F0O0s5e0M0y0s0Q0L0}1n1p1r1t0q6n2_1I370(0*0,0.3K0G2c0C4k0}3t121p170H4k2y520x0D0q4p0v1(0q5|0o2H510o2Y0w0q0x0C2F0?0#451w7O1z371C0r522F3.1y6G0P1)7V0d0q0P0w0Y4j0S6B7B1K1M3k1.1V1X1Z7i3K2l23250}2r0V0A0m0{0R2s0v1|1e3!3@5*2^3`718l6:04446)6a4c6x6V4g4i7S4n0#4p6~2L6y1 5%6)4C046(8O6N0^4J7z366p5@6V4S0}4V234Y4!0q4$1)6S4+0D4-4/0m4;4?8}4_5v4{4}6Q7)5355266.8Y1,5`6=6@6_5)6/4B5Y6!126)8!6o6q6r8*6*6L6U9y8$6Q8T8V9t6X8)6{6Z6#64988W8H5:0}6-9n9h410}5|0m6`5+9L629N5.9U6V0t6a6c9*9C5-4G9J9#6*0E0e6.5B9V3l0}4p150R6)5M5O6M9K6*5U9?3D9q5!aa3K9ua69@8$8(ah5S6+5=9v9xa74J3R0g8G732M7g3%0)0+0-7C8f3K0x0G0O1e2z9c0S0x8_0m7M1E3kaGaI0oaK1e0!0`0R1@040l0maN0t0q0b1G7`040H9%7-0A0A0Y0.0W4(000y0d4k0A0#0A1)0A0x0A0Q0P4c0x0q0Q2F0h0^0i0i0g0k0k0!0x6v0#0m0s0X0s2+0F0g7t2G1e4p0m909=0x048c1J3%3=0 75aA7F04.