Nombre de feuilles basses d'un arbre
😀 On considère ici des arbres non étiquetés.
Feuille basse
Pour les besoins de cet exercice, on définit la notion de feuille basse. Il s'agit d'une feuille qui donne sa hauteur à l'arbre ; une telle feuille n'est pas nécessairement unique.
Exemple A_4
graph TB
N0(( ))
N0 --- N1(( ))
N0 --- N2(( ))
N1 --- N3(( ))
N1 --- N4(( ))
La hauteur de cet arbre est 2, il y a 3 feuilles, dont 2 feuilles basses.
Exercice
Coder une fonction nb_feuilles_basses qui prend un arbre non étiqueté en paramètre et qui renvoie le nombre de feuilles basses de l'arbre.
Indice
On peut coder cette fonction, au choix,
- avec un parcours en largeur,
- ou alors de manière récursive.
Indice - option 1
On peut utiliser un parcours en largeur qui compte le nombre de feuille par niveau
🥼 Indice - option 2
On peut aussi résoudre ce problème par programmation dynamique. (Cela utilisera bien plus de mémoire.)
On pensera à créer une fonction auxiliaire récursive hauteur_nb_feuilles_basses qui renvoie un tuple (hauteur, nb_feuilles_basses) pour un arbre donné.
On pourra alors écrire
🐍 Script Pythondef nb_feuilles_basses(arbre):
"""Pour l'arbre donné, renvoie
le nombre de feuilles basses
"""
h, nb_fb = hauteur_nb_feuilles_basses(arbre)
return nb_fb
.128013x/.Tr;nbylaeu)dV63Am(P+02è-U,59fq!78 N_o=pcwgv4F1kRéhtsSàLCji:E050p0m0$0l0-0k0%0L0R0k0l0%0%0P010$0-0Q010406050%0n0u0u0l0f0j040(0O0k0n130O0h0L020l0u0Q0g0L0Z0m1d0f0H0n0m0%050c1a1c1e1g180Q04051L1E1O0c1L180p0-0U0{0}0 110#0-0T0#0k1$0#0$16050?0i0k0m1X0~10011#1%1)1%0$1/1;1-0$0f1M0$0#1?1Z010G0^0m0h1r0m010{1j0%0Q0l0h110z1-2j2l271^2a1;2d0u2f040a0L0w0f0O0Q0O0%0-1m1o0;2h0f0f0m0R2J1E2q0h1M0c252V2224231.0p2s111)0h2c2G1-1U1W0|1@2)0-2+0h0O2/1-0Q2O1M2T2V30192k1o2;282_0f1d0k160L0X2S3417332r361^383a3c0z3f2l3h2T2(013m0l3b040L0s3q2U183t3k113w3y0L0V3C3s343u3I3c0E3M3E3O3G3v0O393x3c0r3T3i351Y3l3Y3n3z0J3%3F3*3H3,3!3z0K3:3V3=3X3Z3J0F3{3j3}3Q040X0y423)2=3~3-0X3e1F3g3U434b450X3p4g3r4i4a373@3y0X3B4o3D3(3P4t160X3L4x3N4j4s3 4C3S4F4q4A4J463$4M4z3W4l3/4S3;4k4B463`4X3|4Z4P0X414%4H3+4P0z484-4r4/3-0z4f304N4U4!0z4n4|4T444 4w524Y4I4_4E574(593^0z4L5c4.3?4:4R5i4@5k4_4W5n4O4_4$5s4~4:4,321R2~1E2/2Y0p242%3W0R2`2y0:1V1M2}0m2 3g3M055K0;5S5j010Y160;0G5U581^0S3c5)5d3l0G160h0i0N0G0m0n0^1;0%0N0i1@1C5.5Z15040v635o3v161e0i2O683u650o0.493u5,3z0L6o6f3W0%0p16016v0w0O0n0f0L0k006c2O0L0p1n0h0!0D0L2O0h0U0O0-0m6k6r6t6n6o6X6B1=2_0u6d1=2L5_5{0k5}0L600 624?3u6s3c6X6v013T066Y534b0R0X16030L0+0=0$1=0G1n2Q0-1n0L1C0$6G0!2a0h6R0L0)6B002@0$0!0f6R6z6G1=6C0l1l6e4M6~5*115#045%6q3}6m0L7K4k5;040#7A786z0N5?5^5`5|1C5 611D4F6 2865677)7F6a046E6S7.5/116h6j6=3W7M6Y6X7O286@046`6x7w7z0f6%6G6I6K6M2c6P7m0v2L1d7l0A6F0f0!0R6z2H0U0m0o0L0n1o0$0n0Q1;0L7{5w3}837 8I0L0B6B0l0L7S1l5`6A2L886%6T8G6V8J7 8L8C6#8a6)7Z6,1C6.7%8W4b8H8J6`3T8Z7*3l162c0G2l0$7(307N7/0O160P3M927^7:7=8@8J8_7G160-5(4F985Z5?162v811^7,9p3H8{0h8}0h8 9s016h979e0194040P969j9D0u0-164=327/658E4h8Z7E990h160#9z650D9C7/9X047X0G0i9%999F9I919K9M049O5T9Q169$9J7/9L4C9c9U9k697H2O8z0f0h9.64167-9P9W9Y9!9|ab699)9+9-7@ac040oa27 9D7H0m0_7?afaq9S4pa36p9(9Y0N1d0bai049}9=aG9*5@9,0N0#aI0laK9~9/95ak3ua09^aLaN3ga4a$9@9_aDaEav167a0fa#4U160%6y5~9baY5Z0O6m2@a_449u9w9yap699RataEa,a`7Ra)b54k5=aRaoaOaZ9Gbj379Y7T8R7WaR8*5}7$6:909`999rba3Pa{a}0Na aAbb16as7Dbe807/7H9hbr8`bhb0699F020T0$0gbW9t7RaVaXbM6g16aC3DbR9daPaUaJb*9Ea!bZbHbY4|b@8I9DambmaTb-b|9:b|c65^bna+aF9971730L9L0%1=7o0,6ya^bQb@a=04axbVb bg9Zcz3}9:9;a+c5aHb{bG3Wbcctc3ch9lblcec8cJbob1160xcF3rbfb6aQce97c#707204747A0T2x9x0l2J0L0Ibdb^99a60=6zaacC4bbFb/3Wa%4{cG93cXcccIaWbid1bsc%aSb`ddcK3}9B4M6}bScic,741w0$cr7n8M0L7a0h7c7e2}2@0R143xaz9TdqcQc1bDaqa*c!cHdhcfdRd9bqdfbX8P7U0fbw7Y6+bz6/cnbC3r9Dd3dOal6b897Cd4dmbOatcva7c dbdT3%0c5W5R1P5C0c5E1E0$5Gea2#2W0l1:e5e85O1K5Y692O0u5^0l0Y0maT0s161w1y1A8,b=2V1S5N2:3}0l0p0u1n2I7d2K2l0T0m0f161K3ueHeJ7l2J0B130$20040t8t0R8w1o2k0f5K8r7f1o0}0feP6z1P3h1L0+5Le+0L0Q5`7N1x7R0l0R0Y0j1Ef4f0dw2@1Uez6A6-0R7S0hePc;8 7x0L7l8t7A0b0de`el0C2+0L7T6F0u0!25e~8B0n0`05f40|0m2lfa0u3zcn0f8N2}2E2G0!6(2l0`6C0m0beQdG0R8,19221n0T040*1ee^0f0`0p008xfAd@azf.fl04fv1R3h2/3u1`1(1*1,em3u2u2c2e162A0(0R7u0Q7h0w0jfFd0325Qem315Te4gc3W0Y9)0G2D0u9z7M9z0h9)5K8+dC0hd-2U9DgGdl4bgA9g1s3Y0$e00;ez6|cv3kgF5-gS370R160W2baLeBdpcP690%2o840+3*1=g/8C0le)e+6(0mez7f0G2a0Rf6h42Bgp0#1n0Bb$b(gK1;gM0%6{cNcv7Jg+5+g*d_4b0G0u160N0N2@2IhAaLaed;3u0i65cn0k9ihv7+bOg=8^7/hJa{axhNhH3W9Fg3hObX0pc?0lcab~cVd=7Ih51BhFbP4|g?c*287Hhrh$11gRh}3v7Q7g0N0U0-0;hF9zhU04hLhXd.9{arhRc{5Zc}a8grd899iaic9zh!gH5$h)h+9GcZ2Uh_h%h:dJiebEadh?4hh^hq0midgP7/h hY44i29vg:hs7_adi9hKhWdeh-c0b.iQd2hQc`g@hIiZhMir16h#i)dgh(0?i;g2it7;0Qf10h0pi8iV7:i(iEaqiH4piJbT5$iLg)3zgH7Q5%iUi0d:j769ipi!j47`i,iA9f04cyi$3Wjpi:j4isj49)i3i5i7jriGiha3d}0@cncc2y0q3x1B0/2N3Yj3i0g_6ug 1=jH2faLj9b?iia516d~a9b|jAiMgycDi=i}i_h*jCj`jE162F8BiLgYjJ66j+174}3}h{jej4iPjn3P7Q9+by7#d+6;jliXk07;f~j*jLju7:9+bAd,iwiyjg9 a.d|aP0UfIkAe0j$h=kFag04kHgOj^4bjDi0jFiT1;jYi@bXbLk!iWarkNdMkQi{i?kgbg8|jkk%9Akpi00Yg-040M1niDiNiFk)9jkvcjc-0L7efe0-h6f|fjeO1x2c7h2LfrfN0nk*j.040S1#kYdY7Gk{0e0fh;k6ku9VdM2_5`j2lsb}dXjyc$k,j~i|kqjjlrkok7jtcvjxinlB0OlDcab3kRkvk`16k}2+g;c)9Dl574ldfllf9xfplj7A7i782Q0!jtlAlnlUdVkOlKi0kUk?jF0%0$i4i6k kShPk7eBi-5Jdsl71o8N7k0-l~j-3uikd lFcd0GkykndKjMjccwayl+cNbedSkxkml#9DcblFa%a/izl4mk7e8ohC133x0-cn6Z2h1sd#mqc4kGkIlLk.l0dMk;lPk?jmm/a5k{l)mdd/d{l3l-mT1ol9lb35fkfmlgl@1VlklSmCaxjPlym)kvmwmymLdWcYb|d6nhdS8|8~nlbpkBni5=lX0nlEc2a;mCa@e0a|fIbKkslFb29gimm2m:9vntmFnCcum+kRmMj kVb7k=k/d`66i}nHa~nKlQk8jbc|j/c~j;mv9nmZ78e2gxe6ei5E18ej0U3he80=0@0_04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)