Aller au contenu

Arbre filiforme

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

Définition de filiforme

Un arbre est dit filiforme si chaque nœud possède au plus un seul sous-arbre.

Exemple

graph TB
    N0{ } --> N1{ }
    N1    --> N2{ }
    N2    --> N3{ }

Cet arbre est filiforme.

La modélisation de cet arbre est :

🐍 Script Python
F_4 = [[[[]]]]

Contre-exemple

graph TB
    R{ } --> N1{ }
    R    --> N3{ }
    N3   --> N4{ }
    N3   --> N5{ }
    N3   --> N6{ }
    N4   --> N7{ }

Cet arbre n'est pas filiforme.

La modélisation de cet arbre est :

🐍 Script Python
A_3 = [
        [],
        [
            [
                [],
            ],
            [],
            [],
        ]
]

Exercice

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

  • True si l'arbre est filiforme,
  • False sinon.
Indice

C'est facile à coder !

Il faut juste renvoyer un booléen en fonction du nombre de sous-arbres de la racine.

  • Il y a deux situations faciles,
  • la dernière se résout de manière récursive !
###(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],59/f.Tq78r;nb _oO=ylaepcwgu)vdV46F13kRmhétsP(S02[i:050G0y0S0x0!0w0T0q0A0w0x0T0T0u010S0!0z010406050T0D0P0P0x0m0v040W0s0w0D0_0s0o0q020x0P0z0n0q0O0y130m0j0D0y0T050f101214160~0z04051B1u1E0f1B0~0G0!0F0.0:0=0@0Q0!0C0Q0w1S0Q0S0|050)0p0w0y1N0;0?011R1T1V1T0S1#1%1Z0S0m1C0S0Q1)1P010g0+0y0o1h0y010.190T0z0x0o0@0Y1Z292b1}1+201%230P25040a0q0U0m0s0z0s0T0!1c1e0%270m0m0y0A2z1u2g0o1C0f1{2L1^1`1_1!0G2i0@1V0o222w1Z1K1M0/1*2V0!2X0o0s2#1Z0z2E1C2J2L2?0 2a1e2%1~2,0m130w0|0q0L2I2`0}2_2h2|1+2~30320Y352b372J2U013c0x31040q0M3g2K0~3j3a0@3m3o0q0I3s3i2`3k3y320d3C3u3E3w3l0s2 3n320J3J382{1O3b3O3d3p0k3T3v3W3x3Y3Q3p0l3$3L3(3N3P3z0e3.393:3G040L0X3^3V2(3;3Z0L341v361F2;1u2#2O0G1`2T3M0A2-2o0$1L1C2:0y2=47463h054h0%4p3_410N0|0%0g3C3U3k0B324D3%410o0g0|1s0S0r2k0!0g3Y0y4I3/410{040V4W4x2}0|140p2E4$401~4Z0E0#3J0q4@0q4E3M0T2e04011m0o0F0s0!1(0i0m1r0q2x0q0w004*2E0q4O0q4R4T2 0y0c0q0K3n0T1(2x2,0o014?4^4`3`4N4L2b0S1t4r2K4_4J1~0s0|0u3C5I4X4(045e4V5G0}4^5P4%1+4z044S5O5z4K0p0|2l4-3k4Z4#5V5)5R220g5D5F2^5J1+4:5(5}0@5L04020C0S0n605Q1+0P0!0|455|6a0@4Z4=5V065X5X5?5!0|2E0S0D0m0o695Z0@0N0A0|5p0,5U2?6m5y61015#0y1V4C5V5Y4.3b5+045-5=6J5:5.3M5v045^5`6Z3:5 6P6p625M5N6,6J6c0|3~6W6h016j5x6n6Q3k5#6s6u6w6;6`6A0|561r6}6 3M6L6E6)4Y0|6k6G6~4@6-010A0L0|035b220V6%0o5E0E0q0u0u337b6o6J6#0T0s0D0T0r5T6x6R6.046:2?7c5A6$5C7x5{476X0|0Z7g1~6?046^6g6y6{0|0b7E6I766r0(737O3F4N0T4P5j4U7(5~0|5;7-7P3l0|7I7K7M0m4+6F7!6`6+6G1u4u4o488m0f4b1u0S4d8r2R2M0x1$8o4b1A4w872E0P4Q0x0N0y0r0Q0M0|1m1o1q1s0q7j4q1I0$0(0*0,3k0G2b0C0y0m0|3u111o16051n040t2X2W8(1u8:2I8,1y371B0H140!5D1(220q0D2X5b1S981q0!960_1V5r5b000R0F3n0D0x2z0q2a2E0=0y7K0y0h1F372#3k1-1U1W1Y8C3k2k22240|2q0W0A0m0`0S2r0v1{1d4D4n8C2@478l9G7d4A0y6O864F4H6_7.4L7}7 0+4S819.876Y9_7|5S8d4,9|3M4:8T3h6H7m6J4|0|4 2252540q795s9d5c5T5g7~5i9?5k2n5n6D9h5t1d5w6l7F6`6#7w5E7{3M637S367U4K4)9 8fa5ay9/0|747T7naFaD3`6T6V9+a284823x5B5_7Ya$7/040E7b7n717_6vaV7h4!a+6#aRaHaT6/a@7)6d7+a+8ia}6J0s4G043Ob083a_ax7l7n9{aZ7Va|3haI5Ka 757.7*6f8g7.b5bmaTb92b0Gbca%6$7~4Qao9^bja^85bu87aA7XaCa16*7$a+7*7,bM5/7:a.bfa78h0|b!8j0f9#8n2L8A4a8X0+0T378pb;0,04.