Aller au contenu

Filiation de la feuille en bas à gauche

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

Hauteur d'un arbre

La hauteur est le plus grand nombre d'arêtes d'un chemin allant de la racine jusqu'à une feuille (le cas de base pour les arbres enracinés).

⚠ Mais le chemin n'est pas unique, il peut y avoir différentes feuilles à la profondeur maximale.

Feuille en-bas-à-gauche

Pour un arbre ordonné, cadre de notre exercice, il y a une unique feuille à la profondeur maximale, le plus à gauche possible, qu'on appellera feuille en-bas-à-gauche.

Filiation de la feuille en-bas-à-gauche d'un arbre

graph TB
    N0( )
    N0 --> N1( )
    N0 --> |1|N2( )
    N0 --> N3( )
    N1 --> N4( )
    N2 --> |0|N5( )
    N2 --> N6( )
    N3 --> N7( )
    N3 --> N10( )
    N5 --> |0|N8[/ \]
    N7 --> N9( )

Pour l'arbre dessiné ci-dessus, la feuille en-bas-à-gauche est dans le trapèze, avec la notation Neveu, sa filiation est [0, 0, 1] qu'on assimile à une pile.

  • Partant de la racine, on va dans le sous-arbre d'indice 1,
  • puis dans le sous-arbre d'indice 0,
  • puis dans le sous-arbre d'indice 0,
  • on est arrivé à la feuille en-bas-à-gauche !

Exercice

Coder une fonction filiation_bas_gauche qui prend un arbre non étiqueté en paramètre et qui renvoie la filiation avec la notation Neveu de la feuille en-bas-à-gauche.

###(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 : ∞/∞
.128013]x,59/f.78r;nb _o=ylaepcwgu)vd4613kRmhtsP(S0à+2[-i:050E0w0N0v0Y0u0O0p0y0u0v0O0O0s010N0Y0x010406050O0B0L0L0v0l0t040R0r0u0B0@0r0n050g0~1012140|0x04051k1d1n0g1k0|0E0Y0D0,0.0:0=0M0Y0A0M0u1B0M0N0`050%0o0u0w1w0/0;011A1C1E1C0N1K1M1I0N0l1l0N0M1O1y010h0)0w0n0v0L0w010,170O0x0v0n0=0V1I1_1{1)1Q1,1M1/1;0`0a0p0P0l0r0x0r0O0Y1a0n0p0#1@0l0l0w0y2i1d200n1l0g1%2v1!1$1#1J0E220=1E0n1.2f1I1t1v0-1P2F0Y2H0n0r2L1I0x2o1l2t2v2Z0}1`2j2N1*2S0l110u0`0p0H2s2%0{2$212)1Q2+2-2/0V2=1{2@2t2E012|0v2.040p0I302u0|332`0=36380p0F3c322%343i2/0e3m3e3o3g350r2,372/0G3t2^2(1x2{3y2}390j3D3f3G3h3I3A390k3M3v3O3x3z3j0f3U2_3W3q040H0S3#3F2O3X3J0H2;1e2?3u3$3.3(0H2 3?313^3-2*3Q380H3b3~3d3E3p430`0H3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4s3N3`4b3)3T4x3V4z4p0H3!4D4h3H4p0V3+4J414L3J0V3=2Z4n4u4A0V3}4V4t3%4Y464#4y4i4S4e2#1q2X1d2L2y0E1$2D3w0y2T1=1l4?1m4;4/2#4|0#2Y4E1*0J0`0#0h3m4$3.0z2/5e4+2{0h0`240Y0v2i0q0o0/0q0A0v0B0y0M0w5j581Q0_040Q5C4K3h0`120o2o5I4Q0=5F0C0Z3t0p5W0p5f1*0O1~04010K1.0D0r0Y1N0.0p5o5q0Y1b2k5.0v5:0w0B0)1M0p1.0X5t0O0X0T0X5w5y5A013t065X5Y5k0=0y0H0`035:1b2q5?2j2Q0N0w0l2H0p5x0c0)5p0Y5O4m6e5Z1Q5a045c5P345h396K4u5m045;5r635v5x5z0w0q6x6O3W5F5H4f6F5K045M6C2#6g015S5U6D6e5X6*015#0`5(5*5,5_0p0M5x6s0B0l600N0p5/6S6p5^7a5`0h5|5~1N616365676W6a5V6^5W6`0n0`1.0h1{0N0O3m6f5D0=0r0`0s7C7u5L0l5N5B6@7s7K040n0o0q7x7z7B4f7D5J017G047I7Z7u0o0`256#3.6%7/2*7w0n7y0n7A7=5E0`0C7r7Q6:6H0Y5d7*6:7v7S7U7W7`7Y2Z7!5Q7$7H7)8e6`0L0Y0`4O6/7E6;0`6?4V7s818r6H2o0N761c868r7;6)6:8m8o7|5R0`0d7J6:5F0W0b7 7P6^7R0M0q110c8P8r7%8j2?8f347%0X8L018J3)808W825n3y8$7#880Y8{8g0r6M2Q8 3p7,040l1{0A7O8q7#8G9c8g887T7V7^7X8/6=8?8w8+4u0`0O0r0B0O6Z7M6.8*6`8(949r048b7{8H8F0`0W8/8}9m0`0b9o8w8X9O048O8E8|5n5s0A9D3W9C9X9g5n6z5=1b5s5u686X6Z0B8#9I9d0`6(9f3p9s9u9w6-9b2?6`5S9R8x7#83858k870`0M9$3.7%020A0N0mag7?048Y8!9U8u3@9p9p8X8Z0v9^ac8%7Han2{aea7av7R0YayaA9A6:9(aB9Y048~8Vav6_ad6R9,2r9)8,aDa#9E0h9!aH7R7c1b8/7%0i9M5L0x0x1.0E9U9|a4aXaKar9_8ga6aUaW8y0`8A8CaE8M5G8/8;4UaNaC040Ubb35aeaL9U9WaQ9*aY1E9-8D9}3wb44V6db67#6i6k0p8A9u770T7f6m0n6o5@0w0c6s6ua33 6EaXafb2345FbqbhaRa*0o9#a(9%a%br9~bt5p6T9:7p6Y6!bZby9{a?6,9ybU2ua57~8?6`8z0$bab,3`9Zb*3D0g550w2v2Wch4=1u4@2y2B2w0v1Lck0g4?0|cu0$0(0*04.