Aller au contenu

Hauteur d'un arbre étiqueté

Le cadre

Cet exercice porte sur 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, (au niveau 0)
  • la liste de ses enfants, il y en a 3 :
    • un nœud qui porte 5 (niveau 1) et une liste de 2 enfants :
      • un nœud qui porte 3 (niveau 2) et une liste vide
      • un nœud qui porte 1 (niveau 2) et une liste vide
    • un nœud qui porte 4 (niveau 1) et une liste vide
    • un nœud qui porte 2 (niveau 1) et une liste vide

La hauteur d'un arbre est le niveau (ou profondeur) maximal d'un nœud.

La taille de T est 2.

Exercice

Coder une fonction hauteur qui renvoie la hauteur d'un arbre passé en paramètre.

###(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 : ∞/∞
.9888.128013x/.Tr;nbOylaeêu)*dV63Hm(P+02è-W@],59fq!78 _o=pcwgv41kRéhtsSàCj[i:050t0o0*0n0;0m0+0R0W0m0n0+0+0U010*0;0V010406050+0q0y0y0n0g0l040,0T0m0q160T0i0R020n0y0V0h0R0%0o1g0g0N0q0o0+050d1d1f1h1j1b0V04051O1H1R0d1O1b0t0;0Z0~1012140)0;0Y0)0m1)0)0*19050_0j0m0o1!1113011(1*1,1*0*1=1@1:0*0g1P0*0)1_1$010M0{0o0i1u0o010~1m0+0V0n0i140D1:2m2o2a1{2d1@2g0y2i040b0R0A0g0T0V0T0+0;1p1r0@2k0g0g0o0W2M1H2t0i1P0d282Y2527261;0t2v141,0i2f2J1:1X1Z0 1`2,0;2.0i0T2=1:0V2R1P2W2Y331c2n1r2@2b2|0g1g0m190R0#2V371a362u391{3b3d3f0D3i2o3k2W2+013p0n3e040R0w3t2X1b3w3n143z3B0R0!3F3v373x3L3f0K3P3H3R3J3y0T3c3A3f0v3W3l381#3o3#3q3C0P3*3I3-3K3/3%3C0Q3?3Y3^3!3$3M0L3~3m403T040#0C453,2^413:0#3h1I3j3X464e480#3s4j3u1S311H2=2#0t272*3Z0W2}2B0?1Y1P300o323j3P054C0@4K4m2b0$190@0M4M3@4e0X3f4X3 4n0M190)0n1o0o0q0g4$4R1{18040z4;4d3a191h0j2R4`3x4@0r0=3W0R570R3+3x0+2r04011z0i0Z0T0;1^100R4+4-4/0R2O0m004~2R0156585a3Z0i190g0n0W2`0o513Z4@0J3P594Y4|042f0M2o0*1G4r2X5O4%2b0T190U5N5A474}0g4 5I5X1a585Z4=144T040;4W5:5?4{3o0j192y5J404@4_5:5*4n195S5U5W355P4?190r5)6g145$040U5(5}692b0y0;194b686l014@555:065=5=6s1{5_2R0*4/0i6k5!1{6u6w5y576H5^6b0|5/6f6P146B6T6F6V3y4*0S1g0c6O5@016n6q335~3x6R046x336E6F6U6z5_0M3#6:5 3K190+0T0q0+0S5v6Z3j6_3Z0T4!5`6N6r6z5C5R0i5T0i5V644e6%6D70706*7q0)763x6?7F5B4*4,0*4.4:6y6#6A19676!6;7q7a7c7e5-507P6;536(7A7i405_5{7I5+040)6-0n6/7o7Q6n020m0*0h7/6a7;7w2b7y6~7*7*7C6,6.805#5%8c3o4*7)5z725D0^6M8f146{4i6^6*6n0B8o6+7;7?7^6~1H4O4J4t8E0d4w1H0*4y8J2(2Z0n1?8G4w1N4Q77012R0y0S5T0$0o0S0)0w191z1B1D1F0R6C351U3k2=3x0n0t0y1q2L0;1q0R164@1N8^8`8|2M0F160*231k0*0l1@0R0q1r0V4.0R740i2T8~0i2.0m1S8?1Y3x1}1+1-1/8U3x2x2f2h192D0,0W0g170*2E0l281q4M4I8U344L8D9B3Z5_4V831{7l597$8V7s7K5p7O7U8V669#78047f9=7R04546(6*5c195f2f5i5k0R5m5o7M5q5s5u7!1^0(168-0*0(5x7z8j7Q7q5E5G2.9_5L8w7q6c7u6e7h8t8e7_7V5,5.9}8k5`5|8s7p6104639)527S9_au7s6dar6i8w6?6@ay6z6{6}4L6z854k88aG6K8naB8Va$aF7Q5_0o6YaV048:a+7A6*6J8m0g7naJ7Q8qaX198va:3SaL8baO5KaQbf7:a77Na{7Ta(am797b7d9^bi7xaWbb9Y19749.a!bp047XbsacaX7l2`at6baTawa{6j6D8C4D2Y9S4v4G1b8HbX0?0^0`0|3x0X1h0i2`0Y193H1e1B1j0u0o0g2K8 0n0Z2S599W1g0VbS4P2Vb;1L9u2?409x1 1.2s7Q9D2z2B9H9J9L9N9Pb44LbV8;359Wb04U0oaIbo6;9%aR4)7;7Lblbu84bh9/3SaD7#cJbg9{a}3u6 717Q9 5e5ga35l0n5ncEa95lab5.0Rae0;agaia?aC04ao5Ha{5Mbx7:av7vc`4e7Hc~5Qbt86al6;7-cx3u7+4naLaNcN65cIcy9*bM7tc}debv9{b86oaZd96*a=cG6ha|8icTd68l6Lb38wdud4dz8Va^a`dv6$19cQ3Ga,a@dBa/b56;b7d11{8uatbd7@bmaRd#c2dL9`bn4s7p9,a8bBd.7QasdX9?c|axd?7%6ibQ8B0dct1U4ubZ0Z3k8Hb$0{0+8?eab(3Z0t2o0Yb^b/1cc61i04b@b_9p0Rb|b~9hc#0W0$c51Keo8T050;0y0Yet7}140a2j3Z0*0X1A0T0/6v0R0+0g0W1%210V0+0=0de20t0i0e0/0+0@1,0Z0g0e2.0*0d1*0d0/0@ey0o0t2ZeP8{eS0H0#0K0e0#0e0C0d1`0^0+1I0Z0Y0d0D0v0n0C0e0+fg2j991@140=b*b3b-0=010d3C0A7b0ga58.0o0c9j0g5V0R0O9t1W9v3Zcb9zce6;cg9F2C0R9I9K0V9M0A9O0)9Q68cq4L68ctaG9!d+cAd+9+cD9-d%f^cL7gd}9:6idO5;d58VcVa15h5jcZc#9-5rc(7fc+af1EahajdGda5Qc?aqd+d^dUdi7rdkd|5Yaz6obL9@bHakdH3xb1dCcodsa#6v49dpbagtbc19bedmcH4^dygndwd-2X89f`d;f|gU8gbEbr7ZaEgrbwgQby04bAgBbFg.cMbC6;7k19bKd_8xd{bPc_gm6Gd/044V4,7}9_6?0F9_dWgm6*7(5}gY140W0#1903eU9d9f9m9o1q9r0Jetb}0W9g1r4+ey0R0h0Fe04kc38GbVe63k1ReFeH3A0*eKeM40eOeQeS2jeVeX1|eZe#e%0We)e+e-a_1Ye;e?e^0)e`e|8#e h!f20;f4f6f8fafc5Vfffhfjflfnfp902Lfs01fub+fxfz3C0k1r2|7M5Ea55u0/7b9M2O2n2R7u0)0E0+8.7LfDgea5c!4C1v0g0(0)2fb`1rfN8=8Tinie2RhB5U0nej5r0q0Riy1u0E251^iy5r0(5T1ob bThb0qhde2bTeU0q1Y5UiI5r0T0W1e2f0_2MiHf(cn8/fO4Fc94efS20fU8VfW2A19020Y7~jojqjp1xiO0m0V0z6.hL4sf-4sf/bT0xa_0V0R8 0ji~7}0F2`9l9hhx1r6.0RjP8{0ti_1^jL0{160ie#06066.0z0ej.0rcS0Rj,2Lb^8P1@hA0s0:hAi^eJ0T0j0/hA8#0l0U0MjR0I0r0R0Fjr1x0Z3A1Ej;j,1h0Y0#hAkl0Dj{kl0+j{j}0Rk5k7k9kbkdjt0Rkg1n0oj*5=0G2L29c!2K0i0Y9fj@5E8Qet0g0Yj57uhAa.b3jVfL0j1)ej0+9Mj@0y0e0R0fiOj;j 9Mk50X3#0t0F1q0m0lkUkW2A7ueU9j5G2diE1rk10/2S9M0*0T0Rk!1r5{j;28i-2G0Z0;0@2*kRj_1^0;0}1Af$0l0ej;kJ2890k`jJfE8{iXklkX5VkZb21rlmiIkV1F9MlLl30*lBhNbUe58S4veeec1Wl)3xehkOek3venb?b^iQ0RfH250p2AeAb=hR04fC5q0W4.0c0R1D0;j=0`25lwj6fFht9e1^hw2M9rhBb~5mmjes4NbTc1l!jd8@fR1-cc9A6*jlcifZckf$cmf*gJg#jCg#jEc4f;cw9_f@g*3KcCbk4/g)dhcKgCg/mT9`9|gEhn01g7cXgaj1mWfEaaggc,c.gla~gF7Jc=5Fc@g:04h6g}guh4h2d0g=7:d3m{m+gHdTn46`gM8rng7jb9d!gSd$n1g!9X47d)mYg0m!m;c^gBn6m%53n3gKbDk@he5%hgd+himZcOjAdPg53xhphrmghv1qjSmll`0gl|0okohChEex0$hIhK3*i{c4e48Rb!i_3k1,1Pc00nd*9Wet0V0V1,8-j1mp8 mr4Pnyn:4J0R0-0~4+o4bF0Fgg5sc!1,k+1^o84Jn6e3n`1bn`m4m7i~i(2GjY2Ln*2L0(5Ed;c_ou05n`0t1q9M8 4I0i2*9f6.eF1emmhD9h1^kE7Ni(1hi/i;9Moeoq040F4in 0+000{0R0i00l0b|mbo(0}0t00c|0e1HoKn`0.op1AcDey1Hpai(b^2Aiw00k17Mb,fE0Ci(iGewgg0+2olxbNlYp50;e8n^8TeqiQ0}oe302JckiX2foA2}0qjSfMmvfQcamyfTns4emC9GmEf#f%f)f+35mL9U4sf:7QnT04hsm2fE9f0ti:0;hAo!eU4.9f1 2.0R0z0Wp2k+pfi%iK30iNiP0;kT0OqfnP3QdAhamQf?4#f^mVc$d=g#a)dgnwm}nbqvdfcP8wnedDh2nMnFg~nmh20id#8AnNqznr7CnunqaRd:cFnC19nEgyh9qxqsd@190:hhnia{kaqY3Cg$nHd+hfq*19njqydnqhj*6*p/p;iGp@p_hAptj(mf2K0Yq1gPhMmPd8q$czqnm%f_oaqWgWf}m#g|q`gVm)n94eqCmJq/aKnoqMrqgZd(nod*rlqPh9rkqNdnq.m+7qq#pWgVq)nLq+n1q-gBq;m%q?rTq^bPnI04p4d+0M0y190S7e0t0tr/nvrfa;rUrlq|4l8Vq 2Er18.0Y1m0M7N0}q3q5k,0monqd9fqf0Oq|g$rJqG8Vn8nk7,621u0jehgB0na{g3m+qFqZ7`qIrt3aqLr@rQ60rEsFsiqqnzqJ4}a{rSm%sysGdM04rWsNqki;i`rZnJq@gNn1shobl#n?e7bY0@0_ebe8s:b%ec.