Greffe d'arbre non ordonné

🧓 Cet exercice utilise une modélisation d'arbre non ordonné, avec la liste des parents.

Greffe d'un arbre

On souhaite greffer un arbre non ordonné à un autre à un emplacement donné et obtenir le même type de représentation : une liste de parents ainsi qu'un dictionnaire d'association.

Exemple

Le porteur

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

    S3("0") --> Q1("2")
    S3    --> Q2("1")
    S3    --> Q3("3")
    Q1   --> Q4("5")
    Q1   --> Q5("4")

🐍 Script Python

# Indices             0  1  2  3  4  5
porteur_parents = [None, 0, 0, 0, 2, 2]
porteur_assoc = {0: "Ga", 1: "Zo", 2: "Bu", 3: "Zo", 4: "Meu", 5: "Meu"}

Le greffon

graph TB
    Un("Un")
    Un --> Deux("Deux")
    Un --> Zéro("Zéro")

    ZUn("1")
    ZUn --> ZDeux("2")
    ZUn --> ZZéro("0")

🐍 Script Python

# Indices          0    1   2
greffon_parents = [1, None, 1]
greffon_assoc = {0: "Zéro", 1: "Un", 2: "Deux"}

La greffe à l'indice 2 du porteur

On réalise ici la greffe du greffon sur le porteur à l'indice 2 du poteur (donc en Bu).

graph TB
    R3("Ga") --> P1("Bu")
    R3    --> P2("Zo")
    R3    --> P3("Zo")
    P1   --> P4("Meu")
    P1   --> P5("Meu")
    P1 --> Un("Un")
    Un --> Deux("Deux")
    Un --> Zéro("Zéro")

Voici une modélisation possible :

🐍 Script Python

# Indices     0  1  2  3  4  5  6  7  8
parents = [None, 0, 0, 0, 2, 2, 7, 2, 7]
assoc = {0: "Ga", 1: "Zo", 2: "Bu", 3: "Zo", 4: "Meu", 5: "Meu", 6: "Zéro", 7: "Un", 8: "Deux"}

graph TB
    R3("0") --> P1("2")
    R3    --> P2("1")
    R3    --> P3("3")
    P1   --> P4("5")
    P1   --> P5("4")
    P1 --> Un("7")
    Un --> Deux("8")
    Un --> Zéro("6")

Un procédé

Pour réussir cette greffe, voici un procédé possible.

1. On crée un tableau parents dont la taille est la somme des tailles du porteur et du greffon.
   • On recopie le tableau du porteur, sans changement.
   • On ajoute le tableau du greffon avec deux modifications :
     • Le None est remplacé par l'indice de son ancêtre dans la nouvelle construction.
     • Tous les autres indices sont augmentés d'une même valeur à déterminer.
2. On crée un nouveau dictionnaire en accord avec la greffe.

Exercice

Coder une fonction greffe qui prend en paramètres

• porteur_parents et porteur_assoc qui définissent un arbre étiqueté non ordonné. (Taille \(n\))
• i_greffe un entier positif et inférieur à \(n\).
• greffon_parents et greffon_assoc qui définissent un arbre étiqueté non ordonné. (Taille \(m\))

Et qui renvoie le résultat de la greffe suivant le procédé décrit ci-dessus : un tuple à deux éléments composé

• d'une liste des parents, de taille \(n+m\)
• d'un dictionnaire dont les clés sont les entiers positifs inférieurs à \(n+m\).

###(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 : ∞/∞

.128013],59/f.78rnb N_o=ylaepcwgu)vd4613kRméhtsP(S0+2[i:050D0v0N0u0W0t0O0n0x0t0u0O0O0r010N0W0w010406050O0A0K0K0u0k0s040R0q0t0A0=0q0l050f0|0~10120`0w04051i1b1l0f1i0`0D0W0C0*0,0.0:0M0W0z0M0t1z0M0N0^050#0m0t0v1u0-0/011y1A1C1A0N1I1K1G0N0k1j0N0M1M1w010g0%0v0l0u0K0v010*150O0w0u0l0:0U1G1@1_1%1O1*1K1-1/0^0a0n0P0k0q0w0q0O0W180l0n0Z1=0k0k0v0x2g1b1~0l1j0f1#2t1Y1!1Z1H0D200:1C0l1,2d1G1r1t0+1N2D0W2F0l0q2J1G0w2m1j2r2t2X0{1^2h2L1(2Q0k0 0t0^0n0G2q2#0_2!1 2%1O2)2+2-0U2:1_2=2r2C012`0u2,040n0H2~2s0`312^0:34360n0E3a302#323g2-0d3k3c3m3e330q2*352-0F3r2?2$1v2_3w2{370i3B3d3E3f3G3y370j3K3t3M3v3x3h0e3S2@3U3o040G0S3Z3D2M3V3H0G2/1c2;3s3!3,3$0G2}3;2 3?3+2(3O360G393|2s1m2V1b2J2w0D1!2B3u0x2R1:1j4a1k482Z451j4g0Z2W3T3,0I0^0Z0g3k3C320y2-4z3L3^0g0^0z2m0g0g0v4E4t1(0@040Q4O3@2(0^2c0k0N0v0A0k0p1^2m0l0N0O4U3 1O4R0c3k0n4A3u0l4X3w4!4$0p1N0q0x4.324;4?4^3#0^0W0p4J0v4L4N4o573,554o4@4F4W045c4L194(101,4,533u5j2X5l4P2_4I4K0g5r50525g5m4:0^0B0X3r0n5Q5A4V1O0O1|04010J1,0C0q0W1L1K0n0k0L0|0t0#0N2i5(0u0n5p4M0n0X0n0A2h0N0A0w5)0Q4)5u0O0c0n5H0B015P5R5h5n644+4-5k6e1O0q0^0r565K3f4{4Z4#4%6g5v5J5B0:6m040h5w58044g0w0s6E5i0^0Q0B6c5Q6k6r041a6j6q016B6o6V6z330m0^236K4Q6M6*5C046w6i2Z6W4R6O4o065R5S4/0:4v045F0k6p6#4`040W735T6A4C766U5z6R335D5d5F0l5s4*6x6=6#4R5O6_6{6{7f6 0W4y6!797g76786}6X7b0W6;2;6|320I0x0^0o195f7o7A7q6P7t7u6W756:6-6A0^6D6y7A750u0w0w1,0D7#014R4T7)7E755a5^7R2;7f6@7V7X6#6 0v0(7}2 7 0^7r2X6`7W7t7f7Z5t6h7;6B7(7S7_0^7,7.0l7:7^546,8u4_597D326B0T8A8y6T7;807s6d7Y8p0.518E3U6Y8P3^6s4}4%5H8k7%7;756H6J8x3U7?6^8c827A6 718S5n777z7E0q7G7d7J8g7h5q7k8X8(6L048b3=8e7K8F918n8v040V8!8z8@8B0^8D9h8F8{886?0^0b8;6l6n9s6S5^5G8N5I9b5x0^9e928=8H9q7V7v0^2m5 0k9n2s988)8w9B6F7!9F5L044=9l6F9a7~9p048+3=1b4q0v2t2U9/491s4b2w2z2u0u1J9=0f4a0`9 0!0$0(04.