Désordonne un arbre ordonné

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

🧓 Cet exercice utilise aussi une modélisation d'arbre non ordonné, avec la liste des parents.

Version ordonnée d'un arbre

graph TB
    R3("Ga") --> P1("Bu")
    R3    --> P2("Zo")
    R3    --> P3("Zo")
    P1   --> P4("Meu")
    P1   --> P5("Meu")

🐍 Script Python

arbre = ["Ga", [
    ["Bu", [
        ["Meu", []],
        ["Meu", []],
    ]],
    ["Zo", []],
    ["Zo", []],
]]

Version non ordonnée de l'arbre

On place ici les indices dans l'ordre d'un parcours en largeur.

graph TB
    R3("Ga") --> P1("Bu")
    R3    --> P2("Zo")
    R3    --> P3("Zo")
    P1   --> P4("Meu")
    P1   --> P5("Meu")

    S3("0") --> Q1("1")
    S3    --> Q2("2")
    S3    --> Q3("3")
    Q1   --> Q4("4")
    Q1   --> Q5("5")

🐍 Script Python

# Indices     0  1  2  3  4  5
parents = [None, 0, 0, 0, 1, 1]
assoc = {0: "Ga", 1: "Bu", 2: "Zo", 3: "Zo", 4: "Meu", 5: "Meu"}

En effet,

• Le parent de 0 n'existe pas (None)
• Le parent de 1 est 0
• Le parent de 2 est 0
• Le parent de 3 est 0
• Le parent de 4 est 1
• Le parent de 5 est 1

Le dictionnaire assoc permet de retrouver les étiquettes d'origine.

Exercice

Coder une fonction désordonne qui prend en paramètre un arbre étiqueté et qui renvoie

• la liste des parents (modélisant un arbre non ordonné)
• le dictionnaire assoc d'association des étiquettes de l'arbre

Le procédé doit présenter les indices dans l'ordre du parcours en largeur de l'arbre ordonné. Même si ensuite on pourra créer des modélisations alternatives.

###(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 : ∞/∞

