Aller au contenu

Arbre cartésien

Valeurs toutes comparables

La notion d'arbre cartésien n'existe que pour les arbres binaires dont les valeurs sont toutes comparables entre elles. Par exemple : toutes numériques, ou bien toutes des chaines de caractères.

👍 Pour simplifier cet exercice, on considèrera que tous les arbres binaires comportent des valeurs numériques positives.

⚠ En commentaires, vous découvrirez comment gérer le cas avec des nombres négatifs, ou des arbres binaires dont les nœuds portent des valeurs textuelles.

Définition

On dira qu'un arbre binaire est cartésien si, pour chaque nœud :

  • les valeurs de ses deux sous-arbres sont toutes supérieures ou égales à celle du nœud.

Exemples

Il est possible de construire un arbre cartésien connaissant son parcours infixe.

👍 Vérifiez cela avec le générateur suivant (que vous pourrez construire dans un prochain exercice).

Exercice débranché seul ou en classe

En classe, on utilise le vidéo-projecteur.

  • Lancer le script sans montrer l'arbre dessiné en dessous.
  • Le parcours infixe attendu est affiché.
  • Les élèves dessinent l'arbre cartésien dont le parcours infixe était celui annoncé.
  • Pour vérification, on montre ensuite l'arbre cartésien.

Il vous suffit de (re)lancer le code sans le modifier.

###(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

L'arbre sera dessiné ici.

Exercice

Coder une fonction est_cartésien qui prend en paramètre un arbre binaire et qui renvoie un booléen :

  • True si l'arbre binaire est cartésien,
  • False sinon.
