Aller au contenu

Générateur d'arbre cartésien

On peut construire un arbre cartésien de manière unique à partir d'une liste de valeurs distinctes qui constituent le parcours infixe de cet arbre binaire cartésien.

Il existe plusieurs méthodes ; voici un algorithme simple, mais peu performant.

Algorithme

  1. Si la liste est vide, on renvoie un arbre vide.
  2. Sinon, on cherche l'indice du minimum
    • ce sera la racine de l'arbre
    • on coupe la liste en deux parties avec le minimum comme pivot
    • de manière récursive on construit les sous-arbres cartésiens
    • on construit alors le nœud racine à renvoyer.

Exemples

À l'exercice précédent, vous avez pu générer des arbres cartésiens associés à un parcours infixe.

Exercice

Coder une fonction générateur_cartésien qui prend en paramètre une liste de valeurs distinctes et qui renvoie l'arbre binaire cartésien dont le parcours infixe est la liste valeurs

👍 On pourra se contenter d'un algorithme simple. Un algorithme plus performant sera présenté dans un autre exercice.

###(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 : /
.339.128013x/.ùr;nbOylaeu)dVM6z3m(Pô+02è-],59fq!78 N_o=pcwgvF41kRIéhtsàSL[jDi:E050r0o0+0n0?0m0,0P0V0m0n0,0,0T010+0?0U010406050,0p0x0x0n0g0l040.0S0m0p190S0i0P020n0x0U0h0P0%0o1j0g0L0p0o0,050d1g1i1k1m1e0U04051R1K1U0d1R1e0r0?0Y111315170*0?0X0*0m1,0*0+1c050|0j0m0o1%1416011+1-1/1-0+1^1`1?0+0g1S0+0*1|1)010K0~0o0i1x0o01111p0,0U0n0i170D1?2p2r2d1~2g1`2j0x2l040b0P0z0g0S0U0S0,0?1s1u0`2n0g0g0o0V2P1K2w0i1S0d2b2#282a291@0r2y171/0i2i2M1?1!1$121}2/0?2;0i0S2^1?0U2U1S2Z2#361f2q1u2`2e2 0g1j0m1c0P0#2Y3a1d392x3c1~3e3g3i0D3l2r3n2Z2.013s0n3h040P0w3w2!1e3z3q173C3E0P0!3I3y3a3A3O3i0I3S3K3U3M3B0S3f3D3i0u3Z3o3b1(3r3(3t3F0N3-3L3:3N3=3*3F0O3_3#3{3%3)3P0J413p433W040#0C483/2{443?0#3k1L3m3!494h4b0#3v4m3x4o4g3d3}3E0#3H4u3J3.3V4z1c0#3R4D3T4p4y454I3Y4L4w4G4P4c3,4S4F3$4r3^4Y3`4q4H4c404%424)4V0#474-4N3;4V0D4e4?4x4^3?0D4l381X341K2^2(0r2a2-3$0V302E0_1#1S330o353m3S055c0`5k4@170$1c0`0K5m4(2e0W3i5x4.3d0K1c0X0)0i0)0g0n0+0o0p0g0R0V1k0+0)2N2i5C5r011b040y5Y4}3N1c0Y3D5O0g1J4L4Z435#0q0@3Z0P5{0P5=4h0,2u04011C0i0Y0S0?1{0m001k0j2U0P0j2}0}6e5S0g5U5W2Q1t0+0P1`0P2q0g5c5P102}2g0c1{1I6q2q150)0P2i0P5,1`6x015`5|5~2e5t040?5w4L5}5y3r5+5-6x3S6Y5D1~0S1c0T0T6(6R1~5#0:0G5_4S5|6{6)5Z6T2U0+5P0i6:6Z5s0V1c0Q1t0o6P5{6;5s1c0o0 7b5;755!1c6_36066|6Q7l0i1c736X7e016,046/7x7t0j1c2B5(3A5#5%7k6*5*046L5.5:387l5@3Z7q7r6}5)3B1c0$0R0x2}0?747N7z6-7,5Z7)1c4{7p7Y7Z3V1c7)0i7+7D7-7A7C367`4!6#6M5/7I3$6?8a437=047@5l7U1c0G7c6|7y6T0K3(7:7!7u040$8s3A0S5A6U7w847y0i7F045L0i0X7j7T7-7K8d4q7v8P2e5@7o4n7_6{8E1c0c8x3$828$4a877R8S6=1c0:8-7O8w7M5Z5#8l6`8X7d7l6T6V8)8Q048#805Z7A020m0+0h913d7|7*8;7m048V4v8|7r8Z047}7 8D7l8(958t8!8m9l858*8v7(9f9u8y7/9E868v7W7_9n7Q6x0R0X0n0p0V0*8L3m9z4h9t9r8N8/9g8u9N898@7!8c9+7{9J9.8b8k9c1~8p8r9H9A8?9!968A2}9@3N8G8I8K9g8O9;9|9C7~a71c0q8`7^7Y9n9Q9S9Ua27.7Ban8u5H5J5L5N5P5R5T5V688C8i9#5$9%8+9Oak9T9V3x7y7V8{9m7taG5/0R0r2J2OaK2!9X2e9Z9WaM9$a9929)7SaC8^a(8M5Z8u9}a-9,9?9{4h9_0gaq7$an8z1ca1a`3da42ra6a)8T1c7La:9v9B9pb01c0Ban8f51a@7J1c0Ha~04aBaL8j04af9x7s7-8uaU675Nbhapb46!04as5K5M5.ax6laz5Xb98.aEbS7Oa+aTaVbEbV9h0q9Kai8~1c7072br795O0radbUbd9/bgb#5#bqbH7OaIamb`bpbrbCaWb=b%4Y0d5o5j1V540d561K0+58cg2+2$0n1_cbce5g1Q5q7!2U0x0R0K0n0$0o0R0*0w1c1C1E1G1I0P9j2!1V3n2^3A0n0r0x1t2O0?1t0P195#1QcPcRcT2P0F190+26040z0S5P0P0)0YaW0g6rcI5c0U68102R1/0,b!1Y1T040k3b0g0)1{0p2;0P8q0i2WcV1u9R0c0~0?6i1{1G0?cX5L5,0~6s0n0Y2Vc_6y0i1!0V1I0ecMcr0^1u2b0)3(68117h0nc;c?5NcXc/5N106s2Uc{c}0Pc 0?d10o0e0P0t0}dX1{9Q2}0Pd87h6Id16t1q0+0A6qcx0?cndF1X3n1R0/1{cSavc^0z0l2bcW0r0)5N2Wdo1H6rdQd!1{d@0m6s0i00eh0}6E140P1r2h6I6q28dw0}er1{6ud?0)0K5K2idD0P0,2r10eoc^0MdG5f2_43201.1:1=cs3A2A2i2k1c2G0.0V0g1a6qeceebtcL5ics375lcae)3$6T5v9g8A5}b#0i5FbJ5IbLeabO6maAb=bcbn9Ia+c6cK1d8Yb*04f4b#f69%fadjdldnfiaF6Ub=b|9~be0;fnby8}7-8 6WfG9/9qa$9s6-83fSbA1cfIc19ifK8nfrb,0ge`3F8o7704792;f$8o7g7ib=fo7X8|9n7%b_fP8%9Gg09AfR9k9l9nf fW96g2gabefmf!8:f8b2b=ag8Wg7fr8qa}b}7#9:g39Ya0f+aZ3rb68JaXf15?bbfCg5cLbvfFgd9/fZb@9=bwf`9yfqfX93bFfV3xgybW6$9*gOgE04ghg%92a?buaDglg6gSgZ01fNbr94gua!1c989abrg9g.a.f#aOg=bza;9eacgra#gY9ng`gmh6h7bef~9Dg{6+gchdaQgt4nf{8Xaj9RaJgWbrfy1/fAf!fjh2begHgD4hb{brhkhag+babwf$gTh8fsbZgCg?hcaY9nhAdm0?2UfBgibfhlgLg104bjgrblfEbrgNfkg(c7ahf|f(0{b-gr8ub/0pb;hDfCh1gIaDgKhpgUb gCa%04ibhZhqc4b!hObTh{hgg?6 h f*hz0pdkhBh%ifbvhEi97;0?7?h?i18G7Hi6h*gfin175@ip4v1Kf0ccco561ecp0YcN0{eGeT430rb70o0g1c3K1h1E1m0si,2NcW0Ui,gp1j0i5N0H2n1rdU0p0;c/5/6r2}0)hC1Mi;e5040Z0neP0-ezdi0g6d1{egbKd86r6b0m0XdM2b2D6td80V0)0`i~6t5O6q0`dx7~c^280Ed/i~e3d31R0(0md_6E2M2Ncnd$d:1k0`c^db1{5c0id10g9S2P6IdJ1D0UdXj9dn0PcHeHj{el0,bDjs2i28d90Pdwdydb0P2Ddu5.k6jujw0*2DjQ3n1p3n1/d53b1tj-0p2Ojs6c2Uj06J0nj51r2r6qj)6Kg#0Pjj13dd670,j0c dQie6Ki@emd$hVe3kn1eknc.c:eR66h%0P0S0fkukA5Nc^cWj+0,i,dxjkeIeB0`100i0ai4100+dVkHkUbD1{0;0p0,1G6b0pj!f*68c^kzdVkW0?kmlkd6d$0)c|6sl7l90p00jj2}0,eNc^esc/dx9R0Pk}i4k6lc0jcW2iilljllko6I1yeBlB0plDlclG5ad80)lOiYklcr0/eue;2O5Pjoj*j*5djVk6150o0vlo1/5SdTj+dDf*kCjs7*193Dd(5Mdhd+d-d(c_jz2}0V1ad:fc5LjU6Dl@k=l`cm3(i*e2eXcO3$e#221;2v7-e+2C2Ee/l,0Ue@ed0*1t5me|3.e~aLiUfrftiO01fvf8fajqbMaw6kfgbRmUa8mU9(g#a,hFbogQ8mf?6UfOh-4aiJm(h_hJgFiMm-c6gWgXij7-8f8hm/gPgRb)fMb+itgxf-787am=fr7hk=f_f=hqcmhygr0$f.f:gChthSbej%7~i,nshm76nif;h5nz9/lqhW7yhYf,bv6@npnd04gpg_b0gwbriNm}hPnbh}nU0W1+1`brnMnY1c2ri5nFgsn/gg9g7A0F9gh=f!g:iD7!7Ae3m+aRbF020Xg i19wf!n(gS9nnBlfnEm_92n_mUo4fC2L0UfiiR3J9ym?90oc04onolg|7Bn4nQaD6@ofownq0jokichTi3n?n$bTiChI9dgVf!iioGhToinDoYannunHiAaDoufph69noBn943oph*0n0Ui`dBh)o604nrf!o.nync6~f@nnoehRp5bejh717hoNn5hTo=o2m:g*oS17n|n~iF4cgkb(g=9n1g1#kCpgo!pc2W1H0mn{1co5pngsilnxhh9n2 lV0o9RpAg?i20Sb:o~pJ8uhfo?m~ihbrpx5,i~iHn@o*f/njp2paaPgUpdpEpG04pIp$oWpLpTpOlCpR0pp?f%gUpjoVhnp|fCo`o|oRp~oTfCpPlWn24Sp4n)5Z0V0#1c03nM0eqelM0y0yp_7h0epLcJ0T0PoQ0y0cj0qB0mqDhVj0nw0qqSq6nK5bqs040303jFj2cu0U13m0dz3Qj80X2;c~l;2R330)jBjDdWnknUf)ngoL3-c95d2#mNiZjek!c^ls192gi,j~69l;j2mm2:jaizj00~l?2`k(cHmd2 0xjndU0|jU0r00j?2h2Di~10mm0o0cpd1Dk3kT0m1t0X1Hc:kOj8d)d+0=1t0Vrr0Srt6el1rw111h0p0m6H2R5nr2oriTr2l?1/7)5U6t1kkT0|kcj!rLd(5NkjiY0`r}0 3ncei$0~0,04.