.128077.128013x/.r;nbylaeu)dV63m(P+02è-@U],59fq!78 N_o=pcwgv4F1kRéhtsSC[ji:E050p0m0%0l0-0k0(0M0S0k0l0(0(0Q010%0-0R010406050(0n0t0t0l0f0j040)0P0k0n130P0h0M020l0t0R0g0M0!0m1d0f0I0n0m0(050d1a1c1e1g180R04051L1E1O0d1L180p0-0V0{0}0 110$0-0U0$0k1$0$0%16050?0i0k0m1X0~10011#1%1)1%0%1/1;1-0%0f1M0%0$1?1Z010H0^0m0h1r0m010{1j0(0R0l0h110y1-2j2l271^2a1;2d0t2f040b0M0v0f0P0R0P0(0-1m1o0;2h0f0f0m0S2J1E2q0h1M0d252V2224231.0p2s111)0h2c2G1-1U1W0|1@2)0-2+0h0P2/1-0R2O1M2T2V30192k1o2;282_0f1d0k160M0Y2S3417332r361^383a3c0y3f2l3h2T2(013m0l3b040M0s3q2U183t3k113w3y0M0W3C3s343u3I3c0F3M3E3O3G3v0P393x3c0r3T3i351Y3l3Y3n3z0K3%3F3*3H3,3!3z0L3:3V3=3X3Z3J0G3{3j3}3Q040Y0x423)2=3~3-0Y3e1F3g3U434b450Y3p4g3r4i4a373@3y0Y3B4o3D3(3P4t160Y3L4x3N4j4s3 4C3S4F4q4A4J463$4M4z3W4l3/4S3;4k4B463`4X3|4Z4P0Y414%4H3+4P0y484-4r4/3-0y4f304N4U4!0y4n4|4T444 4w524Y4I4_4E574(593^0y4L5c4.3?4:4R5i4@5k4_4W5n4O4_4$5s4~4:4,5w544P0s4=5A4)3-0s4{4h535G3^0s515K584^5N565Q5d5S3y0s5b5V5j4c5N5h5#5o5%5Y5m5*5t5N5r5/5x5H5v3g1P2~1E2/2Y0p242%3W0S2`2y0:1V1M2}0m2 5`4F05640;6c5$0Z0h160H2D0t3M5L280T3c6q5R3H6l04640k1;2Q0-1n1D6e6w016t3z6v5W116k160-1s3Y0%3M0M6r3l160;1A0m3T4}3}0Z163k6M5$6K6W6H6N3v0S160X2b6-5+15040.3T0M716W6I0(2o04010*3*1=6_1;0M0l0V2P0M0n2+0M6!1B0M0m0H2a0S0l0S1=2L0v0j251n0A020U0%0g6A6C2J0(0170726X6O6Z7p6{3u6/7R3W0H0t160O0O2@2I7Z7U3}6}0u7(4b0i6}0(0m0k0H7,286}0o6 4M727}736=7.167:7=7@1^0P160e853H6Z0l0?6V7N0187040Q8f6I6y7m6$6;5$7*0o6%7}8g6*040;7?8q5+7T8B3P0H161C0%0O0V0-0;8a017*8O8104838A326I7_7{4|7~7M6I8x2O0%0n0f0h8l807/7;8V5`6I8i898E4U8c8e4F7 5$8i0Q8k8~8g8n0m6#8O8s8u8$6=8x8z8O8D8W6=0h8G042c2u8p9i8r167+8`3}8S8U99160E8.5$6y0c9y047`7L8#8g9w8;8O8^8O8n8d0l9N889P160l0R0R2c0p9F9t9q5+9D9F8t4M068v8%7P8=3r8g9h8?9j9l0p0#9o9$8R8:849u4b8Y9I7~8w6Q9=2U8 5+9La29(3u9Oa3378H0(8J8L8Naj1^8s8Z4h8#9J9:040f0@7:9B9)2y0q3x1B0/2N3Y9 aq117516017c1=ao2f9+a69/9d168)8+8-946Iaeaa6i5+aiag8{8y9R9T048_a.44162F0R1;0H6UaM8P9s9,4|6(4b9e7Qb09^9?8m9{0#0(3Y0p1n2+aLa^4k9W0f0i2O9+at4p9@3c7Mb00(0paP01011w0h0V0P0-1=0u2k2O0h0%0E7e0 0P0S0o7i7k0t2`0#1)0(8d6E1o2_1obgbi0#7v1=0k001ebp9p5?3}bybv712c0M1a1V2l0%0Mb/bg2O7l0n0MbK648+0`b|0}0f0U0m8+493ub_3z72bB7K7|9c9Ca`1e2c0%6G30acah1693cy8g6}0+0Da6959WbQ0SaCcA8jcN4U0i6Z0-2Q9$b3aucr9)160V0ncx3gcz3W91cQa_04aRcWcI8ma`c-4bc,a%9d6@040N1nb?3r718g0S0Y1603c21=bKcv7lb.0l0Maz0S2@d13DaXcs04c$c(bb6=a-9_dn9n6`b07*9%duc!04b;bqdy9zc^ak040R9+cX4pdmdC0-dI86cBdS118i0A8O0t0-4Cc=aY040T1#1;dV8h6K2_a cDc?doc%a=a@dB3Palan8Mdka+3uasaWcZd|04dRc{90160wcCc)8gd!d$cqaw9j162_ch9#dG049Ae9dCdLescOedd2cJd@dq2U8gdtdrdn9|9~ep0udNdlavezdhdj9Ferd=ek9m9kc0eB6L8@dUeva/em0neo8!eNd?1@bR9F0+9Ve79FcHe$3}c`eTdnePbjeia7d?dbbMeYeD9Ub06y9X9Z0he*d{3W8Qf8c@epeL17avc*6)6maKe_bm8T0Pc%0OdEe0fnc_6K2@d-6y9neX9FbseMfmd3d?dpd_e=dwd,eJdAeFdCbffvfxeRfD6QdM9bfLd(a!8,f!dKcuf4fZfrdJe.cM4S0d6g6b5{f{0d5~1E0%60g02#2W0l1:f}5~1Ke13W2O0t0O0H0l0Z0m0O0$0s161w1y6#0`fI2V1S672:3}0l0pbW0h2Ib$0Md:2y1K3ugygAgC7A130%20040C13bZb#1n0M0H1l8+8pgu1O6R0U7e0k0%110a2g3W0%0T1x0P0,d#b}0f0S1!1~0R0(0.0df_0p0h0e0,by7;1V0f0e2+0%0d1%0d0,0;0Sgi0p2Wg;bWg@0B0Y0F0e0Y0e0x0d1@0=0(1F0V0U0d0Y0H0W0W0p0e0(hC2ggN1;110.0w0Y0.010d3z0*0=0%1=0H1n6DgV7:az0M220z0`1l2bc8fu0f0M0P0ih!gBh@7jaS0m0f2HgVb(h^0fbh0h0hb,7l007j7eboc53x0#8dbGc50J1P3h2/3u1`1(1*1,gb3}9o2w2y2A0)0S0f14c17x7za$326aa+315`f`iva416e;b08^0ed`fUe216e^5FdJf3cwf:e|dCf?d-e{eed?9|bfi6bie0cE9se=fxfw0kii0%ikgj0?0^fRbl7^i`fh04iIfe7)160ofk18f_65gt5|f~68jhg95}0=0@0_04.