Aller au contenu

😀 Arité d'un arbre

Rappel

En Python, on peut modéliser un arbre ordonné non étiqueté avec la construction suivante :

  • [] pour une feuille : une liste vide indique l'absence d'enfants.
  • sinon, une liste des sous-arbres.

Ce qui peut se voir sur les exemples suivants :

Un arbre à 3 nœuds

L'arbre représenté par [[], []] désigne une racine qui possède deux sous-arbres :

  • le premier est une feuille,
  • le deuxième est une feuille,

Il se dessine ainsi : 

graph TB
    R{ } --> N1{ }
    R    --> N2{ }

Un arbre à 6 nœuds

L'arbre représenté par [[], [], [[], []]] désigne une racine qui possède trois sous-arbres :

  • le premier est une feuille,
  • le deuxième est une feuille,
  • le troisième est un arbre qui a deux sous-arbres qui sont des feuilles.

Il se dessine ainsi : 

graph TB
    R{ } --> N1{ }
    R    --> N2{ }
    R    --> N3{ }
    N3   --> N4{ }
    N3   --> N5{ }

L'arité de cet arbre est 3.

Définition

On rappelle que l'arité d'un arbre est le nombre maximal de sous-arbres que possède un nœud de l'arbre.

Exemple

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

L'arité de cet arbre est 3, il y a un nœud avec 3 sous-arbres ; les autres nœuds n'en n'ont pas plus.

La modélisation de cet arbre est :

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

Exercice

Coder une fonction récursive arité qui renvoie l'arité d'un arbre passé en paramètre.

Indice
  1. Comment obtenir l'arité d'un nœud ?
    • C'est la longueur de la liste de ses enfants !
  2. Comment parcourir tout l'arbre et mettre à jour le maximum ?
    • Pour chaque sous-arbre, faire un appel récursif.
    • Mettre à jour éventuellement le maximum.
Guide
🐍 Script Python
def arité(arbre):
    "Renvoie l'arité de l'arbre"
    enfants = arbre
    a_max = ...             # (1)!
    for sous_arbre in ...:  # (2)!
        a = ...             # (3)!
        if ...:             # (4)!
            a_max = ...     # (5)!
    return ...              # (6)!

# Autres tests
A_3 = [[],[[[],],[],[],]]
assert arité(A_3) == ...    # (7)!
  1. Initialisation avec l'arité du nœud en cours.
  2. On itère sur la liste des enfants.
  3. Faire un appel récursif pour chaque sous-arbre.
  4. Quand faire une mise à jour ?
  5. Faire la mise à jour !
  6. Que voulez-vous renvoyer ?
  7. Pensez à ajouter des tests, comme celui de l'exemple !!!
