Aller au contenu

Fusionner deux arbres par le produit

Définition

Pour les besoins de cet exercice, on dira qu'on réalise la fusion-produit de deux arbres binaires si on multiplie la valeur 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 un arbre vide.

Une fusion-produit

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-produit des deux arbres binaires

graph TB
classDef Nil stroke:none,fill:none,color:none;
    R("0")
    Rg("104")
    R --- Rg
    Rd("169")
    R --- Rd
    Rgg("34")
    Rg --- Rgg
    Rgd(" ")
    Rg -.- Rgd:::Nil
    Rdg(" ")
    Rd -.- Rdg:::Nil
    Rdd("252")
    Rd --- Rdd
    Rggg(" ")
    Rgg -.- Rggg:::Nil
    Rggd(" ")
    Rgg -.- Rggd:::Nil
    Rddg(" ")
    Rdd -.- Rddg:::Nil
    Rddd(" ")
    Rdd -.- Rddd:::Nil

Explications

  • La racine vaut \(1×0=0\)
  • juste à gauche, \(13×8=104\)
  • à gauche de \(104\), on trouve \(2×17=34\)
  • à droite de \(104\) : \(8\) et le vide, on obtient \(8\)
  • ...

Exercice

Coder une fonction fusion_produit 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-produit.

###(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(S2-i:050D0u0M0t0T0s0N0m0w0s0t0N0N0q010M0T0v010406050N0z0K0K0t0j0r040Q0p0s0z0/0p0k050e0_0{0}0 0@0v04051f181i0e1f0@0D0T0C0%0)0+0-0L0T0y0L0s1w0L0M0=050Y0l0s0u1r0*0,011v1x1z1x0M1F1H1D0M0j1g0M0L1J1t010f0!0u0k0t0K0u010%120N0v0t0k0-0R1D1;1?1!1L1%1H1*1,0=0a0m0O0j0p0v0p0N0T150k0m0W1/0j0j0u0w2d181{0k1g0e1Y2q1V1X1W1E0D1}0-1z0k1)2a1D1o1q0(1K2A0T2C0k0p2G1D0v2j1g2o2q2U0^1=2e2I1#2N0j0|0s0=0G2n2Y0?2X1|2!1L2$2(0=0R2,1?2.2o2z012?0t2)040H2`2p0@2}2;0-30320E352|2Y2~3b0=0c3e373g392 0p2%310=0F3l2/2Z1s2=3q2@040h3v383y3a3A3s040i3E3n3G3p3r320d3e1j2S182G2t0D1X2y3o0w2O1-1g3X1h3V2W192-053%0W2T3N2J010I0=0W0f3T3F3_0x0=0m3 3^2#0f0=0f0z2b160o2R2O0z2c452:3O0;040P4j3x3_0k0=0t0l0o2+3/2{3w2~4m0b3e44402#4t4v2_4y2p4A3o4m0A0U3l0m4T4F461L0N1_04010J1)0C0p0T1I0)0m4a4c0k0S4f0D4h0M2f1I4u4w0m0X0m4{1_4S4U4N3O3{040T3~4L044V4k3_4m4o5a544r4I4w4E5i1#0p42570N5m4G1L0I0w0=0n160u4p4B0=0A5t4W0-5p0=3q5G5d1#5f5C3o4s04505M4q5o5q0T5s5a5c5W5v5x045z2C5Q4l5E4R5a064U5?5$2~562j0M0z0j175#5n5(5y5A524T610-560u0#5B5h5u0-4m5:2U5=5@666e2 0=0C310u5}5V2~0p0=0q6t5R5k4x2W6m6v040g5-5j046p1H6s606D0=0B6y3O5S5U6d5H016E6G6V5N2=6o6q6M6i6k6l6W5S0y0t0z0w0L6c2U5^3o6E6x6N6-494b0T4d4=4@6H5O0=5g6C6~5T4v6B3:6O6F756$046/6;6?7h6f0=4D6}6#3a5k4K797s6X0=6Z7w5%7t7j6:6=6@7e6W4P655@676n040D272c7H2{6_3O6{6R6I4.710k4e274?4i6!7C015P7+3h6A7n7y7g7/6z7P7R0M7T4M6m4C7Y4H7b0o7v7I7x6Y7=5S7Q4)7|7=7K5;6+7V3_5`0X5}5 6^7N5S5z6r0D8e77896%6L0j8u047q8o6m6.7F7m7^5.8B817i8b7S8A5F5;183=0u2q2R8U3W1p3Y2t2w2r4u1H2q3X0@0e0W0Y0!0N04.