###(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.128077.9888.128013x/.Tr;nbylaeu)dV6ç3m?(P+02è-@],59fq!78 N_o=pcwgv4F1`kRéhtsSàj[i:050s0p0,0o0=0n0-0Q0W0n0o0-0-0U010,0=0V010406050-0q0x0x0o0i0m040.0T0n0q170T0k0Q020o0x0V0j0Q0)0p1h0i0M0q0p0-050f1e1g1i1k1c0V04051P1I1S0f1P1c0s0=0Z0 1113150+0=0Y0+0n1*0+0,1a050`0l0n0p1#1214011)1+1-1+0,1?1^1;0,0i1Q0,0+1`1%010L0|0p0k1v0p010 1n0-0V0o0k150D1;2n2p2b1|2e1^2h0x2j040d0Q0A0i0T0V0T0-0=1q1s0^2l0i0i0p0W2N1I2u0k1Q0f292Z2628271=0s2w151-0k2g2K1;1Y1!101{2-0=2/0k0T2?1;0V2S1Q2X2Z341d2o1s2^2c2}0i1h0n1a0$2W381b372v3a1|3c3e1a0D3i2p3k2X2,013p0o3f040w3t2Y1c3w3n153z3B0!3E3v383x3K1a0J3N3G3P3I3y0T3d3A1a0u3U3l391$3o3Z3q040O3(3H3+3J3-3#040P3;3W3?3Y3!3B0K3N1T321I2?2$0s282+3X0W2~2C0@1Z1Q310p333j434d0^4l3m3~0(1a0^0L433=2_010X1a0Q4x3}4z0k0L1a1G0,0S0W1i0,0*2L2g4E4r4z19040z4T3*4G1a0o0l4Z3x4W0I3N4D4y3b1a0x2{0=4)3X0T1a0U0F4^3~0k0l1a0L0n0T0o0,4~4V1a4Y1J4m4/1|0-0$1a002{0L00582c4W0r0r4-3)3x4`040F020Y0,0j5s5e3J51040l0T1n5n1|4W0?3U0Q5P4.4F2c0-2s04014%0Q4K0F0|0 4O4Q0=2g5Z0,0Q2P0Z3A0p0q0i0~1e0V0*0i5*5?1G0Q0/0Q4=0k0=0Q0y015O5Q5t3X4t040=4w5c3u5R4U4:044%5C5S1|0T4B6e1H6h2Y6j4!2c0(0W1a0R1r0p5K155M695Q6a5D016d2S0,5?0k6o6k1|6A1a0h0i1F6J6x3x6d0p0}6F6v4q6y5L1a5N6,066K6K6b4 1a0e6T6.155v0U6}3Q4$4(6,6_4z5v0g6G3y1a5:1^5?6#6^6M6d6f723X0k4;4?7m3~5v5y5A7r4#046|766M6I6=6@7E6$6c1a6P6R7w6z6B040#3A0-6+346?7F776z7I0_7K6,7G6`044K4M5(4R6S7A6p6H5a7b7o6m75366M797=1a0Y0o0q0W0+7S5d7/014+7L3o6{7b5p886 6s2p0s8d7c7(0-4L4N0i4P7,8b7;7.6U3J747b7{8t6~8j0s2H2M833u7W6/044,7#8H8v7y8r045r6=1I4o4k448V0f471I0,498!2)2!4%1^2Z471O6-3x2S0x0S0L0o0(0p0S0+0w1a1A1C1E5 6;361V3k2?3x0o0s0x1r2M0=1r0Q174W1O989a9c2N0F170,24040t5;5?0~2}1s0k1f5{0=916u1W051n3k1-1l659f0V5=5-0o0Z0T0=0i5.5 7e5=5@0Q9z0x9B9D9!0*7~170Z5 9x0Q5H0i0k0*1G0I0Q9M9O0Q8;0V110W0p9U058U3x1~1,1.1:8/7n7p648x4{7b4=1a0C430f8U040Q2oa3a53Xa7201/2t857?634@8z5u4{4}aC7n5F535557aG3~4W5b7_855g5i5k5maM598Qalan7a0f9J1c9J050=0x0Y0Q3A0,150c2k3X0,0X1B0T0:0=2k0-0i0W1(220V0-0?0fam0s0k0g0:0-0^1-0Z0i0g2/0,0f1+0f0:0^0W8_0s2!a_9ba|0G0$0J0g0$0g0C0f1{0_0-1J0Z0Y0f0D0u0o0C0g0-bJ2k9p1^150?0X1i640k0Y0?010fao0.9L9y1_0-0{5-2o0~910Q1^0~9X9v0Q0-1r5-9#9%1F0-9_9f2/ap9|b=0Q1p0|0=7R9U0n00126Qa15.0q4Das3~aua9ax8u8jaAaf044|7=aI54568PaP84cuaS045j4HaVaQcu8c76am4e04a#a%059Jb+9`1sb/2M0Qb@b_0Qb{9Zb~0k5-0,0T1p5 0,0p0e6Q6)b_c51s9N1pcb171-cfcocS0%030N0V0m624?1568cR4p9_5+0p0L0L0_9_0W004Kb^0oap1o0~9N9p1_810{c72P8n0o2U0E2S0-cU0=9IdLa*a,a.0na:010ba?3~a^a`a|a~b0b20,b4b6b8babcbe1Zbhbjbl0+bnbpbrbtdY0=bxbzbBbDbF0,bHbRbK0$0L0!0!0sbQbS9g2MbV010?0B0$b%b)0QcYc6b.b:9}5*1s61ch9Q2pa19_9R0=0W650qc78@0v9f2P8@9T1_6;cV0f9H1X1Za61.avaa8M2d2f2A2C2E0.0W5|0V5-0A0m291r434j6-354maneW6d4v7b6s4DaW3b4I8k8m7+ercE7|7@8P8R347$781a5x5z5B8L6M501a5H5Je~8I933j7U5Pe^4udke{4C7=f00Z9B2e8F2YeWaOf62}5=8hfn7:aYfh855vfe7vfOcufj5G5I0n8Pfp3ufr6@eW0W5h04039!0TfJ5Z8lcb1s5Y9/0Z0=2P0N7h6Lay8afT8A708i7?fI0qfKcNg21aa#g97304c+f}fs7j523Zg41ab/7^3jfb2c6r1a2{8i4W0;fHf.g7cxgccG8A7?7~80828P8KfaeWg5gAg8gEaDcTf68C9Sc@8P0Hf!3F7Ff%gj6e6ggMfign6ng15u6sce8igt042}aLg+856W046D2/fZghg$gr1|f)1af,gof:5-eDa.0lf-1sf_0^9_b/9}dF2{1_drhc0k0agB7Dh37Eftg)gw8sgdac8Og/4_1a7ufgg{fUg-gp8G7`gbf6ggfL861af9gqeWg@glhEaNhAgRhCfA5|fCf5hS7?gof8g?g;6uhJ8Ag}7P6*f8g!1bhvhvhx7J9=8ih_7QfDh~7Vg(i27-h@6%7N6Y6!6=f$f(f*f,6Pc;9U0L1r2U9ec~5|0keB2o1^6#hx7lh!7xg.id4_h=i47Ng i7fF6:h2i17Zi3iD7M6X6Zi7ijg(6)7Rh1huhwiaiRichWg,gffB5*h,hB7%iFh%h#fNiG3~h6f+hdhahfc*f`1_f|8Sdg8Xe:464heQ2@cqeTcsab3~2y2g2i1ae#e%18e*e,0+e.76j99436e@6Mi}f,1i0ldI9:2{0{jE9Q2Tcm9gc^gXiigN740Sc@c_i7h46 agiT89g~gPi;i^4z5U1a015H0k0:iodfi=aXhVf#jQ7@jSjNiMhOgTh-7}7 81jVhXjYi{7x6DfJj%hNaR5V019b0k0^j;j(5ohU3|cu6dbF8ogmf17*8o5)4ShSfGk0j`jTjOj=kli`i,fPiIjZ15g}igiXj_4%j{jUgCgU8DkDkHcug3kK8jk9htkE8IcFkccHke0o0+kjk+8AcP7Thxkqg`kXgF4J8lku8pf4kyh$k;gekQkCj}85k?k{g:guh?lb6c7Nh`i#j6e@1V458Yjbja0Z3k8Y0_0{0}04.