Aller au contenu

Fusionner deux arbres par la somme

Définition

Pour les besoins de cet exercice, on dira qu'on réalise la fusion-somme de deux arbres binaires si on fait la somme des valeurs de leur racine (si elles existent) et qu'on applique le même procédé à leurs sous-arbres. On fabrique alors un nouvel arbre binaire. Si un arbre, au moins, est vide, on renvoie une copie profonde de l'autre.

Une fusion-somme

Un premier arbre binaire

graph TB
classDef Nil stroke:none,fill:none,color:none;
    R("1")
    Rg("13")
    R --- Rg
    Rd("13")
    R --- Rd
    Rgg("2")
    Rg --- Rgg
    Rgd(" ")
    Rg -.- Rgd:::Nil
    Rdg(" ")
    Rd -.- Rdg:::Nil
    Rdd("18")
    Rd --- Rdd
    Rggg(" ")
    Rgg -.- Rggg:::Nil
    Rggd(" ")
    Rgg -.- Rggd:::Nil
    Rddg(" ")
    Rdd -.- Rddg:::Nil
    Rddd("13")
    Rdd --- Rddd
    Rdddg("9")
    Rddd --- Rdddg
    Rdddd(" ")
    Rddd -.- Rdddd:::Nil
    Rdddgg(" ")
    Rdddg -.- Rdddgg:::Nil
    Rdddgd(" ")
    Rdddg -.- Rdddgd:::Nil

Un second arbre binaire

graph TB
classDef Nil stroke:none,fill:none,color:none;
    R("0")
    Rg("8")
    R --- Rg
    Rd("13")
    R --- Rd
    Rgg("17")
    Rg --- Rgg
    Rgd("8")
    Rg --- Rgd
    Rdg(" ")
    Rd -.- Rdg:::Nil
    Rdd("14")
    Rd --- Rdd
    Rggg(" ")
    Rgg -.- Rggg:::Nil
    Rggd(" ")
    Rgg -.- Rggd:::Nil
    Rgdg(" ")
    Rgd -.- Rgdg:::Nil
    Rgdd(" ")
    Rgd -.- Rgdd:::Nil
    Rddg(" ")
    Rdd -.- Rddg:::Nil
    Rddd(" ")
    Rdd -.- Rddd:::Nil

La fusion-somme des deux arbres binaires

graph TB
classDef Nil stroke:none,fill:none,color:none;
    R("1")
    Rg("21")
    R --- Rg
    Rd("26")
    R --- Rd
    Rgg("19")
    Rg --- Rgg
    Rgd("8")
    Rg --- Rgd
    Rdg(" ")
    Rd -.- Rdg:::Nil
    Rdd("32")
    Rd --- Rdd
    Rggg(" ")
    Rgg -.- Rggg:::Nil
    Rggd(" ")
    Rgg -.- Rggd:::Nil
    Rgdg(" ")
    Rgd -.- Rgdg:::Nil
    Rgdd(" ")
    Rgd -.- Rgdd:::Nil
    Rddg(" ")
    Rdd -.- Rddg:::Nil
    Rddd("13")
    Rdd --- Rddd
    Rdddg("9")
    Rddd --- Rdddg
    Rdddd(" ")
    Rddd -.- Rdddd:::Nil
    Rdddgg(" ")
    Rdddg -.- Rdddgg:::Nil
    Rdddgd(" ")
    Rdddg -.- Rdddgd:::Nil

Explications

  • La racine vaut \(1+0=1\)
  • juste à gauche, \(13+8=21\)
  • à la droite de ce \(21\) : \(8\) et le vide, on obtient \(8\)
  • ...

Exercice

Coder une fonction fusion_somme qui prend ab_1 et ab_2 deux arbres binaires en paramètres représentés à l'aide de la classe Noeud et qui renvoie un nouvel arbre binaire résultat de la fusion-somme.

