Aller au contenu

Arbre miroir

🏷️ On considère ici des arbres étiquetés et ordonnés.

Rappel : Arbres ordonnés

On dit qu'un arbre est ordonné lorsque l'ordre de ses sous-arbres compte.

Par exemple, les deux arbres ordonnés suivants sont distincts. (Si on avait considérés ces arbres comme non ordonnés, ils auraient été identiques.)

flowchart TB
subgraph "A_droite"
    direction TB
    N0(5) --> N1(7)
    N0    --> N2(9)
    N0    --> N3(1)
    N3  --> N4(4)
    N3  --> N5(2)
end

subgraph "A_gauche"
    direction TB
    M0(5) --> M1(1)
    M0    --> M2(9)
    M0    --> M3(7)
    M1  --> M4(2)
    M1  --> M5(4)
end

On peut même dire qu'ils sont ici en miroir l'un de l'autre.

Miroir

On dit qu'un arbre est miroir d'un autre si leur structure sont symétriques et qu'ils ont les mêmes étiquettes avec la symétrie.

Exercice

Coder une fonction miroir qui prend un arbre étiqueté en paramètre et qui renvoie un arbre de structure symétrique, avec les mêmes étiquettes.

###(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.9888]x,5/f.q!78r;nb _o=ylaeêpcwgu)vd4613kRAméhtsP(S02[-ji:@050H0y0S0x0$0w0T0r0B0w0x0T0T0u010S0$0A010406050T0E0P0P0x0n0v040W0t0w0E0|0t0p0r020x0P0A0o0r0N0y160n0j0E0y0T050g13151719110A04051E1x1H0g1E110H0$0G0;0?0^0`0R0$0D0R0w1V0R0S0 050,0q0w0y1Q0@0_011U1W1Y1W0S1(1*1$0S0n1F0S0R1,1S010h0.0y0p1k0y010;1c0T0A0x0p0`0Y1$2c2e201.231*260P28040a0r0U0n0t0A0t0T0$1f1h0*2a0n0n0y0B2C1x2j0p1F0g1~2O1{1}1|1%0H2l0`1Y0p252z1$1N1P0=1-2Y0$2!0p0t2(1$0A2H1F2M2O2_122d1h2*212/0n160w0 0K2L2}102|2k2 1.31330 0Y372e392M2X013e0x34040L3i2N113l3c0`3o3q0I3t3k2}3m3z0 0f3C3v3E3x3n0t323p0 0J3J3a2~1R3d3O3f040l3T3w3W3y3Y3Q040m3C1I2@1x2(2R0H1}2W3M0B2:2r0)1O1F2?0y2^383.3{0*433b3(010M0 0*0h3.3%2+010C0 0r4g3L4a0p0h0 0P0$2w4u4n494i0~040V4x3V4i0p0 170q2H4D3m4A0F0%3J0r4R4m4h210T2h04011p0p0G0t0$1+0E1h2/0E0G0y0w0r4I2H0e0r0T1g0r4t4v0n014Q4S3U3F0 0n0x0B2-0y4L3M4A0e3C4T4o4F0 250h2e0S1w1y385f4y210t0 0u5e523M4G044=595o3j064S5q4E300 4,4.0x0E0d5w4U1.5t045v5D2N5H4M0 0Z0c504R5x4p5K5Q5g5s5u5,5r3d0q0 2o5a4a4A4C5W485I3d5i4q5l5n2{5R0`4N5%5Y3M4c040h3O5:5 3y0 0$6g3m0t4k042-6l5y5?04550p0D5C655-1.5{5_5h040p6D214N4P5}5F5G51663n5K0t4-0y5N5P5}5)4i5T0i6H605A0A0A250H6$670 5|6z5;6i044|4%0n6-016C6X6P5z5j636{4A0Z6{5z6G5}6a4a5T0!6r4a4t357e6Z0 7d796Y5J6p730 0c0F0F697n1.6c2H0S0E0n782_7a4z5!765456587q045d7m6 6R6T6V7M5$6L1x46423/7Z0g3=1x0S3@7(2U2P0x1)7#3=1D5~3m2H0P0s5k0M0y0s0R0L0 1p1r1t1v0r6K2{1K392(3m0x0H0P1g2B0$4`0H2e6x4~390A8c8e8g2C0!0|0S1_040O4.0B0r4*1+3{1l0n0Q0R252A1g1I8a1O3m1:1X1Z1#7?3M2n25270 2t0W0B0n0}0S2u0v1~8M6X415~2`447Y8V4a6c4e6{6o4m6~6A3y4r6@4u6_7M6:447Q5A0n4J6y98906|0 4O7v6P4W0 4Z254$4(8C4+6S4.4:5B4@4_1h6^4u4 6L5G7w6?55572!7M7O7E9F6Q04710p5m7i5.5U9T6%5B9j9f7y0+7B7D5p9N747I6u7K9J8 6=9g7N9W6.04759D6N5(999A6`9:6h9=973j9N5z4_0E0T0s9Ya15Z047u7P9!0 6ea09M99a8aaacam9f6n6j9(3j7F306t2H4.0n0T0y6,ad5b6/9,9Q9SaG5`9h9Z9;4A0c7V2_110g8@7!2O7;3;3 1M0+0-0/3m8k6w0y8n3v141r198z2I0r0?0r6e0p2J8i1h058@160A7X3|2`a;1B8O2)4a8R1=1!2i9f8X2p2r8#8%8)8+8-av2N1G3:882{aX6P8`0y4faM4i8}76929 969,aq9eaQ9h87386M9}9f9l4Y4!9p4)9s6T9v9b4?4^4`9 9CaU9E999H7LbB6I0 9L9)99aK64b?as5/ah9;5zbJ5Eb+ai6u9$7C9@9=9`6;a25zb-9/caaeb=awa66t1Y0T0SbHb/5=4s0xb4cp9^a4br9~944wcu9=ch5Xcj540yaBaDaFcfaH4BaJ629Rb_a56P4N7taTbOb547aYa#0G8o8y8A9r4^0S0v1*a{1ga~1g2!4:121{1g0D9P0d1{0z2q2Lc_6w040r1n050$0P0D4;0w0S0`0b293M0S0C1q0t0#0$290T0n0B1T1@0A0T0%0gaW0H0p0i0#0T0*1Y0G0n0i2!0S0g1W0g0#0*0B7|0H2Pdj8fdm0(0K0f0i0K0i0X0g1-0+0T1y0G0D0g0Y0J0x0X0i0Td-298v1*0`0%0C170p2-0D0%010gd42/1h2H8F160p0H0Q9x5N0h0r2y7Ba_851k0x0S0y7B0:2E051q041g4/58a0ew0r0keE8N1M8P3Mbd8Tbg9;bi8Z2s0r8$8(0A8*0U8,0R8.2{8:3U8=a5bwc38{cBbDcB4q4sczalbKa26}cL5*9a9c7M9ib}a29#7Ac6e aec9e?53e{4KcB9+cB7g040X7UcDd4cF04clcnfbaIe.6tb3coe_6EbGfo9?f46scGcIaEftf75y4Hb!9dcS9ffcfu21fe36fx7scV3TaWb6c!7$a$3;a(0.0T397$f#0/04.