🧓 Arité d'arbre non ordonné

Rappel

Pour modéliser un arbre non ordonné, on peut donner une liste de parents à des indices de \(0\) à la taille (exclue) de l'arbre, ainsi qu'un dictionnaire associant les étiquettes éventuelles de l'arbre.

Un exemple

On considère un arbre non ordonné, que l'on peut dessiner de plusieurs façons

graph TB
    R3("Ga") --> P1("Bu")
    R3    --> P2("Zo")
    R3    --> P3("Zo")
    P1   --> P4("Meu")
    P1   --> P5("Meu")

    S3("Ga") --> Q2("Zo")
    S3    --> Q1("Bu")
    S3    --> Q3("Zo")
    Q1   --> Q4("Meu")
    Q1   --> Q5("Meu")

    T3("Ga") --> R2("Zo")
    T3    --> R31("Zo")
    T3    --> R1("Bu")
    R1   --> R4("Meu")
    R1   --> R5("Meu")

Une modélisation de cet arbre non ordonné avec une structure plate peut être (parmi plusieurs possibilités) :

graph TB
    R3("0") --> P1("2")
    R3    --> P2("1")
    R3    --> P3("3")
    P1   --> P4("5")
    P1   --> P5("4")

🐍 Script Python

# modélisation

# indices     0  1  2  3  4  5
parents = [None, 0, 0, 0, 2, 2]
assoc = {
    0: "Ga",
    1: "Zo", 2: "Bu", 3: "Zo",
    4: "Meu", 5: "Meu"
}

Ce qui se lit :

• Le parent de 0, n'existe pas, c'est donc la racine, l'étiquette de 0 est "Ga"
• Le parent de 1 est 0, son étiquette est "Zo"
• Le parent de 2 est 0, son étiquette est "Bu"
• Le parent de 3 est 0, son étiquette est "Zo"
• Le parent de 4 est 2, son étiquette est "Meu"
• Le parent de 4 est 2, son étiquette est "Meu"

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.

Arité d'un arbre

Coder une fonction arité qui renvoie l'arité d'un arbre passé en paramètre via sa liste de parents.

Indice

• L'idée principale est de compter le nombre d'occurrences de chaque nombre dans la liste des parents.
• On peut stocker les occurrences provisoires dans un dictionnaire.
• On fait alors un balayage pour augmenter de un à chaque nouvelle occurrence.

La difficulté sera alors de savoir comment bien initialiser les variables.

Guide

🐍 Script Python

def arité(parents):
    "Renvoie l'arité de l'arbre non ordonné modélisé par sa liste de parents"
    arité_noeud = ...  # un dictionnaire
    arité_max = ...
    for parent in parents:
        if parent is not None:
            ...
            # plusieurs lignes
            ...
    return arité_max

###(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

