Aller au contenu

Arbre similaire à un autre

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

Rappel : Arbres non ordonnés

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

Par exemple, l'arbre non ordonné suivant est unique, même s'il possède plusieurs dessins.

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

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

Arbres similaires

Les arbres enracinés définis avec les listes Python sont, par construction, ordonnés. En effet, dans une liste l'ordre compte.

On dit que deux arbres sont similaires si leur racine sont de même valeur et que chaque sous-arbre du premier est similaire à un sous-arbre du second, et réciproquement.

Concrètement, cela revient à dire que les deux arbres, en version non ordonnée, sont identiques.

Exercice

Coder une fonction sont_similaires qui prend arbre_1 et arbre_2 en paramètres et qui renvoie un booléen :

  • True si arbre_1 et arbre_2 sont similaires,
  • False sinon.

👍 Pour simplifier l'exercice, on garantit que pour chaque nœud, les étiquettes des enfants directs sont distinctes !

👍 On garantit également que chaque étiquette est un élément immuable pour Python (un nombre, une chaine de caractères, ou un tuple d'éléments immuables...).

###(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 : ∞/∞
.128013x/.Tr;nbylaeêu)dV6z3m(P02è-],59fq!7B8 N_o=pcwgv4F1kRéhtsSàj[i:E050q0m0%0l0-0k0(0M0S0k0l0(0(0Q010%0-0R010406050(0o0v0v0l0f0j040)0P0k0o130P0h0M020l0v0R0g0M0!0m1d0f0H0o0m0(050c1a1c1e1g180R04051L1E1O0c1L180q0-0V0{0}0 110$0-0U0$0k1$0$0%16050?0i0k0m1X0~10011#1%1)1%0%1/1;1-0%0f1M0%0$1?1Z010G0^0m0h1r0m010{1j0(0R0l0h110z1-2j2l271^2a1;2d0v2f040a0M0x0f0P0R0P0(0-1m1o0;2h0f0f0m0S2J1E2q0h1M0c252V2224231.0q2s111)0h2c2G1-1U1W0|1@2)0-2+0h0P2/1-0R2O1M2T2V30192k1o2;282_0f1d0k160M0Y2S3417332r361^383a3c0z3f2l3h2T2(013m0l3b040M0u3q2U183t3k113w3y0M0W3C3s343u3I3c0E3M3E3O3G3v0P393x3c0s3T3i351Y3l3Y3n3z0J3%3F3*3H3,3!3z0L3:3V3=3X3Z3J0F3{3j3}3Q040Y0y423)2=3~3-0Y3e1F3g3U434b450Y3p4g3r4i4a373@3y0Y3B4o3D3(3P4t160Y3L4x3N4j4s3 4C3S4F4q4A4J463$4M4z3W4l3/4S3;4k4B463`4X3|4Z4P0Y414%4H3+4P0z484-4r4/3-0z4f304N4U4!0z4n4|4T444 4w524Y4I4_4E574(593^0z4L5c4.3?4:4R5i4@5k4_4W5n4O4_4$5s4~4:4,5w544P0u4=5A4)3-0u4{4h535G3^0u515K584^5N565Q5d5S3y0u5b5V5j4c5N5h5#5o5%5Y5m5*5t5N5r5/5x5H5v5?5B5H5z5`5M3y0W5E5~5e605J4p5L64160W5P675R5p3^0W5U6d5W6f605!3r1P2~1E2/2Y0q242%3W0S2`2y0:1V1M2}0m2 3g3M056y0;6G5$0Z160;0G6I6e010T3c6S6k3v0G160i0-0+2P2R4F681^15040w6X5$0h161)0(0%0m0O662U6,116.0D3M0M6 3v6@0-6_6{6c6~6T6.0p0.493u6V3z0M7l6;5+0(0q16017s1w0h0V0P0-1=0o2K0-2Q0-1n2d0-2O0M1@0P0S0-2l0%0M1;0`2@1U0S1C0M2L6^6`6|7h3W7p3c7l0M0=0{0m0o0b7X1=7Z7a7;0M0(3Y6`7Q787!0z0,7U0P0,0-0C0C0M0Q0Q7}796|840C3T4}3}7(7k7l0/7P7V7M0M0*7Q0l2h0h1U2J0M1A000^0`7`7y0h7P2L0v0n2x7Q1n0U1B0o0f0d8g758j7*1v2c7w7y0M0N1n1=2c0{0~7X000#0S0$2P8R4?3u8U7*7s013T8V750S0Y16030M0V0m0f2H1n7Q2c6`8{7*756O040-6R4F746T0h0i6@2c7n3u6.6:6+9k778c6}6M5+7e73750P160I0Q9B9k9m042v9p3W9r9M449v7 9P4b7e7g4M8V8|6T9e2O0%8P0h9H6Y0Z0S168#2+9b7m9u04829*5$9D049G9i759l6P7C0%9T289r0p9;9j9+160G3Y9_5+6?9fae3u0P7j2@ai4U9J0f2l0U0ma46-169s329I9n9)9t6Y9OaC6=9R6{9x757e7fa89Zaa04ac0fan9Q040+aT4bak16am9~az04aq0hasau70awa,3v9J9LaF9za.a?3PaH0O7b9y9q160paM9X9Yb49da!9h30a9aG9K7~aIa/6.0,a/ag0-bf168fa$6Y9{89aX37a{a}aK16bha_4U16aWbz3}6.0C9W4|b4bJ9c9!b7bs3la!bO11aZ9faBb99 a16ybl04bH4hbKb(bLaP9$9(bR019,9.8$aNb)baafbY0Pb!byay6Ybjb!bnbW6Tbqb.agbCbIbJb69fb83gb^a`ahbo9`7j2_a3ci5+bTa#c3b b`b!b$4pb@cf3W9#0=b-cn3ub:049/atb39=b+cB0fbVcebX9@7Cb{4M068h4b9e6Qa/7j74bD4k6!047`8F0O2H0v0^0@2O1Dc%a5a^b~bb1e0i2O7#c@av0472cDbA04c|c~bv7db0cv3DaO5$0(2o04017u8Y7z1o0i0P1j0#2c0D0M0e0f1B7_0-980`d71=c+7Pc.c:7H0mdt0X3x0(dD2@1n8`cJcyaUaq7M2+c c`a@d2c6162c0G7O0(dYcPc4169}crc{0fc}bedScQdV2@7ab!d3d;b_04d(d*a|b.c5d4aUdCe5d_bMccd$a(0ldWd^e0aj9Ed:d-csegeiebdZa b#b?cK6N16b,cNb.cFdL0_cI4|06dee10}0i0m0k0O0m9xdTaYd/b.bgbi167`0od+dCb|a/c/16626oda04c2eoeyaQade84keY0Pe!0Oe$e@28cpcO3reSbte20hd)8Fd+aJe-e/cwb*bbeLeNePa}f31^e7ek9NbxeXc*e`e#d?2Oe%d011e)04e+7caDbmeCabe?fnaUeZftd@e6alf12Ufk3Hd%f6e4d9fDe.a8cQ7K7M0l6*fIeT9|ef6$6(7D1nb!ax6H9?fgeOeQd~eff^fib!a7ecaP9geff#7Nf(e:coalc?f)28cFcHcuewfRb/ezcMfP3z9d9-04eEdN8geJcEfGaSe~bPchgcflfOg40 7Lg67EgmbwevdSgud5c8g8elf+gyfSd6gFf$g7e,fXb}f?epbkfx01bFghcQe3c,eR9CeUgT76f5f70%f9fwetd5g(g}bEfEgMfee1g.0%esgQ3Wfmh9aUh6d+fW5$eWg)c7c1g,edg3g?bTclefdEc-0-c/0}dIgbg$hhc_hAh5fUg/f{g?agh6h8gZhB04b2c9b)cbeAgmgieDdMeG4heIh4gva(gleCgpdv1B3%0c6K6F6ph:0c6s1E0%6uh^2#2W0l1:h=6s1Ka~3W2O0v0Od)0Z6{0$0u161w1y1A7Wdc2V1S6B2:3}0l0q0v1n2IgI0M136.1K3uioiq0his1n0B130%20040K6%6)it0l930S74h/f51b94f%cIiR1P3h2/3u1`1(1*1,i33}2u2c2e162A0)0S0f147P0x0j25f:6+6E9y316HiXedcZg)c#bic)f-iLi|h09UhChMeKbdd,jfeud hce^bc8chgd!hP631^c#9cg)8j8_dk7xdm7Xa2gI7G7Ig57OdA0M7T7C7W7Yjh9xcW288@7l7,7V7/7^7?a|7^7`0f7|j!80828e87898b7!0Y8e8S6TjU0M8m7-8p8r0}8u8wit8z8B7_jB8F7^8I8K0k8M8O8Qj@6Yj_jA8ZcH7+358*0q8,8.8:7$8i7q8k0M8_fZ6T8~909294961o2v9ag1e;hogB3Ha;9og)aEjcf4j!fafXg0kL019{9Fc6kNgJe-f=jjd5j*f iih!b5edhTh)b;9:kIe19^hpg=kXa0cR2Qf;kWb%h#czgwefg hDjkef0bfNa!hU9 9J2ciTaqkHkRd1k)fCffjQk-hmaPaRefgPk*h1d#hI160jlebUk#fTlkiVf;fqk,kPdbghgN3}9ekKjmf4ldk|9|enf2cQlElOgLhQcxhVbNlCgAlVgClfefk{lna-l)l4l+9YhSh(g?geb=h3hR9?l@lafo04g#lzjnl9mbc^fYlYl!fQcQlyddcahncdl#9?mdmjc4ck0PcmkXf0l?cSggm3l}k;l kXm1k^l*l~9%eBl.m667h.6zij6qh?6Ci20rfsiu2D0o932O0t0M7A1=m%kE0M0R1k0`aq0R0-2L0q2l0`1;m/2D1:0A8K1a0f98jDf/0hjG1=2Lj9n78;ikmV0V3hh?0=0@0_04.