###(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.128013x/.r;nbOylaeêu)dV63Am(P02è-],59fq78 _o=pcwgv41kRéhtsSàL[i:050r0n0!0m0*0l0#0L0Q0l0m0#0#0O010!0*0P010406050#0p0w0w0m0f0k040$0N0l0p0 0N0h0L020m0w0P0g0L0X0n190f0I0p0n0#050d16181a1c140P04051H1A1K0d1H140r0*0T0@0_0{0}0Z0*0S0Z0l1Y0Z0!12050/0i0l0n1T0`0|011X1Z1#1Z0!1+1-1)0!0f1I0!0Z1/1V010H0;0n0h1n0n010@1f0#0P0m0h0}0A1)2f2h231;261-290w2b040b0L0y0f0N0P0N0#0*1i1k0-2d0f0f0n0Q2F1A2m0h1I0d212R1~201 1*0r2o0}1#0h282C1)1Q1S0^1:2#0*2%0h0N2+1)0P2K1I2P2R2|152g1k2-242=0f190l120V2O30132 2n321;3436120A3a2h3c2P2!013h0m37040u3l2Q143o3f0}3r3t0U3w3n303p3C120F3F3y3H3A3q0N353s120t3M3d311U3g3R3i040J3W3z3Z3B3#3T040K3)3O3+3Q3S3t0G3F1L2`1A2+2U0r202Z3P0Q2?2u0,1R1I2_0n2{3b3{450-4d3e3?0W120-0H3{3*2.010R120L4p3=4r0h0H121a2E0Y4w4j4r11040x4F3Y4y4B0f0i2K4L3p4I0q0+3M0L4Y4v4q240#2k04011s0h0T0N0*1.0l004C0!0Y0L2H4;1a4Q2b4X4Z3X3I12280H2h0!1z1B3b4!4x240N120O3F5b4G334O4}4 4Y513P0h4B0M190c5h5p3?5e045g593m5i4M330i122r4S3P4I4K5C2Q5x4N045456582~4#1;4U5n5E3p4l040H3R5w5X3B120#0N0p0#0M4|4R5O045#3P0N4t042:5+5c3g534z5U5K3?4I4W5_064Z6d5{3?5r040m615j1;5z5B2|6f5R4?4E5_5Q245M675R5/5;5?4P5^5W620}5Z6b6e505,015%0*4o5_6q5k6i5t0m5v6R6v6m12020l0!0g6k5F636i6y6w126a2|6c6K6e6Z5-6U5u6*3p6n6}5q4B5!6_6N122K0!0p0f0h706g5s6|6b1A4g4c3|7j0d3 1A0!417o2X2S0m1,7l3 1G4i6+0}2K0w0M550W0n0M0Z0u121s1u1w1y0L6;4e1N3c2+3p0m0r0w1j2E0*1j4_2h0S0n0f121G7W7Y7!2F0C0 0!1|040s4C561.0m0T2L0L0#0!0k1-0L5)0h2M7$0h2%0l1L7U1R3p1?1!1$1(7z3p2q282a122w0$0Q0f100!2x0k211j3{4b7z2}4e7i8n3P5%4n6.1;5~4v6u6M4z4O4D8N6H125N6F6l6`5@0n8W014U7R3m6?5o6M4%124*284-4/0L862=0w4}0L5u0*364_1.6A0#0C8%0?0r000p1k0h0a0p2Z4`4=6D4~6J6L6G3q8U4@5V5a746 6Y6M4I0)8)6h6s8)6x8R9o6h956C5m9F8#8*120q7c4r5%5)0f9Q6T9I8%9V6m5~609w9G5l6E4e9x120D738S9q0Y9s3m9u120e9A4B0P0P280r9D8Y9A5H045J9L7A9N4J9{6i9ka1040q9P9m8/9o5%77797b9%9M0ha47f8!a89Eau52ac4D9?5P9,af3W0d8I7k2R7x1J040v0p0Q9c1.7+2K790L0h001y8y2_0N4-1w0Y1.1q0w0o2t820*4v8I9YaG465`aY0LaQ8`0*831.0T0*0-0Ea:a@6s588I0L2B0{0B2H0m0p8 4.0h0?9c0L0Y0l0Y2t0h8y1wa/a_058I2r0x8%ahb80%8`0m872:b30.4_1j0Qb44h5uby8w9rbAa@0La_bk900w1782aUa{1#a~4!1~1j0S042=1kb00-2Ob*0hb,9`7T1P0.0:0=3p0r7)7+7-15171u1c0v80bL83851.0P1g0?888a1j8d0L4K1t040Z0m0Q0W0k1Acnah1Cc68g2,3?8j1^1%2l9o8p2s2u8t8v8x8z8Bao2~8E3X8G9@aH6M8L0n6Qax3P8P9A4Aaz4@ae8Z9+9(ac9Kc!689O8,3x6d748;4)4+8^4:1.8|8~bX3s93825:96984_9b9d9f9h4:9j4}019/ak760.an9Z3Bas6Wc+5!c_8Sa4a6c;4Ha2a7aya=dy6/af0Edt9naqdq6XdE5YdA6=6@6^aDc,9@9:c)6tdN8XaadB71049Xadd$c=aEapa89S5*d.ayd)c:9t6M5}129$6p749Bd*dZa90qdHaidR6S6,4nbe6%8)9ve20w0*120zdIaj9M6IdQdJav9OaFaH1N3}7m49147mb|0;0#7UeAb~3Pc0b@c23nc51EaMc9a`1kcb860n0c1~a,1.cm0w040j2%0(2:7+cueZcweL1bcz8i1$cD8m74cH8r2v0L8u8w0P8y0y8A0Z8C6ucR2~6ucVc.9Cd=5|5fdo75a51n0ic0fee0d^dV9o69fkdLdsd+4ydw28fse2fl9*fnem9Oe5d~dv12atc-fCd#fydq0PfxfJa8e08VftdFfEd_f9e1fQ4TfDfk4mcYeb0!edfdfU1;egeiaeagesa@aI3~ex3~eEeCeyaKez0/eB04.