Aller au contenu

Maximum des valeurs d'un arbre étiqueté

Le cadre : 🏷️ les arbres d'arité étiquetés

Une modélisation Python est de donner une liste à 2 éléments :

  • le premier élément est l'étiquette du nœud racine,
  • le second élément est la liste, éventuellement vide, des enfants qui sont des sous-arbres.

Cette structure est donc de nature récursive.

Il n'y a pas d'arbre vide !

On pourra ainsi dépaqueter un arbre et parcourir chaque sous_arbre :

🐍 Script Python
racine, enfants = arbre
...
for sous_arbre in enfants:
    ...

Exemple : Un arbre à six nœuds

graph TB
    A(6)
    B(5)
    C(4)
    D(2)
    E(3)
    F(1)
    A --- B
    A --- C
    A --- D
    B --- E
    B --- F
🐍 Script Python
T = [6, [
        [5, [
            [3, []],
            [1, []],
        ]],
        [4, []],
        [2, []],
    ]]

T est constitué d'une liste à deux éléments :

  • l'étiquette 6,
  • la liste de ses enfants, il y en a 3 :
    • un nœud qui porte 5 et une liste de 2 enfants :
      • un nœud qui porte 3 et une liste vide
      • un nœud qui porte 1 et une liste vide
    • un nœud qui porte 4 et une liste vide
    • un nœud qui porte 2 et une liste vide

**Le maximum des valeurs de l'arbre est \(6\).

Exercice

Coder une fonction maximum qui renvoie le maximum des valeurs d'un arbre passé en paramètre.

👍 On supposera que toutes les étiquettes sont du même type et comparables.