Exécuter le code
(Ctrl+S)Valider
Ctrl+Enter
(Clic droit pour l'historique)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : ∞/∞

.128013x/.âr;nbylaeu)d63Am(P+02è],59fq7}8 N_o={pcwgv41kRIéhtsSC[i:050p0m0#0l0*0k0$0J0Q0k0l0$0$0N010#0*0P010406050$0n0t0t0l0f0j040%0M0k0n0 0M0h0J020l0t0P0g0J0X0m190f0F0n0m0$050c16181a1c140P04051H1A1K0c1H140p0*0T0@0_0{0}0!0*0S0!0k1Y0!0#12050/0i0k0m1T0`0|011X1Z1#1Z0#1+1-1)0#0f1I0#0!1/1V010E0;0m0h1n0m010@1f0$0P0l0h0}0y1)2f2h231;261-290t2b040a0J0v0f0M0P0M0$0*1i1k0-2d0f0f0m0Q2F1A2m0h1I0c212R1~201 1*0p2o0}1#0h282C1)1Q1S0^1:2#0*2%0h0M2+1)0P2K1I2P2R2|152g1k2-242=0f190k120J0V2O30132 2n321;3436380y3b2h3d2P2!013i0l37040J0r3m2Q143p3g0}3s3u0J0U3y3o303q3E380C3I3A3K3C3r0M353t380q3P3e311U3h3U3j3v0G3Z3B3$3D3(3W3v0I3,3R3.3T3V3F0D3@3f3_3M040V0x3~3#2.3`3)0V3a1B3c3Q3 47410V3l4c3n4e46333:3u0V3x4k2Q1L2`1A2+2U0p202Z3S0Q2?2u0,1R1I2_0m2{3c3I054E0-4M4f240W120-0E4O3-470R384Z3^4g0E121a2E0Z4(4T1;11040u4:4n3h122g2K0h0#1z4t4S4`0}4?0o0+3P0J5a0J3!3q0$2k04011s0h0T0M0*1.0k004-0#0Z0J2H5p1a0i2K0J2=1k3U0p1j0h5t0t2?0Z1#0$5t4}0J0$0l0J5L0#1.2H4}285001595b5d3S0h4,0f4.0L2=0m0n0p3I5c4!240M120N5=5%400i4W0*2M4_3q4?0u0o5#5a5}4g5*5,190b5|5@1;5_045{525?4)240t0*124452065b6n4;0}4V040E3U6g6o4{045X4 6E6y010M4$042:6K543r4|1a5Y512~6h5512586u6w6w6a4U120*4Y6m6*6G6I0#6R3q6N6,6X3c6x6S6_042=6?6/6Z010W0Q120K1j0m633S4?6$2|6v6(7i6:6z6,6.2|6}3L6U4~727o7k6M6O716@3S6 6Q736F3D6c5s5-0M5/5;527v7e687i7Q7v5)045r0Z7I7K7c3_4?0)7Z6b6H6V6J7M744?0A7z3_6j6l7u746q124b7g7Q6(7v6A0m0=7b7,7E017O6%7}7R747T7V7X5:7%247#8g6;7*7t4N7-127/7D6L6j0w7?6|7v7_427P7}7 7m7:7(8d6e8E5^12020k0#0g8I6G8d5.8f846L8i8U6S7T6=8j6!040A7f4d898a858c5+7H8H8r6~5`8P7F7U8/7W8S7L6Y858W8 6L8Z8l8#868p7P8C042K0#0n0f0h8^6T8`6d0l6f6u1A4Q4L4v9q0c4y1A0#4A9v2X2S0l1,9s4y1G533q2K0t0L0E0l0W0m0L0!0r121s1u1w1y0J8)3n1L3d1H0Y0Q0*0B0J1j0J0P5/0#2d0h0$0/5U0f0J1w000;0J1y9:0P1g0?2D1o1-5u9|0h2E0*3t0*0$0m9_4Ea50z5U2t4 5S5V612F290*5z0l0T2h9:2Hahal0Qaf0d9!1P1R3q1?1!1$1(9G3S2q282a122w0%0Q5+0P9:0v0j211j4O4K532}4N9paM3_6A4X966O5c8X3L4+9j5s966596947s6{9Z8o045799745f125i285l5n5S5q8{5u5obe5y1.5B9+0f5E0h5G0J5I0p5Kad5N1a5P5R5T5V1.6=0$5!88698b7G8|7J8T7@857=9h4?0Oa}6,a{6#9h8y6tbN6L6A6C0f9h7T0*9h7B9g8=3L5 9b2h0S83926Sa|a?5(b;2rbV4@bT7)a c00o0o0Hb58-bJ0L8;b!8?6kbX6r04bZ8*5$74b$6Db/5(7r5Yb,6O7Cce7qc36Wc09Y3z8Bcn8Dcq40cs7+cx7Acvb02Q7pcM127ycH4776787acB8A8,93cb8}c07$b|cIczcK8n9098cU8J048uch7`c!7jcF6P7n8wbIa_7Wcdd0bO8K8M8Oc=8Q8{8e8~c/8V12c*b_cy8!c+477.cC138+c|cad2cc9lb,8@da8_8RbLdeb1c:04didf8YcJ8mdEdg8%c9b#129c9eb.cLc,8Gdw9n0ca+9r2R9E1J040s0T2L0J0n1k9?0ja6d/9-5/9-a20J6C0h2M0*5F819*9,5R6$1O4H2,3_aI1^1%2l85aO2s2uaSaU10aXaZ0!a#7Ma%3!a)9Zd#c}a/dm24a;a}a^7Vc04^ey8kc4eG8$b4bGcQ3_b75h5jbbbh7Vbgbd5x5zbl5D5F5H5J5Lbw9_5Q5Sad5UeVbDbF7|cmdtdB7Ydz6MdydVdn12bSeJ9ib+f187e}6pcick3neNcV12b%b)bUe`b-b)b;0fb?b^dI6412eFdjb}12b f4fqc2bDc5c7dP6Scob(e`a~ctfhcvdUd5c$c-50cZeM6)c}6-fffOcu6`fX700MdLcP7 7704792%fQe=8+7Sc%dCc)fy95fwdOfh12c^e`8y7{clbH856AdS9ffj12d4dMb`fxf18.5,c(f16jaDgd12av1g1yeEc63Zd!4F2Rer9t4I9F0Y0k9~0be-5V5q0;1-9e0?0p2h0?a6bs0na64Pgt0(1f1-d 1j51a+d.2%0Jav5+awbB5uape0bp0:5z0#0M1h5V0Z2D0S5GbCg=ag0.e.0#0e0Q0!1.0+5c5R0!2K0E1W1`0P0$0+0c9t0M0Q0$0d0Pen1j0d3U0S0c0E0f0c0r0c1#5y1Egs0kgV2Fhl1%0t0k034EhD2LhF0dgTd/9^1)a+hQ4 af9ogt1A0lgu3d2+aH1$ecaL7vegaQ2v0JaTaVema!fL9Zer2~7Mevg37Thu0M0ta:4%gd7ThLhEg-cOa,4#i5fsa-b*1o3Uf$3vf:04hV9^3P4m3qa.0mc ga3qeAgdeC8{eEf@eIife~b3dp7hg26LePb95k5meTbf5vbieY9,e!bpe$bte(9-bxe+bAe/8lbEfCiscGf6eHcAf{6k8vfa7Ndh96cWf*cYf_8(c{fb6+9b0.dTc_cji,3S8082f-g17~c}g5h_f%8bb;g94ub2frfocring=hWfFiF8hgcjwi:4 ibi_b396gic2gm1xjCjogqdZd#1N4wgw0T3d9t0.0:0=04.