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
- Si la liste est vide, on renvoie un arbre vide.
- 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.
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
.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.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)