###(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.9888.128013x/.Tr;nbOylaeêu)*dM63Hm(P02è-WU@],59fq78 _o=pcwgv41kRéhtsSàCj[i:E050u0p0*0o0;0n0+0R0W0n0o0+0+0U010*0;0V010406050+0r0z0z0o0h0m040,0T0n0r170T0j0R020o0z0V0i0R0%0p1h0h0O0r0p0+050e1e1g1i1k1c0V04051P1I1S0e1P1c0u0;0Z0 1113150)0;0Y0)0n1*0)0*1a050`0k0n0p1#1214011)1+1-1+0*1?1^1;0*0h1Q0*0)1`1%010N0|0p0j1v0p010 1n0+0V0o0j150D1;2n2p2b1|2e1^2h0z2j040c0R0B0h0T0V0T0+0;1q1s0^2l0h0h0p0W2N1I2u0j1Q0e292Z2628271=0u2w151-0j2g2K1;1Y1!101{2-0;2/0j0T2?1;0V2S1Q2X2Z341d2o1s2^2c2}0h1h0n1a0#2W381b372v3a1|3c3e1a0D3i2p3k2X2,013p0o3f040x3t2Y1c3w3n153z3B0!3E3v383x3K1a0L3N3G3P3I3y0T3d3A1a0w3U3l391$3o3Z3q040P3(3H3+3J3-3#040Q3;3W3?3Y3!3B0M3N1T321I2?2$0u282+3X0W2~2C0@1Z1Q310p333j434d0^4l3m3~0$1a0^0N433=2_010X1a0R4x3}4z0j0N1a1h0d0;0z1f4E4r4z19040A4P3*4G1a1i0k2S4V3x4S0s0=3U0R4,4D4y2c0+2s04011A0j0Z0T0;1_110R0Z3A0p0r0h0R4K4M510R0u000r1s0j0a0r2+2P0n004Z2S014+4-3)3Q1a0h0o0W2{0p4$3X4S0K3N4.4F3b1a2g0N2p0*1H1J3j5D4Q2c0T1a0U5C5q3X0j4Y0h4!5x5M3u064-5O4W5F04501^530S4K5U4/1|5R045T5$2Y5*5r045t5v2/5o4,5V4s1a0N3Z5?5E3o1a0+0T0r0+0S5l5#345~3X0T4B042{6b5P6d045H5J5L365@154S4*5|1b5)5)664X5-6t5+5^5S6M5 564N0z5y3~4S4U6F6J5,6f6h6j5Z4#6Z6B014(646H6!1|4t6r4w6F6n3~5X5-515:5=6_6;155_020n0*0i6Q5W1a0Z6V4R1a6E345(6H7j723y7b6~0h5;0o0d793~5_5{6m7l6|7c6F7i656,6?2S0*530j7t6K5.527p707h1I4o4k447T0e471I0*497Y2)2!0o1@7V471O4q6N152S0z0S5I0$0p0S0)0x1a1A1C1E1G0R7g4m1V3k0^0`0|0~3X0u2p0Y0p0h1a3G1f1C1k0,0*0m1^0R690j2U0;1r2/0n0R0p0d260q2B2W8i1M3k1S4M0Y0R3A0*150b2k3X0*0X1B0T0/0;2k0+0h0W1(220V0+0=0e0e0W0u0j0f0/0+0^1-0Z0h0f2/0*0e1+0e0/0^0W7@0u2!8S0z8U0;0I0#0L0f0#0f0C0e1{0_0+1J0Z0Y0e0D0w0o0C0f0+9l2k170*1^150=0X1i0j2{0Y0=010e042F6g541^0~8y0V8e5K0f0R0H1s0+8m8o8q8s8u0p8w0p0N2e0W5u1_1G0*590(1-9,9:0-0R266g0Z8e0K550{0~2J130;7)0f1T851Z3x1~1,1.1:7-3x2y2g2i1a2E0,0W0h189:0B0m291r434j7-354m7Sag3X6?4v7d2c6q4D6+6c3J4I046S4OaK6u6C1a6Y6AaL7m046kaG1|4(825%6I6,4;1a4@2g4`4|0R4~7M53a04L3e1_5a5c0R5e5g594}5k6)2j6/7y5s5u5wa#aT045B716,6|6x0j5K7K5Q6PbgaX6|a!7Ba*aX7F0_7Ibm3o0k4J7rbc6-aUbE6|61bbaR7.bFbebz3JbBaObDbL4%bGbU5WbR1h0VbE6XbHbCa`aQaWaSbNbf7xbh5G4H6yb$1a0sb/5Nb8044v0o0r76bE7vb(60ba63bX6Wb_0s3(8+4e2Zax464h7,0.0_0*1_6f1o2Na 1_ao0(1_2o0~5i0;9X1_2{cn3d0(1Y0{2S8x9:0(0Z2M4}cw0;0E8d590ra_4M1f0R1e54a~2M0(5tcna^cN0^9T0l1s17cJ0o50bk0ocT0ucV2o5t0z0E26cw1i9;5I1p4DaBb c10*7RcfcZ0r1Z5Ja=0o590T0W1f2g0`cr2Pasau1s6E1W4g2@3~ac201/2taXai2A2C020Y77dIdKdJ1y0)9%0V0A4Kcc6Zch366ZaB0ydQ0R1r0R0kdf760F2{8p5c9#1s4K0Rd-96c{8od)0|170j8(06064K0A0fe40s7Ca_0AcO5t7)9 0t0:9 d9760U0T0k0/9 7@0m0U0Nd/0J0s0R0FdL1y5.1Fe7e21i0Y0#9 eD0DedeD0+edef0ReoeqeseuewdN4 3AeAe70G2M2adj2L0j0Y8oea7(8oeDdnbk9 7G7Id?5Kd(1*8d9Xe@1B9T0gdPe7eh9:eo0X3Z0u0F1r0n0m8K0h0Ye/9:2n2T0;2e802vek0/2T9:0*0T0Re=0h1sfke729cw2Hc,0p2+e+7)d?9O1w8m0feYe!9`f6d$5496c=fefgeLfubxfw9`dPdife9/fdff2BbkfMdc4p7U2Z7+dx3x0o0u969Dcr2{698g1Rf^f`1r2M8t0j0F9w24040?0d0V9?0odqcV7Sa81cc13k1-1Q7Sab1.dBaf7ybZbTb,bMb%c94Ggwb#gB2cgAgy6R7rcX6UgFa$1ab{3u6`6KbjblgNbdb`bPaYf3c3bogI7ac6626l4m6,6.6Zce4p811za/4{4}dja@fSgKa{0Rc}0z0;a=80gU0+9T1d9{e(040va12Wha0Y9J0+000|a 00fcdjcx5900h6e;g^a;05aBbJc8aBh0d30u0(d50*a70ego1cgohx4egr1 aedDb-bw7HfwgZ0jgw7sgWbNaVg-bqb9g+b^bObpb-5_e4hIg(ca04dUdXhB0=g@4_g_h4cW6T8xbkcJ4~hz9.9:8oaP0zb29Ob?bk0~0Ahj888x4LcBbk0shIhK1Igm1c7Wcj460_0{0}3k7Wiy8804.