Génération d'arbres binaires non étiquetés

Génération

Notre objectif est de fabriquer (générer) toutes les formes d'arbres binaires. Il y en a une infinité... Il faut limiter notre étude. On peut filtrer par taille, ce qui permet de faire une classification.

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

Il y a donc un nombre fini d'arbres binaires non étiquetés de taille donnée.

Modélisation () | (⋅, ⋅)

Dans cet exercice, on modélisera les arbres binaires non étiquetés avec des tuples, de la façon suivante :

l'arbre binaire vide sera modélisé par (), le tuple vide, de taille 0 et de hauteur 0.
un arbre binaire non vide sera modélisé par (gauche, droite), un tuple à deux éléments représentant respectivement le sous-arbre à gauche et celui à droite avec des tuples.

Pas de classe Noeud dans cet exercice !

Classement par taille

Il y a un seul arbre binaire de taille 0 : ()
Il y a un seul arbre binaire de taille 1 : ((), ())
Il y a deux arbres binaires de taille 2 :
- ((), ((), ()))
- (((), ()), ())

Il y a cinq arbres binaires de taille 3 :

((), ((), ((), ())))
((), (((), ()), ()))
(((), ()), ((), ()))
(((), ((), ())), ())
((((), ()), ()), ())

Arbres binaires de taille 4

Les 14 arbres binaires de taille 4, peuvent être répartis en fonction de la taille des sous arbres.

Il y a un nœud racine et 3 autres nœuds à répartir à gauche ($t_g$) et à droite ($t_d$).

\[\text{Formule sur les tailles à vérifier : }(1 + t_g + t_d = 4)\]

$(t_g=0, t_d=3)$

$(t_g=1, t_d=2)$

$(t_g=2, t_d=1)$

$(t_g=3, t_d=0)$

Exercice

On considère le dictionnaire dico_ab qui, à une taille donnée, associe la liste des squelettes des arbres binaires de cette taille.

On peut initialiser ce dictionnaire avec {0: [()]} : pour la taille 0, la liste des squelettes n'a qu'un seul élément, le squelette vide ().

Compléter le script avec la fonction génère_ab qui prend n un entier et qui modifie le dictionnaire dico_ab avec

