Aller au contenu

Arbre qui se réduit

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

Arbre qui se réduit

Pour les besoins de cet exercice, on définira la notion d'arbre qui se réduit.

On dira qu'un arbre se réduit, si pour chaque nœud l'arité de chaque sous-arbre est inférieure ou égale à l'arité du nœud.

Exemple

graph TB
    N0(( ))
    N0 --- N1(( ))
    N0 --- N2(( ))
    N0 --- N3(( ))
    N2 --- N4(( ))
    N2 --- N5(( ))
    N2 --- N6(( ))
    N6 --- N7(( ))
    N6 --- N8(( ))

Chaque nœud (hors racine) n'a pas plus de sous-arbres que son parent. Donc, cet arbre se réduit.

Contre-exemple

graph TB
    N0(( ))
    N0 --- N1(( ))
    N0 --- N2(( ))
    N2 --- N3(( ))
    N2 --- N4(( ))
    N2 --- N5(( ))
    N4 --- N6(( ))

Il y a un nœud avec 3 sous-arbres alors que son parent n'en a que deux ! Donc, cet arbre ne se réduit pas.

Efficacité attendue

L'objectif étant de ne pas recalculer l'arité de chaque sous-arbre, ceci se faisant de manière récursive... Celle-ci étant ensuite utilisée de manière récursive pour savoir si l'arbre se réduit...

L'objectif est de n'avoir qu'une seule fonction récursive autonome se_réduit qui renvoie seulement un booléen.

On n'utilisera donc pas la fonction arité vue précédemment.

Exercice

Coder une fonction se_réduit qui prend un arbre non étiqueté en paramètre et qui renvoie un booléen :

  • True, si l'arbre se réduit,
  • 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 : ∞/∞
