Aller au contenu

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 (tg) et ร  droite (td).

Formule sur les tailles ร  vรฉrifier : (1+tg+td=4)

(tg=0,td=3)

(tg=1,td=2)

(tg=2,td=1)

(tg=3,td=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 () | (โ‹…, โ‹…).
Aide
  • Si n=0, c'est facile ร  crรฉer, avec dico_ab[0], par exemple.
  • Sinon, on fait une boucle pour k allant de 1 ร  n inclus, et on peut utiliser les listes des arbres binaires dรฉjร  construits.
    • On construit (si ce n'รฉtait pas dรฉjร  fait) tous les arbres binaires possibles avec une taille k, composรฉs donc d'une racine et de deux sous-arbres binaires dont les tailles tg et td vรฉrifient tg+1+tg=k.

On recommande de crรฉer une fonction auxiliaire pour un code plus propre.

Guide
๐Ÿ Script Python
def construit(k):
    "Renvoie la liste des squelettes de taille k"
    if k == 0:
        return ...

    liste_k = []
    for t_g in range(k):
        t_d = ...
        for gauche in dico_ab[...]:
            for droite in dico_ab[...]:
                skel = ...
                liste_k.append(skel)
    return liste_k

def gรฉnรจre_ab(n):
    "Complรจte, si besoin, le dictionnaire dico_ab pour toute clรฉ de 0 ร  n"
    for k in range(n + 1):
        if k ...:
            dico_ab[k] = construit(k)
dico_ab = dict()
def gรฉnรจre_ab(N):
"Complรจte, si besoin, le dictionnaire dico_ab pour toute clรฉ de 0 ร  N"
...
# Tests
gรฉnรจre_ab(3)
assert sorted(dico_ab[3]) == [
((), ((), ((), ()))),
((), (((), ()), ())),
(((), ()), ((), ())),
(((), ((), ())), ()),
((((), ()), ()), ()),
]
ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
###(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)
rounded
>>> 
 
x
x
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 : 5/5
.9888.128013.8901y@ร - ;ak?s_v3hbP,e[6N1xDARnfuj|cรจm4.wS2tl]+5รฉgroICd/0U98)p:7i=(Mq050#0u0Q0j0/0R0m0h0I0R0j0m0m0:010Q0/0,010406050m0F0K0K0j0X0d040O0Y0R0F170Y0D0h020j0K0,0i0h0C0u1h0X0?0F0u0m050$1e1g1i1k1c0,04051P1I1S0$1P1c0#0/0o0 1113150q0/0W0q0R1*0q0Q1a050`0r0R0u1#1214011)1+1-1+0Q1?1^1;0Q0X1Q0Q0q1`1%010E0|0u0D1v0u010 1n0m0,0j0D150P1;2n2p2b1|2e1^2h0K2j040b0h0s0X0Y0,0Y0m0/1q1s0^2l0X0X0u0I2N1I2u0D1Q0$292Z2628271=0#2w151-0D2g2K1;1Y1!101{2-0/2/0D0Y2?1;0,2S1Q2X2Z341d2o1s2^2c2}0X1h0R1a0h0y2W381b372v3a1|3c3e3g0P3j2p3l2X2,013q0j3f040h0p3u2Y1c3x3o153A3C0h0L3G3w383y3M3g0U3Q3I3S3K3z0Y3d3B3g0w3X3m391$3p3$3r3D0.3+3J3.3L3:3(3D0*3@3Z3_3#3%3N0)3 3n413U040y0%463-2_423;0y3i1J3k3Y474f490y3t4k3v4m4e3b3{3C0y3F4s3H3,3T4x1a0y3P4B3R4n4w434G3W4J4u4E4N4a3*4Q4D3!4p3?4W3^4o4F4a3~4#404%4T0y454+4L3/4T0P4c4;4v4?3;0P4j361V321I2?2$0#282+3!0I2~2C0@1Z1Q310u333k3Q055a0^5i4=3L1a1Y5a0n0j0r3Q0h4X410Y1a0:5x5z4o0r5r0/2U5k4$2c19040;0+3X4R3!0k5r0u0E5L4,2c0N3g5Z5p3z0E1a5a0D0m260F2M5(4{155O0;5?3T1a0k5{3!5O0+0-3X0h655y5M1|0m2s04011A0D0o0Y0/1_110h1-5/1_0^0~0m1E0u1^221G0h2P0`0|1^0h5V64665F2c5V040/5Y4J675!3p5}5E68155B040:5D6M6G1|0K0/1a4_366S015O634Q666/6N5)6I2S0Q0F0X0D6R6O5^1a0v5Q0S5S6/6Z5q046m0Q0u0n5~6Y6*6U6X346;5@6+6 726.6F6*6I0E3$6|5)0D1a0Q0n0W7t7j0Y5$6J6{7d6}3z5H040X2p0W0u5 415_7P4o6Q4J757k04626E6:7i5|047x0#7A3y7f7+4Y7U7h7W6U0g7.416#4G7^4f7?7|3b7w7y7!6:7W7q7s7G7u1a0W0j0F0I0q7O887B7D2{7 6P045s0Y5u5w7V6*5O0v7S807(828s7H5O0S6-34067#7#851a7r0X8l760#2H2M8g7;7e8j7F8T7H7v8n5J8p5v8w1|8u8(767)8+7X8D838H846*8Z0m0k6t8N017-8h3y7R8A89048b8d8f8.5O0t8|8Z8P6h79981a5R7n8=8I8@1a787a7c6)7H6U0M8.8Z0j0,0,2g7*927j919r938_8{9C909h838J7K0_6_8W3k7$7/770/6n7b5S9N0^6L9F7j7D5y9J4Y5+940V0D0J2S8q9g5P9v1a9R3v7W618E4l746*6a1a010!0Y1w0R0J796x8#8q0h2J6_0h0Q0Y1p6w1^0~100V0~2P0%0h0f0h1s2{100F0m019M7p8K878X939q9S7=8V9b7J7L0D7N9@5`9+489`8|6U0T8|7`4a9@7Z9j8?7H6I6K9b7:aK8U9`0Y0QaXaM8 9U8o9?aU4f6,8;8H7W9cad8%a~5N6 9_04aJ9|8t1a7maH7B5Ca.045-5/0X5;a@b78)1aaT9%7%bc2Y9}9L4W0$5m5h1T520$541I0Q56bJ2)2!5v1^2Z541O5o7j2S0K0n0E0j8`0n0q0p1a1A1C6s0~9 9|1V3l2?3y0j0#0K1r2M0/1r0h2{7r1a1Ob?b^b`2N0g170Q24040sak1D0F6h0h0F2O5J2N2h0/2S0t0h0_af12ch2/6l9Wab0l1T3l1Pccah5/0Y0I8`0X6l6w0Xaq0F0R0`0Q0mcpb}0j0 0q6h2Lcp0#2paocr0u0z0u0X0I5J0ucpciac2Ub|0Dcm2S0h1E0/0h2S0W2H0F9zcK0~1i0r2S0~2ocJ6z0R1^0M0h0!001G0Qcu0/6s2B0Ddkc#5.cu67261r0W040r1paf0Vc#0W0Y0Wdm1F2WdvaQ3DagcJ0V0o8RcJan2l0D0EaAc@d50o2Td4cw6nar6jcx1G0Md-cAbT0=0{d9cdcu1_bn8d6^c`2P0#1r0D0V6wd dpd$ap6q1rdk1ddKdxajaAdJ2HdLd$2{5se31_atav0xcq0zazcp0|cq5/0h0r6i1s0,1o0~2hd|6t6x001p0|9Wc+duehdxcid*6negdw3D6y0{dd1_eqdN0hcFcHeN0I6t0j9ub:bT0B2{2Ld^0hd!0X2LcUd!0Ie@9o6x6wd6d8ey2{0{f4aP0We2csdbeY6Bdj0h6-1W5d2@411~1,1.1:bU3y2y2g2i1a2E0O0I0X18dk0s0d291r5k5gbU355jbDfr9U5v0n0!0j0`119{2Y9T5Abja`7Q6 700+0Sbg4l5T416I9#8.9)9v9-fa9:9=b6bv60btba0xa%b.4C6*9)6Fbr150m0#a401a5a7eCaac/e%c}0r1G6h0Dcp6kf0fPfRfT2ve$eedkekc.1tcP1yf 4`3yg83g66dTf36wcv0me9c{1Ff16q6s6u790~5Q0h0H0h0;0ccp0c9i8F7WgF3D66gbaCa)b3aWf!7}fZbh3T7J2zaSbagqfS3B2pa%aDa+1a0N1)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_fO0rfQh0fU9@8vhUh 8zhXb8048:a)h$h%hBhDh~5r8Q9fh?hJ7Ebkg gshbbz04imiq8mh)iN6~ish!iv9khpf`i63!8~ifhkbuhRh.948ci99@9aiz8niBiabyhSg(a0iUb29mhq790niJ7e1ae.iQhV049x9z0D9Bj49Ei(93iXbd8BbA8FhAi)iHh1j09sj2g~9y9Ag}in9nd+i h3iu7oi)hshd040T7giY7_6$a$bBfMbFbEbH5ebT0Zc-cp5l5bj6ihgrjn0v0%7mfMeweafMf%j(jXfh0 diexeRd%ab6p0hgJd)aifeendf0!0_abf0fg5a1w2Kfb0#eJ1s0V0R0Vdodk0-5yfM5Q1Ij)1y0R00gJe^0/0^e.fj1S0/0K0Wj{cP150a2k3!0Q0N1B0Y0G6$e%c,1(220,0m0-0$bC0#0D0M0Gg86t1Z0X0M2/0Q0$1+0$0G0^e)0#2!kJb_kM0e0y0U0M0y0M0%0$1{0_0m1J0o0W0$0P0w0j0%0M0ml62kc81^150-0N1i0D2{0W0-010$3D0Ac$0 k31_e_e{gm0hb}f@9;1_0GaA1E00eperazdf0A1r0Icpgu7L0oj cJ0je}d$j|f1j~6A1_0UcTaxln173BeM7Lj{lZjW5nlEf_0r0;0w9ijNe/1R040(176mfSc@fhd/fk3yfn201/2t7Hft2A2C2Ea65.1n1_fDfFiJfI3,fK9|jN6*0W5O020W0Q0imAmCmE1ybal_7ajfi?jhhTj4a#4Vjbji4l7WmyhemBmDmYmG9*j40Dg{2gjum%1ajmikhU8*hUa#4PmSisi^4tmV6U0L4rg)bCjXjObRjR53n5bH0_eY0m04.