toutes les clés entiers naturels k inférieurs ou égaux à n
et dont la valeur associée est la liste (peu importe l'ordre) des squelettes d'arbres binaires de taille n modélisés avec () | (⋅, ⋅).

Évaluations restantes : ∞/∞

.8901.9888.128013x/.r;nb|ylaeu)dM63Am?(P+02è-U@],59fq78 N_o=pcwgv41kRIéhtsSàC[jDi:050r0o0*0n0=0m0+0P0V0m0n0+0+0T010*0=0U010406050+0p0w0w0n0g0l040,0S0m0p170S0i0P020n0w0U0h0P0$0o1h0g0M0p0o0+050e1e1g1i1k1c0U04051P1I1S0e1P1c0r0=0Y0 1113150)0=0X0)0m1*0)0*1a050`0j0m0o1#1214011)1+1-1+0*1?1^1;0*0g1Q0*0)1`1%010L0|0o0i1v0o010 1n0+0U0n0i150C1;2n2p2b1|2e1^2h0w2j040c0P0z0g0S0U0S0+0=1q1s0^2l0g0g0o0V2N1I2u0i1Q0e292Z2628271=0r2w151-0i2g2K1;1Y1!101{2-0=2/0i0S2?1;0U2S1Q2X2Z341d2o1s2^2c2}0g1h0m1a0P0!2W381b372v3a1|3c3e3g0C3j2p3l2X2,013q0n3f040P0u3u2Y1c3x3o153A3C0P0Z3G3w383y3M3g0J3Q3I3S3K3z0S3d3B3g0t3X3m391$3p3$3r3D0N3+3J3.3L3:3(3D0O3@3Z3_3#3%3N0K3 3n413U040!0B463-2_423;0!3i1J3k3Y474f490!3t4k3v4m4e3b3{3C0!3F4s3H3,3T4x1a0!3P4B3R4n4w434G3W4J4u4E4N4a3*4Q4D3!4p3?4W3^4o4F4a3~4#404%4T0!454+4L3/4T0C4c4;4v4?3;0C4j361V321I2?2$0r282+3!0V2~2C0@1Z1Q310o333k3Q055a0^5i4=3L1a1Y5a0R0n0j3Q0P4X410S1a0T5x5z4o0j5r0=2U5k4$2c19040y0q3X4R3!0#5r0o0L5L4,2c0W3g5Z5p3z0L1a5a0i0+260p2M5(4{155O0y5?3T1a0#5{3!5O0q0?3X0P655y5M1|0+2s04011A0i0Y0S0=1_110P1-5/1_0^0~0+1E0o1^221G0P2P0`0|1^0P5V64665F2c5V040=5Y4J675!3p5}5E68155B040T5D6M6G1|0w0=1a4_366S015O634Q666/6N5)6I2S0*0p0g0i6R6O5^1a0/5Q0H5S6/6Z5q046m0*0o0R5~6Y6*6U6X346;5@6+6 726.6F6*6I0L3$6|5)0i1a0*0R0X7t7j0S5$6J6{7d6}3z5H040g2p0X0o5 415_7P4o6Q4J757k04626E6:7i5|047x0r7A3y7f7+4Y7U7h7W6U0E7.416#4G7^4f7?7|3b7w7y7!6:7W7q7s7G7u1a0X0n0p0V0)7O887B7D2{7 6P045s0S5u5w7V6*5O0/7S807(828s7H5O0H6-34067#7#851a7r0g8l760r2H2M8g7;7e8j7F8T7H7v8n5J8p5v8w1|8u8(767)8+7X8D838H846*8Z0+0#6t8N017-8h3y7R8A89048b8d8f8.5O0I8|8Z8P6h79981a5R7n8=8I8@1a787a7c6)7H6U0f8.8Z0n0U0U2g7*927j919r938_8{9C909h838J7K0_6_8W3k7$7/770=6n7b5S9N0^6L9F7j7D5y9J4Y5+940(0i0D2S8q9g5P9v1a9R3v7W618E4l746*6a1a010.0S1w0m0D796x8#8q0P2J6_0P0*0S1p6w1^0~100(0~2P0B0P0-0P1s2{100p0+019M7p8K878X939q9S7=8V9b7J7L0i7N9@5`9+489`8|6U0A8|7`4a9@7Z9j8?7H6I6K9b7:aK8U9`0S0*aXaM8 9U8o9?aU4f6,8;8H7W9cad8%a~5N6 9_04aJ9|8t1a7maH7B5Ca.045-5/0g5;a@b78)1aaT9%7%bc2Y9}9L4W0e5m5h1T520e541I0*56bJ2)2!5v1^2Z541O5o7j2S0w0R0L0n8`0R0)0u1a1A1C6s0~9 9|1V3l2?3y0n0r0w1r2M0=1r0P2{7r1a1Ob?b^b`2N0E170*24040zak1D0p6h0P0p2O5J2N2h0=2S0I0P0_af12ch2/6l9Wab0x1T3l1Pccah5/0S0V8`0g6l6w0gaq0p0m0`0*0+cpb}0n0 0)6h2Lcp0r2paocr0o0d0o0g0V5J0ocpciac2Ub|0icm2S0P1E0=0P2S0X2H0p9zcK0~1i0j2S0~2ocJ6z0m1^0f0P0.001G0*cu0=6s2B0idkc#5.cu67261r0X040j1paf0(c#0X0S0Xdm1F2WdvaQ3DagcJ0(0Y8RcJan2l0i0LaAc@d50Y2Td4cw6nar6jcx1G0fd-cAbT0s0{d9cdcu1_bn8d6^c`2P0r1r0i0(6wd dpd$ap6q1rdk1ddKdxajaAdJ2HdLd$2{5se31_atav0Qcq0dazcp0|cq5/0P0j6i1s0U1o0~2hd|6t6x001p0|9Wc+duehdxcid*6negdw3D6y0{dd1_eqdN0PcFcHeN0V6t0n9ub:bT0v2{2Ld^0Pd!0g2LcUd!0Ve@9o6x6wd6d8ey2{0{f4aP0Xe2csdbeY6Bdj0P6-1W5d2@411~1,1.1:bU3y2y2g2i1a2E0,0V0g18dk0z0l291r5k5gbU355jbDfr9U5v0R0.0n0`119{2Y9T5Abja`7Q6 700q0Hbg4l5T416I9#8.9)9v9-fa9:9=b6bv60btba0Qa%b.4C6*9)6Fbr150+0ra401a5a7eCaac/e%c}0j1G6h0icp6kf0fPfRfT2ve$eedkekc.1tcP1yf 4`3yg83g66dTf36wcv0+e9c{1Ff16q6s6u790~5Q0P0k0P0y0acp0a9i8F7WgF3D66gbaCa)b3aWf!7}fZbh3T7J2zaSbagqfS3B2pa%aDa+1a0W1)1^bkfV3D7=1a02gAbkgCf{f#04g11b8=g;9V9XhbfXg@6V8|8uf*4thoaE048Lbk7x7zg?2c7C1a8khH3paO7M8S5jbe9^g63zg=hja 9hhm8G9k65hp8-hM6Tg^a:8YhWh-5)7~h*01a#4 h:bi047@h?8ZhFb19lh5hCaGh`7%958ehQ3vhthIa_g_fO0jfQh0fU9@8vhUh 8zhXb8048:a)h$h%hBhDh~5r8Q9fh?hJ7Ebkg gshbbz04imiq8mh)iN6~ish!iv9khpf`i63!8~ifhkbuhRh.948ci99@9aiz8niBiabyhSg(a0iUb29mhq790RiJ7e1ae.iQhV049x9z0i9Bj49Ei(93iXbd8BbA8FhAi)iHh1j09sj2g~9y9Ag}in9nd+i h3iu7oi)hshd040A7giY7_6$a$bBfMbFbEbH5ebT0%c-cp5l5bj6ihgrjn0/0B7mfMeweafMf%j(jXfh0 diexeRd%ab6p0PgJd)aifeendf0.0_abf0fg5a1w2Kfb0reJ1s0(0m0(dodk0?5yfM5Q1Ij)1y0m00gJe^0=0^e.fj1S0=0w0Xj{cP150b2k3!0*0W1B0S0:6$e%c,1(220U0+0?0ebC0r0i0f0:g86t1Z0g0f2/0*0e1+0e0:0^e)0r2!kJb_kM0G0!0J0f0!0f0B0e1{0_0+1J0Y0X0e0C0t0n0B0f0+l62kc81^150?0W1i0i2{0X0?010e3D0;c$0 k31_e_e{gm0Pb}f@9;1_0:aA1E00eperazdf0;1r0Vcpgu7L0Yj cJ0ne}d$j|f1j~6A1_0JcTaxln173BeM7Lj{lZjW5nlEf_0j0y0t9ijNe/1R040F176mfSc@fhd/fk3yfn201/2t7Hft2A2C2Ea65.1n1_fDfFiJfI3,fK9|jN6*0X5O020X0*0hmAmCmE1ybal_7ajfi?jhhTj4a#4Vjbji4l7WmyhemBmDmYmG9*j40ig{2gjum%1ajmikhU8*hUa#4PmSisi^4tmV6U0Z4rg)bCjXjObRjR53n5bH0_eY0+04.