.128013x/.Tr;nbOylaeêu)dV63Am(P02è-,59fq78 N_o=pcwgv4F1kRéhtsSàLCji:E050r0n0#0m0,0l0$0K0Q0l0m0$0$0O010#0,0P010406050$0p0w0w0m0f0k040%0N0l0p120N0h0K020m0w0P0g0K0Y0n1c0f0H0p0n0$050c191b1d1f170P04051K1D1N0c1K170r0,0T0`0|0~100!0,0S0!0l1#0!0#15050=0i0l0n1W0}0 011!1$1(1$0#1.1:1,0#0f1L0#0!1=1Y010G0@0n0h1q0n010`1i0$0P0m0h100A1,2i2k261@291:2c0w2e040a0K0y0f0N0P0N0$0,1l1n0:2g0f0f0n0Q2I1D2p0h1L0c242U2123221-0r2r101(0h2b2F1,1T1V0{1?2(0,2*0h0N2.1,0P2N1L2S2U2 182j1n2:272^0f1c0l150K0W2R3316322q351@37393b0A3e2k3g2S2%013l0m3a040K0u3p2T173s3j103v3x0K0U3B3r333t3H3b0E3L3D3N3F3u0N383w3b0t3S3h341X3k3X3m3y0I3$3E3)3G3+3Z3y0J3/3U3;3W3Y3I0F3`3i3|3P040W0z413(2;3}3,0W3d1E3f1O2}1D2.2X0r232$3V0Q2_2x0/1U1L2|0n2~4g4f3q054q0:4y424a0X150:0G3L3%3t0R3b4M3:4a0h0G150$0n0M0f0Z0r0p2H4R3{4a14040x4)4G36151d0i2N4/49274,0q0-3S0K500K4N3V0$2n04011v0h0T0N0,1;0e0f1A0K2G0K0l004?2N5i1;4!4$2H0D0K0V3w4X5i2?1m014 515343152b0G2k0#1C4A2T524S270N150O3L5P4*4;045n0n5D505F4T4=0f2H0Z0M2^0n0p0r5V5(5R5T5?5Q3k0i152u4_3t4,4.5N4F4`3k5H4U5K5M315{104|5$5W4:1@4I040G3X5`5X67040$0N0p0$0M5!6o6i100N4P042?6y663G685J0h5L603V4,4~6406516S6h6G3u150P0;2H6v5I6a6F3t5S045U646U3O4W6t6v6x6Q6T5E6d016k0,4L6-5@5|5~2b6M3|62745)046Y125L0M6$6K6b4g6`6f6 6`6*020S0#0g6(3V0h5*5,5.0N5:5=64706e156P2 6R6^6T7B6{152N0#0p0f0h7r3|0X0Q155w0^5#6@7H7J6|6~2 6.3V6B152^0#7R784X4Z4#4%7.7A7i15636c6p6H6r6;6w0f4@7Y7}6z014|7E3f7G7H6_7~7K047M7O7Q7k8f7T7V5x858b6S7#7L0;8j7/278n045f1A3$0c4D4x4h8G0c4k1D0#4m8L2!2V0m1/8I4k1J653t2N0w0M5J0X4Y0!0u151v1x1z1B0K8a4B1Q3g2.3t0m0r0w1m2H0,1m0K0r2k0S0n0f151J8^8`8|2I0C7b1 040s1d0,5K1;0m0T2O5i0#0k1:0K6m0h2P8~0h2*0l1O8?1U3t1_1%1)1+8W3V2t2b2d152z0%0Q5+0P0#2A0k241m4M4w65304g8F9I7S4J0n7%7h8f6C527_8f4U4W4Y5r7@774{7{9{6q6?866V896g7J5515582b5b5d0K8B1;5j5l5!5p0K9_5t5v8p5z2^7ta46`7t5Z5+0#5-5/5;8x1@6*6,7(7J0h5}045 9;8776aK6Vata09-aL150qar8m8u7N7PaA3GaH3w9zaN619}7Z6^7JaMa13OaHaJa:6Na+a@5G806u82849~7C04aU8l877m0l7paD3f7)a{9haw7w7yb088aTa!017+5Z0h7zaEas9@7=5s7^a`4+a_aRaO6:a}aQ4B7`b26g8s6`6k6m0fbkat6sbC834^b46Vbm6EbT6/aua a,bbbxbG6Q1D9%8H2U8U1M040)0m9s1m9v8 4C4r5Z0la(9%aja95c1;b`4Eadb*b{5z5P211m0S040#6;2Rcb0hcd5k8.0Z0l0Z2w7f901;5l5,0f8R9r1z0,5k4%0K1B9T2j0~0ZcD1n2jcw0w0B21ae1m9T0Z0T3w0p0Z0_0(529%c68Eb{0d9A178J4u1S0;0?0^3t91cj9496181a1x1f0s942G8 9l9nc44x210kcD0b0Q0n9Sc74E2Rc{1H3g1K0*0;0#1;4q0h0$210pb^1nd20Q0K0p2*b?9u2I0K0m0p0b0@9i0,5o6Y380;905maa0fdx344r0K0P1j0_2:dJcD9Tdo0Q0,0$c)8=8Vb;dAdtdDdFdH0?5odz2N5ac2aj5d0h5u0nb}1;0T0Z5+291;0+6udm5u4!0Q7O2G9mcq0#5u8-0Kcf1kcDdq0K3H0d0K0.e2dV2C5beldy1;942N7O0Kczep9Ted0p0Pe50Z9k9mdwd4ce1ed8dadcc%4Ecl0`0}0K0Z0Q0!0Z5Kd+1R4t2/3|9E1{1*2o8f9K2v2x9O9Q139T0y9V0!9X7A9Z3%9#4Bb+bJ9*9,bE9.4Qa)7s4V6r9^7?4(fh75byfe87aPbR8qfra2aT8:3CbI8fa65759aa5e5gaecAagfuaiakejam7Xao5B3S8cb$270Q0W1503d/dCdEdG1(d@1;2?dm7PfvfA8e876k4Kbh9/bh9?fkbt7@6wdFbha/bzbYbD2Ta.fybHf=6VfD010L5qc1ab5+2b5u2|0Nez5heBcD2M5:dRaf5mfMdz5yfOdV0}5Cb#fBfs6I6%bX7*5_gJbcfuga5%brau7vaybpba7JaCbNa=73fob%7|g47sgH7fg2bjgEgb3tbK6ngM7:81g63ygX6CbWbq9=g+6Lg$9|04fz168dgFbA796Z7c7eh2g b5gLhghabP6=gOg/a-fb5Z0~94bvgWasg!8kbwh4g(fwbY7a6!7d69g,h31@7jhj6)1502b70gb93qfW9 avax7xaz6QfV7JfYf!1u0;6tdR9td:0n0bf.2*aVf?15d6g-h5gPhU7 7;fOg00bh`hBg7gRg`g8b(7Fh9g;5Hd9dbhuhCa^h{6-h}01h%04f#gqeDgt5i00cEex2_7@0n5u0rb@h|8t8h8vaZg@8y7U047W4XfUib4pfZio0K0vdsiqgs7Oh?6V6k8iiHhM3V8zc$7Fdd8If6c,0Tdi040jcK5:9T0w0o2w521w8hfmbSi 5kb=h-f%d=f*dJeC1n05i i@0n0)2?941Dj31tdq9qeCh:0fi|1;apc04q1GbocI0$dE0G0KcZ0:hs2?e-9Be:4ae=9Ge^87e`9M2y0K9P9Rf0f2f431f6317Afah0f}i0f(bkgYiI6j5~1q0i91bN150vh`h6il6k1?htgZ4=b}i3f{hxk3hJ7 0mh`b3i(3|b6b8k0aIg#hzhKfqi5j(j_k7bii9hvaW6lg?kc78k9j.6Ag}hyksgG04kokjb1kb8bi-2Ui/b.8Jc/0@0$3gkP0=kR04.