###(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.78rnb N_o=ylaepcwgu)vd4613kRmhtsP(S0+2-i:050C0u0L0t0U0s0M0m0w0s0t0M0M0q010L0U0v010406050M0z0J0J0t0j0r040P0p0s0z0:0p0k050e0`0|0~100^0v04051g191j0e1g0^0C0U0B0(0*0,0.0K0U0y0K0s1x0K0L0?050Z0l0s0u1s0+0-011w1y1A1y0L1G1I1E0L0j1h0L0K1K1u010f0#0u0k0t0J0u010(130M0v0t0k0.0S1E1=1@1#1M1(1I1+1-0?0a0m0N0j0p0v0p0M0U160k0m0X1:0j0j0u0w2e191|0k1h0e1Z2r1W1Y1X1F0C1~0.1A0k1*2b1E1p1r0)1L2B0U2D0k0p2H1E0v2k1h2p2r2V0_1?2f2J1$2O0j0}0s0?0m0F2o2Z0@2Y1}2#1M2%2)2+0S2.1@2:2p2A012^0t2*040m0G2|2q0^2 2?0.32340m0D382~2Z303e2+0c3i3a3k3c310p2(332+0E3p2;2!1t2@3u2_350h3z3b3C3d3E3w350i3I3r3K3t3v3f0d3Q2=3S3m040F0Q3X3B2K3T3F0F2-1a2/3q3Y3*3!0F2{3/2}3;3)2$3M340F373`393A3l3 0?0F3h433j3=3~3U483o4b3|464f3#3y4i453s3@3H4o3J3?473#3P4b1k2T192H2u0C1Y2z3s0w2P1.1h4D1i4B2X4z4J0X2U3R3*0H0?0X0f3i4p3S0x2+4#4u2$0f0?4J0v0U0u4*4V1$0=040O4?4d2@0?0t0l4|3}1M4_0A0V3p0m590m4$3*0M1`04010I1*0B0p4;0m0z2D1:4:1J2S0p0f172h2h0s000~0l2k0m0l2M0!5D5001585a5c1$4X040U4!4b5b4+4~04503i5U4@1M0p4(5Q0M5Z5N1M0H0w0?0n174=4z5V0.4_574i5a5}5!4}0.5P2k0L0z0j185T5,615/045;2D5L5969015P0u0$5?2X5^015`6f5~6h620Y65672V5 533d5:0p0u0z0C52304_4{5@5#6B5X516L60010p0?0g6H4q0?0B336E0j6W3S4_0b5+6o0k4.294;6%3*6J6;2$4 6P6n6M6S6U6@5W0y0t0z0w0K6m2/6h556*686,6.5r6 5_0?6K6{6R6-6O7f6}046V6Q6A314Y282d762}780?0A0A3p4j3s5P4Z7n5(5b7r3l4-040f0z2c170o0M0p0|7x2q7z4`7n7l500o3.7j7s6)6+6|7$0l0o3_7*6I7A5{2V065}6h5e0?5h5j5l1J0*0m7P7R0k0T7U7W2g1J7%0F0m0Y0m7%1`6r6t0?5R7-7k6_7(8p7s5%8n5*7b6|5.6C6e7L3s6q5|5~6g6o6u64668t3l7d6:8D6(7h7#8r7=776o558l8J0?6k8o8y8q6O7;8N3s8v5)8-3S8A6c5=7n8F7`8H8I8z0?636w8;3?8P7X4U6R6?8R938+7)8X6|8Z8G8}6R6j6l8_0?7_3:8|6z8O04717375921$6T040q9w5W860U7S8a1-9l7!996^9b7n9y7q7?6X9s7274957Z7a6y6h7/8,9K5$6~9$6N9t9U9I7C9g6s7c046Z1I659B0.9y9A8)7s9!9c7y6o9O8U9=6!9^9}309y0R9_7t8+8Wa16|a39)ad9?6#6r7|9;0C7v0L959q8.0?9|9Y9;9D9F7V9Haj989Q3Z8ra07Ya29(aG9aaq5las9I9X2/auaHae9NaM9d8*aP7w9-an5M8#04908Ma89R5;6E6GaE8Taj7lala7aN4^0?aT2}aV9a9+9va@04b02qb29La$aRb69.7`194S0u2r2Sbj4C1q4E2u2x2s501I2r4D0^0e0X0Z0#0M04.