Autour des arbres binaires (2)

Différentes représentations

Cet exercice demande d'écrire les méthodes calculant la taille et hauteur d'un arbre binaire. Il fait partie d'une série dans laquelle on utilise différentes représentations :

On rappelle qu'un arbre binaire est :

soit vide ;
soit composé d'un nœud appelé racine et ayant une valeur, et de deux arbres binaires appelés sous-arbre gauche et sous-arbre droit de la racine.

On représente dans cet exercice les arbres binaires à l'aide d'une classe AB ne possédant qu'un seul attribut racine.

Si None est affecté à cet attribut, alors l'arbre binaire est vide.

Dans le cas où l'arbre binaire n'est pas vide, son attribut racine est un objet de type Noeudqui a trois attributs :

valeur qui est la valeur portée par la racine ;
gauche est un objet de type AB et représente le sous-arbre gauche de l'arbre ;
droit est un objet de type AB et représente le sous-arbre droit de l'arbre.

Les classes Noeud et AB

class Noeud:
    def __init__(self, gauche, valeur, droit):
        self.gauche = gauche
        self.valeur = valeur
        self.droit = droit


class AB:
    def __init__(self, gauche, racine, droit):
        if racine is not None:
            if gauche is None:
                gauche = AB(None, None, None)
            if droit is None:
                droit = AB(None, None, None)
            racine = Noeud(gauche, racine, droit)
        self.racine = racine

    def est_vide(self):
        return self.racine is None

    def __str__(self):
        if self.est_vide():
            return "∅"
        else:
            return f"({self.racine.gauche}, {self.racine.valeur}, {self.racine.droit})"

Créer un arbre binaire

Les deux classes Noeud et AB décrites ci-dessus est déjà importées dans l'éditeur.

Utiliser ces classes afin de représenter les deux arbres binaires ci-dessous :

flowchart TD
    A0((0))
    B0((1))
    C0((2))
    D0((3))
    E0[ ]
    F0((4))
    G0((5))

    A0 --> B0
    A0 --> C0
    B0 --> D0
    B0 ~~~ E0
    C0 --> F0
    C0 --> G0

    a((a))
    b((b))
    c((c))
    d(( ))
    e((e))
    f((f))
    g(( ))
    h((h))
    i(( ))
    j(( ))
    k((k))

    a --> b
    a --> c
    b ~~~ d
    b --> e
    c --> f
    c ~~~ g
    e --> h
    e ~~~ i
    f ~~~ j
    f --> k

    style E0 fill:none, stroke:none
    style d fill:none, stroke:none
    style g fill:none, stroke:none
    style i fill:none, stroke:none
    style j fill:none, stroke:none

Par commodité, on n'a pas représenté les arbres vides.

ab_int sera l'arbre portant des nombres entiers, ab_str celui portant des caractères.

Évaluations restantes : 10/10

.128013,:êag)LR1Iiknè9N/SAé=vmsBuhb.84;y7ex6j2odt c0(r5_P3qplf050P0J0Q0e0l0$0y0R0S0$0e0y0y0v010Q0l0#010406050y0A0x0x0e0V0H040s0O0$0A0{0O0n0R020e0x0#0G0R0i0J150V0!0A0J0y050r12141618100#041w1D051G0r1G1I1D100P0l0w0:0=0@0_0B0l0f0B0$1W0B0Q0~050+0C0$0J1R0?0^011V1X1Z1X0Q1)1+1%0Q0C0O0P181(0V1E0Q0B0:1b0y0#0e0n0_0N011-1T010%0-0J0n1j0J1%282a2f1/2i1+2l0x2n040a0R0Y0V0O0#0O0y0l1e1g0)260V0V0J0S2I1w2p0n1E0r242U0Q2221230P2r0_1Z0n2k2F1%1O1Q0;1.2(0l2*0n1~1P1%0#2N1E2S2U2 11291g2:2g2^0V150$0~0R0j2R330 322q351/37393b0N3e2a3g2S2%013l0e3a040R0Z3p2T103s3j0_3v3x0R0F3B3r333t3H3b0W3L3D3N3F3u0O383w3b0L3S3h341S3k3X3m3y0I3$3E3)3G3+3Z3y0E3/3U3;3W3Y3I0p3`3i3|3P040j0T413(2;3}3,0j3d1x3f3T424a440j3o4f3q4h49363?3x0j3A4n3C3%3O4s0~0j3K4w2U2|0J2U2.2X0P2#3t0S1~2x0(1P1E4G2~3f3L054O0)4V4i360~0e0C0X4v2 0R4y3V0O0~0v3L4.3:4j0~0t0z4X4_2g0}040U4~3{4a0m0S0~0q1f0J544$1/510b4@4/3|0x0l0~4,4W4 5f0~5h4E4^552g57595b5d4q5r040g483O4(4*4D4-5j4a4;044?5u5M4%044|5B3t51534E5S1/5y045a2*5W3V5g5i5q0_5l0~5K5p5w5D5t5L5/015%5)5c5!5|515F4E4p5H044)0X3R5R5|5O5Q5{5^3G4{4}616h015Y5+3|5~5A6l5e0_5-6c6m5;046b31625s5.6m6r5*6t5C6v0~642 663V0n5I0X4e6g6u016e6F6W6R5U6k6C6m6o6J67695o3q5#6L045`3f5v6W6z6U5@6W6w6V6K5}585(6s6(6}6M5G6Q6S4m6 3t6Y6x6!6j6p4a6*75706#695?6/6D6=6Z706z7b6|706~6@6:3u6S6B7x5X77657B7n4*2?0Q7t7d4=7O796$7i500~5Z7l6,4*6{7q6)6E7f7u5m04476+5,7(7c7S697w7$765E3S6P436S0B7R3|7e7;7}7T7.3|7k7F3V6H607Y7/7s7)3t0y2d041:017U5_8056725 8n6;6N4g7J6S0m8p2g827A5|6#5V867j7W8t715z6I8d877:8D6m8i0~5}8m8H7V8f838q8M8c898P7`7I8E6S8%3q6^708C8/8x858O8I528K7K0X7 8X8o8g3V8T8k2n8K7z8?5|8b977H6O8@690%8A1/8=2T8:678G8_8Y7X8(8#738N9s8Y6?998S8j2h8W9p918!5T698z908u7884690C9i0_9k3y8@9o9w5D9r7^709b9K6n8Q9z6W94010C9D9W6;9y9l9f4*8.2T7B639M4`684*0S9Q6X7Q92849V9Z7G8{9$8}9h9$989=5|9+589c8Z8R6W9#9E9L8+6m8}0y2Ya19S9m7Sa69_7r9YaAar6S9Pad9(af9A8U0e9.a78e9;9T8,9~0Xa0aH8*9e0r4Z4H1F2}1w4J1w0Q4La*2Z2V1}1 2X4)1+4I4S1C4#702N0x0X0%0e0m0J8~0Z0~1o1q1s1u0R0c4X1J3g1D0k0$0R1u0Q0R0e0A0@0l0R2Ebp1*1,2K0P0u2:2N0V0R1+0/160C2Nbj1g0A2*0R0y0J0A1+0R0%0O0l0y0D0R0hba0)0A0K0R0x0u244P0/1fbl1+0A0VbE0w2a0+0fba0*0R2?4O0n0w0u0n0l2k0Q0/bcbe10bP3g1Z040h0e0Rbxbz0e2IbI0RbK1,bSbUbr0J38b{2K0wbTbB0=bM2Y0A2Pb:bv1,0$00bFbHb00S2j2w0n0Q0bbMbq0J0$bQbk0Rby0V2H1,2k0R0M0O0Ab@bm0w2ObC002?0)cPcj0l1f0D1wcc10c}1H040Dd215cq0-bjat0R2Y0o0/cL2jcgbvby0=bAbC1,150Ab?cqcJ0JcR0S16b|bicX0V0e0#0l0)cOblbx1ZdtdE1,2Natcs260B0u2NcPcg2a0/bQ0#0=0S1pc4df0/0w0l0V0fbPb`bl29dQ24dbbZdTbCcfchdic^c`1F3g0rc c 1Dcecgdh16d{1gb)dz1,d.cY0+0#co0ecM1Z0Q1,0fdy0ndCd!cHcZ2HcE2L2N2PcF0:0B0eb90R0O0C0M0*c{c8c|0lcbeLd20Dd40/d6cXda0/1O0%2ieieybN0RdQ0PbH4O1kekdfd@cA0VcC0Qeu2KcHdqbR2?3wcS1k1+dDcl1Z0yc,czd_e62IeIc 0rcaa`0kcMcRbDe4ci2I0/01c%cnbRbT0y2e2Eb:dyc3dR0d2Y1,esek0/e*2wbM0A2Hbbd}1N1P3t1;1Y1!1$a{3t2t2k2m0~2z0s0Sc!0#bl0Y0Hb*0n4X4U3%304Wa!fS7=7LcPava39G3k7haWaC0 0Rg1g2g3g19U6%9/9%a96Og4gcg4g6ajf 7Bang8aeaR6y7+6.aD7_aQax6q8r74gk6MaQ06gdgBgt4a6`ajgzgCgdgigv9vaO8)gHgIgD8Y0ggPgI7B6z7-aog9gUgCgff~3SgQg3g%gZ88gN9t8saWgsgW7+7pgq7yaIgmamgL9^f=8)gTg)g*g55|7vgGh4h5g,gxgag8gjg/9xa16z7Ehh9Fal9!g ajh365g*9`9d4ggBhvaX4g7|9}69at0Vf_5Pa18Fg7hm6;f gAgQhchMg9hOh5g2gK8$h9hthVgR1/0y0j0~000C00hZgbh#hRg`a8hUh#g+aSazh18`gh9ahqg=a1h(h*0Bh-i1a4g:gwhS63g#h^7B9+96i7h/h^h66Gi0g-g|hPhVhzhsijg$7rithxhQag9BaMh.iygVh`hLh=8eh@iriGgghaikhX9uh0hzidh:agh)04000%i6ioak4oikhWiMg(9$hgiIgOi2iX000mi#hdg?h hYaWixi(iV7%5EiUiF8Si=0Si^ibipiei{iRiDi j47_8vjfgcis3$aZ4P4Fa%0r4J10jr0*0,0.04.

Taille

Compléter la méthode taille de la classe AB. Cette méthode renvoie la taille de l'arbre binaire représenté par l'objet en question.

Exemples

>>> vide = AB(None, None, None)
>>> ab_1 = AB(None, 1, None)
>>> ab = AB(None, 0, AB(ab_1, 2, None))
>>> vide.taille()
0
>>> ab.taille()
3

Évaluations restantes : 10/10

.8709.128013:,ag)1ikn9N}/SA=v{msBuhb.84y7e6+2odt c0(wr5_P3plf050K0F0L0e0i0X0v0M0N0X0e0v0v0r010L0i0W010406050v0x0u0u0e0R0D040p0J0X0x0?0J0k050o0}0 11130{0W041c1j051m0o1m1o1j0{0K0i0s0+0-0/0;0y0i0f0y0X1C0y0L0_050$0z0X0F1x0.0:011B1D1F1D0L1L1N1J0L0z0J0K131K0R1k0L0y0+160v0W0e0k0;0I011P1z010Y0(0F0k0e0u0F1J1;1?1{1R1~1N21230_0b0M0U0R0J0W0J0v0i190k0M0!1/0R0R0F0N2o1c260k1k0o1-2B0L1+1*1,0K280;1F0k202l1J1u1w0,1Q2L0i2N0k1%1v1J0W2u1k2z2B2)0|1=2p2T1|2Y0R100X0_0M0h2y2-0`2,272/1R2;2?2^0I2{1?2}2z2K01320e2@040M0V362A0{39300;3c3e0M0C3i382-3a3o2^0S3s3k3u3m3b0J2=3d2^0G3z2~2.1y313E333f0E3J3l3M3n3O3G3f0B3S3B3U3D3F3p0l3!2 3$3w040h0O3+3L2U3%3P0h2`1d2|3A3,3@3.0h353|373~3?2:3W3e0h3h443j3K3v490_0h3r4d3t3 483(4i3y4l464g4p3/3I4s4f3C413R4y3T404h3/3Z4D3#4F4v0h3*4J4n3N4v0I3;4P474R3P0I3{2)4t4A4G0I434#4z3-4(4c4+4E4o4Y4k4:4K4=3X0I4r4^4Q3V4S4x4~4W504Y4C534u4Y4I584%4S4O5c4-4v0V4U2+1p2%1c2R2E0K2I3a0N1%241k5p1n5n5l2+5u0!2(4_1R0j0_303s4,3@0Q2^5L4;310N0_0m0J0F0x0K5Q5G0;0^040c3z0M5+0M5M1|5I040!0Y5!4 015O3f5@541}0u0_0T0T2W2n615|3a5%0P663C0z5%0v0F0X5?4l5.1R5%0d3s5-5R3n0_0f0e0x0N0y0F6a3$6l6n6j6q040s3d5X0R6y3@6A4l6o5#3b0_0K2i2n6J1|5%0g5)4s5,6!6N5^6c0_6e6g6U1R0J0_0A6,6D6s6u6w6B6p016.040r6_6O0k6r6t6v6x6Z6#5+6C016(046*6h2+6`6|6:6i6`716E6G0x6I6M796|6~7q7k0_6F1N7o5*776$5}7b7d6;6{6/7G7l6R0J6T7u6O7s6 5^7K6S0L3z064$3$5:5K7j6O5`5-7$7S5T040q0w7G5%6Y4#6!795:5=7G7(7G0Y5 0461630L657*5}687G7E6f7e2|796L2)7C3v726@757f6O8e2|8g4A0_0R0e0N2W8k8c6`8n378p3-6Q7U7:0_6X7A777^0_0i8b8A797l8s8u2N7R5}0J5`0i0v8U3a8W0_2Y7V7O5^0j7,5V8T85670_7=3}7B6#8K048M8!8q046?748}3$8$8{8Z8*5}8,5U1a8w378d8=8I8^8_7v8 736^978#0_7t8f8P0_7.8F04698:3C99048.9c2A9e046m9n9z8-9b9v9H9r6`9A9C9v0g9g8^8`8|9I8C5;8E9Y3@948Y923@9Q9L9y6z9f769h9i708D7M8)9O7P9p9*2:9t7/9.6K0_9x8l8+9K8/a6860_9N8o7^a89D5F5^8z2A8B9+ag9S9U7B9s048R8v9~6-9}9$9 9B5W5Y9va58x9@9k8j9Maw6Daua9aGajacaL6P9!9_ap9;9?6%6d8a7G7h7J8r8tavazax6}aS8Qa*aO45067@9P6Q0F8N9E6`7|a22:0Y0_0F0v830s0i0!aE88a!6+b06k8G8?459Va_at0#7o1ba,0;89bdaa9o047ibt8~aNaham1|9(969{a79aa=3ja@5,8`7`be0;a bx3-b2040$0(1NbabO7abca|aiab048HaXa^6O5:9XbF7Db#a$7IbZ7lb4b6b8ah9F0Pb*7?9=bB5H8rbm0Rbob:3a0u0i0_5k8@arbk2u0LbnaScb4iaS6|0HaSbrb$7rb@bR40a)8Sb}7gcvaP5}7l909mcwbCcC9d9jbV0XbXbZ689Tbp7H04cqcTcsb?bva(ata;cA9|c!b^9^7NcIa-bwcD8hbU0%cOc(aQ9wcS4#bK78bkbNc.bP5PbZ7~600Tb50R84d20187bZcYcQbgaqc b-8Lb$c3bqb=bZa%c+04b`0Tb7b9dhc{bh3jc2do015:cickcT0v1_04010a01djdE5:6f6e9vdB0`dD8`dHc7aS0v0e0_ct6`dK0_01aFcL6O2m0_0tbb6)a#drcKa}aHbzcZc:d:7S8i91bZd=040n7Gd,9G7)dce7d@dfdqdcdsdca:cze0c#7x6Heacce8eadL0dedc;3Cefd^7cd`ejd|b%c=d d{c*elc,9`ez3$e7e9e6dL0gdP4y0o5D0F2B2$e!5o1v5q2E2G2C1$1(2E0e1Me%0o5p0{e@0#c@0v04.

Hauteur

Compléter la méthode hauteur de la classe AB. Cette méthode renvoie la hauteur de l'arbre binaire représenté par l'objet en question.

Exemples

>>> vide = AB(None, None, None)
>>> ab_1 = AB(None, 1, None)
>>> ab = AB(None, 0, AB(ab_1, 2, None))
>>> vide.hauteur()
0
>>> ab.hauteur()
3

Évaluations restantes : 10/10

.8709.128013:,ag)1ikn9N}/SA=v{msBuhb.84y7ex6+2odt c0(wr5_P3plf050L0F0M0e0i0Y0v0N0O0Y0e0v0v0r010M0i0X010406050v0x0u0u0e0S0D040p0K0Y0x0@0K0k050o0~1012140|0X041d1k051n0o1n1p1k0|0L0i0s0,0.0:0=0y0i0f0y0Y1D0y0M0`050%0z0Y0F1y0/0;011C1E1G1E0M1M1O1K0M0z0K0L141L0S1l0M0y0,170v0X0e0k0=0J011Q1A010Z0)0F0k0e0u0F1K1=1@1|1S1 1O22240`0b0N0V0S0K0X0K0v0i1a0k0N0#1:0S0S0F0O2p1d270k1l0o1.2C0M1,1+1-0L290=1G0k212m1K1v1x0-1R2M0i2O0k1(1w1K0X2v1l2A2C2*0}1?2q2U1}2Z0S110Y0`0N0h2z2.0{2-282:1S2=2@2_0J2|1@2~2A2L01330e2^040N0W372B0|3a310=3d3f0N0C3j392.3b3p2_0T3t3l3v3n3c0K2?3e2_0H3A2 2/1z323F343g0E3K3m3N3o3P3H3g0B3T3C3V3E3G3q0l3#303%3x040h0P3,3M2V3(3Q0h2{1e2}3B3-3^3/0h363}383 3@2;3X3f0h3i453k3L3w4a0`0h3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0h3+4K4o3O4w0J3=4Q484S3Q0J3|2*4u4B4H0J444$4A3.4)4d4,4F4p4Z4l4;4L4?3Y0J4s4_4R3W4T4y4 4X514Z4D544v4Z4J594(4T4P5d4.4w0W4V2,1q2(1d2S2F0L2J3b0O1(251l5q1o5o5m2,5v0#2)4`1S0j0`313t4-3^0R2_5M4=320O0`0m0K0F0x0L5R5H0=0_040c3A0N5,0N5N1}5J040#0Z5#50015P3g5^551~0u0`0U0U2X2o625}3b5(0Q673D0z5(0v0F0Y5@4m5/1S5(0d3t5.5S3o0`0f0e0x0O0y0F6b3%6m6o6k6r040s3e5Y0S6z3^6B4m6p5$3c0`0L2j2o6K1}5(0g5*4t5-6#6O5_6d0`6f6h6V1S0K0`0A6-6E6t6v6x6C6q016/040r6`6P0k6s6u6w6y6!6$5,6D016)046+6i2,6{6}6;6j6{726F6H0x6J6N7a6}6 7r7l0`6G1O7p5+786%5~7c7e6=6|6:7H7m6S0K6U7v6P7t705_7L6T0M3A064%3%5;5L7k6P5{5.7%7T5U040q0w7H5(6Z4$6#7a5;5?7H7)7H0Z600462640M667+5~697H7F6g7f2}7a6M2*7D3w736^767g6P8f2}8h4B0`0S0e0O2X8l8d6{8o388q3.6R7V7;0`6Y7B787_0`0i8c8B7a7m8t8v2O7S5~0K5{0i0v8V3b8X0`2Z7W7P5_0j7-5W8U86680`7?3~7C6$8L048N8#8r046@758~3%8%8|8!8+5~8-5V1b8x388e8?8J8_8`7w90746_988$0`7u8g8Q0`7/8G046a8;3D9a048/9d2B9f046n9o9A8.9c9w9I9s6{9B9D9w0g9h8_8{8}9J8D5=8F9Z3^958Z933^9R9M9z6A9g779i9j718E7N8*9P7Q9q9+2;9u7:9/6L0`9y8m8,9L8:a7870`9O8p7_a99E5G5_8A2B8C9,ah9T9V7C9t048S8w9 6.9~9%a09C5X5Z9wa68y9^9l8k9Nax6EavaaaHakadaM6Q9#9`aq9=9@6(6e8b7H7i7K8s8uawaAay6~aT8Ra+aP46067^9Q6R0F8O9F6{7}a32;0Z0`0F0v840s0i0#aF89a#6,b16l8H8@469Wa`au0$7p1ca-0=8abeab9p047jbu8 aOaian1}9)979|a89ba?3ka^5-8{7{bf0=b0by3.b3040y6u0M6IbbbP7bbda}ajac048IaYa_6P5;9YbG7Eb%a%7Jb#7mb5b7b9ai9G0Qb,7@9?bC5I8sbn0Sbpb=3b0u0i0`5l8^asbl2v0MboaTcd4jaT6}0Ia:0z0`110Gb!bS3^bsb(7sb_czaBbAb^bwa)aJ92b#a(b`0`bW19bZb#690gae8P6{cBcIbxaQ5~a;8Tb 7hcEc%8iaV7OcFa.c$9e9kcRbY7AcUa50g9U4tbL79blbOc=bQ5Qb#7 610Ub60S85d60188b#c!c}b+bi3kbkb/8Mb(c5brb@cNc-c^aIb|0Ub8badlc1dn0{c4dt015;ckcmbq010v1`04010a01ard3dq046g6f9wdGd29i8{dMc9aT0v0e0`cC6{dQ0`01aGdy5_2n0`0tbc6*a$dwcJcPaua=c+9}e3dg7m919ndgd|040n7Hd?9H7*eece04d~djdvdgcOeaa*c*c#cK7ycTem0`ehb#ej0delc.3Defepdgdkesdxa~aIcHe2c@eQ7T9_c;eI3%efeDeedR0gdV4z0o5E0F2C2%e.5p1w5r2F2H2D1%1)2F0e1Ne;0o5q0|f10$0(0*04.

Parcours en largeur

Compléter la méthode largeur de la classe AB. Cette méthode renvoie la liste des valeurs des nœuds rencontrés lors du parcours en largeur de l'arbre binaire représenté par l'objet en question.

La classe File décrite ci-dessous est déjà importée dans l'éditeur.

Interface de la classe File

f = File() : crée une file vide et l'affecte à la variable f;
f.est_vide() : renvoie le booléen indiquant si la file f est vide ;
f.enfile(x) : enfile l'élément x dans la file f;
f.defile() : défile un élément de la file f si elle n'est pas vide et le renvoie. Provoque une erreur si la file est vide.

La classe File

from collections import deque


class File:
    """Classe définissant une structure de file"""

    def __init__(self):
        self.valeurs = deque([])

    def est_vide(self):
        """Renvoie le booléen True si la file est vide, False sinon"""
        return len(self.valeurs) == 0

    def enfile(self, x):
        """Place x à la queue de la file"""
        self.valeurs.appendleft(x)

    def defile(self):
        """Retire et renvoie l'élément placé à la tête de la file.
        Provoque une erreur si la file est vide
        """
        if self.est_vide():
            raise ValueError("La file est vide")
        return self.valeurs.pop()

    def __repr__(self):
        """Convertit la file en une chaîne de caractères"""
        if self.est_vide():
            return "∅"
        return f"(queue) {' -> '.join(str(x) for x in self.valeurs)} (tête)"

Exemples

>>> vide = AB(None, None, None)
>>> ab_1 = AB(None, 1, None)
>>> ab = AB(None, 0, AB(ab_1, 2, None))
>>> vide.largeur()
[]
>>> ab.largeur()
[0, 2, 1]

Évaluations restantes : 10/10

.8709.128013:,kn9àSA{vFBsuO8;y7e[620w]r5_pag)R1IièN/é=mhb.4joPdt c(}3qlf050!0v0#0G0M0,0o0$0%0,0G0o0o0R010#0M0F010406050o0p0S0S0G0C0t040i0Y0,0p110Y0f0$020G0S0F0s0$0J0v1b0C0+0p0v0o050P181a1c1e160F041C1J051M0P1M1O1J160!0M0l0_0{0}0 0T0M0H0T0,1$0T0#14050;0U0,0v1X0|0~011#1%1)1%0#1/1;1-0#0U0Y0!1e1.0C1K0#0T0_1h0o0F0G0f0 0y011?1Z010-0?0v0f1p0v1-2e2g2l1^2o1;2r0S2t040b0$0Z0C0Y0F0Y0o0M1k1m0/2c0C0C0v0%2O1C2v0f1K0P2a2!0#2827290!2x0 1)0f2q2L1-1U1W0`1@2.0M2:0f241V1-0F2T1K2Y2!35172f1m2_2m2~0C1b0,140$0K2X3915382w3b1^3d3f3h0y3k2g3m2Y2-013r0G3g040$0*3v2Z163y3p0 3B3D0$0W3H3x393z3N3h0D3R3J3T3L3A0Y3e3C3h0x3Y3n3a1Y3q3%3s3E0u3,3K3/3M3;3)3E0r3^3!3`3$3(3O0g403o423V040K0z473.2`433=0K3j1D3l3Z484g4a0K3u4l3w4n4f3c3|3D0K3G4t3I3-3U4y140K3Q4C3S4o4x444H3X4K4v4F4O4b3+4R4E3#4q3@4X3_4p4G4b3 4$414(4U0K464,4M3:4U0y4d4=4w4@3=0y4k354S4Z4)0y4s514Y49544B574%4N4~4J5c4-5e3}0y4Q5h4?3{4^4W5n4|5p4~4#5s4T4~4+5x534^4;5B594U0*4`5F4.3=0*504m585L3}0*565P5d4}5S5b5V5i5X3D0*5g5!5o4h5S5m5*5t5,5%5r5/5y5S5w5@5C5M5A5{5G5M5E5 5R3D0W5J3l1L331C2@2%0!2+3z0%242D0.1V1K320v34684K056h0/6p5+0e143p3R5Q2m0A3h6A5W3M0%140O0Y0v0p0!6F5#0 13040c3Y0$6W0$6B1^6x040/0-6P5+6D3E6)5:0-0S140E0E2|2N6=6-3z6S0(6`3#0U6S0o0v0,6(6r6G016S0d3R6Y770f140H0G0p0%0T0v6~42797b6Z3M140l3C6M0C7m4g7o4K7c6Q3A140!2I2N7x2m6S0I6U4R6X7O7B5+701472747I1^0Y140V7W7r047g7i7k7p777Y040R7+7C7e7%7h7j7l7N7P6W7q017S047U75377,7Z7#7D047t1;0p7w7A7}7-7/8d7d7s7u8b6V7{7Q5:7 81867-7!767;7E7G0#7:5+8f8A5:7=7F0Y7H4R0652426#6z8v6*6E8P8E6I040j0n866S7M517O7}6#6%866+6Y8S3z6/6;6?0f6^0E8Y146}8-6 71738268777z358o3U7f7@7*8{7n147a8h8w040C0G0%2|7_837C923l944Z8x8H8z997y147L8m7{8%140M8 3w9p49149g9i2:8D3z0Y6+0M1B9d8B6+2~9t938%8U6K9K9u7J148!4m8n7P9A049C9L9q7?7)9k9o8e9O9Q9W770e9Y1l9?3w7}8Z9y9*9+8i9;7^9/428C9R8E148W8^048`9l6w9~9!ak5:9n9E9X6J9 ah9c9{7C9}atan909m9wa49*9,9.ad956$8yaa4g9N9B9`9@9|ama02Za29%aFa57|a78G8Iax8B148ga)ae8V8X9#1^6|86az049ZaV6vap9baN2ma^a`ava 6!aUah0IaZ9za79I9jb40 aca-aK6K6M6Oa;6R8_867=7(a9bm78a~aJ9:bcaBa191bvbh9:a%9VaC5+7Kb99F4g8q8~8s85bt7=bya{bL2mbgaS9ebT3Y068$9|7E0v9DaW778+bp0-141A0#0E0l0M0/ahajbH8p8}7Vbt7K9(4uaGb(9f0:8b0fbe7~b b+a|9MbQaoaKb!bwab9_cbb1au8Jb%ayb)ce7}b.bRb:040{0C0H7vb{86bNc0ci3#c2bKaHcebV1^cHcv84048ucJ9G04b=b@b_a{aXai9x7`a!9,2T0#c9cb6S0w0BcMbb1A0p0,0;bGarcTa,bYbI140wcGcdbPcUbp9H9hbdbt8td9888k8ccW9v04c?c*a69e2zbU8ea+cb7=0m2pb{b8dncs5+7=dqd7cVb}aK2qdEc1bobtcRdFdfckdjbWchdH9:br98dSa=aEdA6X7}dDdxdddUbA9edJd*dZbnaid57TbOd+d8bRda9Jc$cTdGd-dC9ra(dV9a04dz8#8n9,0A1#1;cbaP049Udu14dKd;01ded|cY0ob?b^b`dLc(c33Ia!a#9e0Gegdtcl4peld:e6aOd,b,9e6%eJe2a}c(bKdB5:6#aIbDcm14ejeG3c14eDd`e1eNe3eretc#dyey15eAdoe.2T18c{0Gc}e-5:epen7=0G0F0F2qblena?eqe*enf2eKe(9fdbbzf0cgd{f38j8adifgd!e8eUeba7emfsbfeMcf9:d/efewb|eRaKfdfzeofBd(d}dcfefNa7dXd aDfud$c+fxeQfl3#fffIfD0ffyf)e7fHf$cXfKf-eLfnfLbSfjfVa*f^f?fhbFb7c@ctc7c.0Ccae%3q9Hc_e}e 15b$d%c68)btcxen8/046=es0C6_fGd@80d_fa9we?ggbag4eYd1b~d^cIfLf(f:eHe/c!evgxexfveB6wgbg6g8eZ4g0o2j04010a01g3gTcY0@f|eSgze^c,c8g7cb0o0Gel86gZ1401f/fC422M140kgu8re+dQf{dPeqfUg{0M140)g{g!0d8,enh204h4dNd6h7eqdRgIfS9e89cEbthmhghzhihkfLhmhoendOhrfofid~hahLg1hzhe04hBhlg!0Ig(4X0P6t6o69h$0P6c1C0#6eh+2)2#23252%0G1:h(6c1Ih04g2T0S0E0-0G0e0v0E0T0*141u1w1y1A0$e?1L3m1J0L0,0$b=0$0Q7g1;2C0f0#0$2K0}0Mh^0$2Q109g2N0v0C2k7j0Gib0$hx8b0$0X0pes1=f50C0N0^1;iy0Qdqiq0#hjh@0Y1j9Pg^ir0$0h0_0:0#1=0o1hi(1liti%0C0$0{0$0S0Q2a6i6Yh#cA1ccD8lh!6i3E2Qi}3p1=6sjaagj96uidif1T1V3z1`1(1*1,6m6a376rj4eV3z8(b*8*8Rf3czcBj7frf ftg 7}hJgPc)eagBe`gcc|eE7.c:d3dmjRe_a.f,2ZcPfAjXg97$dwfFgP0(e99)fwdpf#h|dTf~gKfhfEg-6{dMhIhqjPg)eW14edj`j*eo9T0Ygekcd)j:huj}j{gagMeuk1cK8_jQj@fZeCjWd0c~j_kjjKj+e,km7$ePkBj~jLj?c4eAfOc7e|jVhKf_e)f6f8cFfchOkThMfQkkkEkOiKjJkJd=kLezkNc60-3%ekcYf+2gkg9^9BgWgEk2d?kYkSkC87htl4gJkF87hcewawk 9:f=k,fMklkOl6lhl8kOhQjPg/e^ghgCcOk|eikfk@dJk`kZl47=cZkpe=gRa5kOj(l9lna7k0kXhLlAirg2fYkc6#c-c/j-l5jUe~3,jjh(6n2!h`1N040q0pik0f6h2Thji*iU0G0$237iiVjg2Q3#jq1|1+2ug4k=k+2!jy7M1S6k2^42m4js31jv6q37jyltg*gjenglf_jGj6hyj;h5gwfLcLlVlkl$k{c jY04c=k7aKlLkcbXkze.j/kqf.k.e@j^e.lLdsljlOf+j`c%jM77jOmBd#j#jz3#6#kakI6,7,kemGkAmTf@k(lOesgNm}9$gQlVm:f;kxk@mZe0dfkHn3kKlImEkQl%l3lhf4kV0ff9m-l1hLlglMhve`h9nll97=k*lUm/mXa.0Hn9l!f4lCnmfPfknvm#9elbnEjSk89-lvm_e#lynJ7fnLnAb;n1lGfGktkMlskheIm@m!m d.m%n=bBnsk!nHewmVgAlJa$nIgXfhnun?h8hNnzloaMn6mpnVgDmQf1m`k@nql7nwa.lFe;n,lrn/lKm(nceqlPgteqomlhbJmDc6lYg?n#kPc`kR57l)2!l+6b6l16h)0:0=0@04.

Parcours en profondeur préfixe

Compléter la méthode prefixe de la classe AB. Cette méthode renvoie la liste des valeurs des nœuds rencontrés lors du parcours en profondeur préfixe de l'arbre binaire représenté par l'objet en question.

Exemples

>>> vide = AB(None, None, None)
>>> ab_1 = AB(None, 1, None)
>>> ab = AB(None, 0, AB(ab_1, 2, None))
>>> vide.prefixe()
[]
>>> ab.prefixe()
[0, 2, 1]

Évaluations restantes : 10/10

.8709.128013:,êLkn9DàSA{vBsuO8;y7e[620w]r5_pag)R1IiUN/é=mhb.4x+jVoPdt c(}3qlf050)0x0*0I0O0;0q0+0,0;0I0q0q0T010*0O0H010406050q0r0U0U0I0E0v040l0%0;0r160%0h0+020I0U0H0u0+0L0x1g0E0:0r0x0q050R1d1f1h1j1b0H041H1O051R0R1R1T1O1b0)0O0o0~1012140V0O0J0V0;1+0V0*19050_0W0;0x1$1113011*1,1.1,0*1@1_1=0*0W0%0)1j1?0E1P0*0V0~1m0q0H0I0h140A011{1(010=0{0x0h1u0x1=2j2l2q1}2t1_2w0U2y040b0+0(0E0%0H0%0q0O1p1r0@2h0E0E0x0,2T1H2A0h1P0R2f2)0*2d2c2e0)2C141.0h2v2Q1=1Z1#0 1|2?0O2^0h291!1=0H2Y1P2%2)3a1c2k1r2~2r330E1g0;190+0M2$3e1a3d2B3g1}3i3k3m0A3p2l3r2%2=013w0I3l040+0/3A2(1b3D3u143G3I0+0Y3M3C3e3E3S3m0F3W3O3Y3Q3F0%3j3H3m0z3%3s3f1%3v3,3x3J0w3;3P3@3R3_3.3J0t3}3)3 3+3-3T0i453t473!040M0B4c3?2 483`0M3o1I3q3(4d4l4f0M3z4q3B4s4k3h413I0M3L4y3N3=3Z4D190M3V4H3X4t4C494M3$4P4A4K4T4g3:4W4J3*4v3|4$3~4u4L4g444+464-4Z0M4b4;4R3^4Z0A4i4`4B4|3`0A4p3a4X4(4.0A4x564%4e594G5c4,4S534O5h4=5j420A4V5m4{404}4#5s515u534*5x4Y534:5C584}4_5G5e4Z0/4 3c1U381H2|2,0)2:3E0,292I0?1!1P370x393q3W055Y0@5*5t010g193u5,5i1}0C3m5_5n3v0,190Q0%0x0r0)5~5;18040c3%0+6e0+5d4l5?040@0=685y015|3J6n3E0=0U190G0G312S6x6s3*6a0-6C470W6a0q0x0;6m4P6h2r6a0d3W6g5`3R190J0I0r0,0V0x6G4l6R6T6P3v190o3H650E6(6Q196S4P6U5 6W6k2N2S6?1}6a0K6c4W6f776{5;6I196K6M71140%190X7f3F6X6Z6#6%6`6,7g190T6+6V7l046Y6!6$6d786e7r017b047d6N3c7w7h047j6O7w0h6.6:0r6=7q7M7t7v6|7x6/1_7V7C7D7F7H7J7k7N7P7L7#7S6~0%707X7#7N7u7{5;7@0)6 0*3%0657476j5^7Q7#6q6g8b8061040m0p7k6a7556777F6j6l7k8d7k6u6w6y0h6A0G8l196F8f6o7-6L7K5+7w6*7 6o7@7z7o8C046_3a798O190E0I0,317p7=696^7!8019827_848F3E738n4r7D7E7w6j0O8J3B8W3Z8Y8!8$8+6o0%6q0O1G8N3E9719338:8V8q8h632^8S8@4z8_788q198}95917y7n7B9b3*9d04999u3*0g9j1q8%8K7#8m7*9p9q7R7m7A9J8 7F7}9E4e198j8S8E8(6o9G629I8S8U3q909F9H9l8;6D8*9z889;9T2(7F739N9p9r9C8~2(9/9Y7^7`9h7M989aaa7#9)049k9|5:6o9M769O7+9Qa89g9.9V7Z9_4u9Z8k9?476E7kagai9,9X6i9{aGaw2raE9+aA6)190Ka08_7F7@8Z8#9=ae5;9WaL6-ah64669#7k8P9xaj9~9^a!8X04aX94aP6@8TaH3h8-838SaSanap7#8H7ea{1}7:a-92aYaja64la$a?9va_aZ4r068p8{8-0xa4ak3E8ub93R0=191F0*0G0o0O0@a,bx7G6J8Ib29n3Na1bqa^0^7V0ha~1}b7btau7Obca^93bm9Uab9sadat8{aJ4Wbo6fa28sbIbw9%3Zbz045(2t0Za:8L8D7kbXbMaT8`af9sbtbg2rc5bIbbbI7@bBbDbFc19L8D74c79Pc9bR0*bTbV146a0y0Dcqa22Ycu0EbUa%cx190yc4bKb8b`9A7ib#blcma#cQch7T7(7WcOaB19cAcH017N0!cwbJ7cbLcfcVc!axb$be7/c;9K8,9w9Sc_b!cWb}2Yb cTalcoc,c*c,cec=2rcgdca(cSc 7;c{a@8.a9dk9cc`3BaV19b~0Oc09#b356b;c85;8rbs8t5}bI8w046x0q2-6BbIaCbIdbdo9@04cpb4crdCcadacMbY7Yd0df6}cjbEbGdOcobN1aaodB9(8YbScFc,0q2o04010a01cBbQ6L6K9mcqbpcscDcvc(0q0I19d$7#d|19019$dS472R190ncLc.cNembhdq9}aqdhc:d(eua c}8RbIeo040.7kei8T8ed)01eHeqdQd#dicRb%d5dpeBdraq7%6;eK0O19eJeGd}0deNeC1}eQer7Ic/eOdee:6}eze_ewbu4(b08/e(e*eKd}0Ke14$0R5.5)1Q5R0R5T1H0*5Vfi2.2*282a2,0I1^fdfg5$1Nf0472Y0U0G0=0I0g0x0G0V0/191z1B1D1F0+d:1Q3r1O0N0;0+bB0+0k0+9f0x0E0+fM0+102h1v1_0Z2S0SfV1r0*1A0H0}2V0,0^f?0+0I0H370%7ofZ00fW2k0}2O163k0xe.0H0r991D001q0+1o0{991`0@0}5Y0h0,0I0*0S2w2Tf_1`1.dL1F7P1X1S040P2^0+2P120O0WgmgvgK0%7V0+0SbEf?f$f{f*fW0)00glgBf#gkgJ0=1q2!0Ogj2l2^c00+0@ge99f)0IfM0;1_0+gj0U1of#0`0*0+0*gS0#gS0E0}f*0U0e2Hf)99f?0X0+0j2lgq1`gt0qe.f*5Yf,0xf.gQ2vh8f@0}2t2wh0fW7F1h2S0V1gf?0Z19090-0s0-0Q0K09dy9.0-2PgT0Q0+e$7Vf_hpf)001h0W2Y0KgE3r2|3E1 1-1/1;5%5R5P3cfc3Jb=bQb@eOb_e{3Fb|dudwd.04ele!b6eTiedV8oaUbQead`c(dRihcUeZex7?6wicfF6Z0Z9#czhY4zdAcc1}dDeg5;i8it8Ob|0Giz0GiBbHeOisiw8)a}c(7@0|asiO8=aRd:iHe85;0,0M19030+0f0I0+0U0S2f5Z0+iRd3dviA0r0Zg^8/f~0rgM0+0e2-1`0Of,0S2H0hgvgoh,hv3@1`8j0$cldj9oincs9tc(9B9fd!esiL96e ds04d+cldxi,d=iI6}i%eUd1f 0H2v67ieigiY8Gije~ivfxc?e}i9e`i)f104h)cZi99 dWbPiijCjQeOaWeWj`i9a.c~eAjtjY9vj0bsj2iTj4iVj 19jPike7i4j^e@etj,47j+k4j-j)klevj$jGdmi(kokmjFaqk6d4k9iCjWb#keeOj=imb5dYctebbjj-kH4r1Hi2feft5T1bfg0^0`0|04.

Parcours en profondeur infixe

Compléter la méthode infixe de la classe AB. Cette méthode renvoie la liste des valeurs des nœuds rencontrés lors du parcours en profondeur infixe de l'arbre binaire représenté par l'objet en question.

Exemples

>>> vide = AB(None, None, None)
>>> ab_1 = AB(None, 1, None)
>>> ab = AB(None, 0, AB(ab_1, 2, None))
>>> vide.infixe()
[]
>>> ab.infixe()
[0, 1, 2]

Évaluations restantes : 10/10

.8709.128013:,êkn9DàSA{vBsuO8;y7e[620w]r5_pag)R1IiUN/é=mhb.4x+joPdt c(}3qlf050%0w0(0H0N0/0p0)0*0/0H0p0p0S010(0N0G010406050p0q0T0T0H0D0u040k0#0/0q140#0g0)020H0T0G0t0)0K0w1e0D0.0q0w0p050Q1b1d1f1h190G041F1M051P0Q1P1R1M190%0N0n0|0~10120U0N0I0U0/1)0U0(17050@0V0/0w1!0 11011(1*1,1*0(1=1@1:0(0V0#0%1h1;0D1N0(0U0|1k0p0G0H0g120z011_1$010:0_0w0g1s0w1:2h2j2o1{2r1@2u0T2w040b0)0$0D0#0G0#0p0N1n1p0=2f0D0D0w0*2R1F2y0g1N0Q2d2%0(2b2a2c0%2A121,0g2t2O1:1X1Z0}1`2;0N2?0g271Y1:0G2W1N2#2%381a2i1p2|2p310D1e0/170)0L2!3c183b2z3e1{3g3i3k0z3n2j3p2#2:013u0H3j040)0-3y2$193B3s123E3G0)0X3K3A3c3C3Q3k0E3U3M3W3O3D0#3h3F3k0y3#3q3d1#3t3*3v3H0v3/3N3=3P3@3,3H0s3{3%3}3)3+3R0h433r453Y040L0A4a3;2}463^0L3m1G3o3$4b4j4d0L3x4o3z4q4i3f3 3G0L3J4w3L3:3X4B170L3T4F3V4r4A474K3!4N4y4I4R4e3.4U4H3(4t3`4!3|4s4J4e424)444+4X0L494/4P3?4X0z4g4^4z4`3^0z4n384V4$4,0z4v544#4c574E5a4*4Q514M5f4:5h400z4T5k4_3~4{4Z5q4 5s514(5v4W514.5A564{4@5E5c4X0-4}3a1S361F2`2*0%2.3C0*272G0;1Y1N350w373o3U055W0=5(5r010f173s5*5g1{0B3k5@5l3t0*170P0#0w0q0%5|5/16040c3#0)6c0)5b4j5;040=0:665w015`3H6l3C0:0T170F0F2 2Q6v6q3(680+6A450V680p0w0/6k4N6f2p680d3U6e5^3P170I0H0q0*0U0w6E4j6P6R6N3t170n3F630D6$6O176Q4N6S5}6U6i2L2Q6;1{680J6a4U6d756_5/6G176I6K6 120#170W7d3D6V6X6Z6#6^6*7e170S6)6T7j046W6Y6!6b766c7p0179047b6L3a7u7f047h6M7u0g6,6.0q6:7o7K7r7t6`7v6-1@7T7A7B7D7F7H7i7L7N7J7Z7Q6|0#6~7V7Z7L7s7_5/7=0%6}0(3#0655456h5?7O7Z6o6e897~5 040l0o7i687354757D6h6j7i8b7i6s6u6w0g6y0F8j176D8d6m7+6J7I5)7u6(7}6m7=7x7m8A046@38778M170D0H0*2 7n7:676?7Y7~17807@828D3C718l4p7B7C7u6h0N8H3z8U3X8W8Y8!8)6m0#6o0N1E8L3C9517318.8T8o8f612?8Q8=4x8@768o178{938 7w7l7z993(9b04979s3(0f9h1o8#8I7Z8k7(9n9o7P7k7y9H8}7D7{9C4c178h8Q8C8$6m9E609G8Q8S3o8~9D9F9j8/6B8(9x869/9R2$7D719L9n9p9A8|2$9-9W7?7^9f7K9698a87Z9%049i9`5.6m9K749M7)9Oa69e9,9T7X9@4s9X8i9;456C7iaeag9*9V6g9_aEau2paC9)ay6%170J9~8@7D7=8X8Z9:ac5/9UaJ6+af62649Z7i8N9vah9|9?aY8V04aV92aN6=8RaF3f8+818QaQalan7Z8F7ca_1{7.a+90aWaha44ja!a;9ta@aX4p068n8_8+0wa2ai3C8sb73P0:171D0(0F0n0N0=a*bv7E6H8Gb09l3L9 boa?0?7T0ga|1{b5bras7Mbaa?91bk9Sa99qabar8_aH4Ubm6da08qbGbu9#3Xbx9A0g2r0Ya.8J8B7ibVbKaR8^ad9qbrbe2pc3bGb9bG7=bzbBbDb 9J8B72c59Nc7bP0(bRbT12680x0Ccoa02Wcs0DbSa#12ccb^9y7gbZbjckaZcKcf9P8PcdcPcIa52 b}cNajcmcu017L0Zc$cwc2bIb6cVbfcU9I8*b!bc7-c;3zaT7R7$7Uc/a`cycFc%17c)d3cHc=94c`9{aocMc_bYcQapdf7/d99tcX0Nb~9Zb154b/c65/8pbq8r5{bG8u046v0p2+6zbGaAbGd8c{c004cnb2cpdvc8c$dKdc7`dbbs4$bydEcibEdHcmbL18amdu9$8WbQcDc$0p2m04010a01czbO6J6I9kcobncqcBctd30p0H17bW7ud?17019!dl3(2P170mc,7abJcTdgd0a$deeodkdL7;cR9weq12ei040,7iec8R8cez01eBekdJc-eadWepega5eseIceeI7=7#6/eE0N17eDbGeF0deHeR4jeKel7GeneUdXc|c@a^e=eQevc?8,a7e,2peBe%eIeF0Jd{4!0Q5,5%1O5P0Q5R1F0(5Tfg2,2(26282*0H1?fbfe5!1LdY452W0T0F0:0H0f0w0F0U0-171x1z1B1D0)d*1O3p1M0M0/0)bz0)0j0)9d0w0D0)fK0)0~2f1t1@0Y2Q0RfT1p0(1y0G0{2T0*0?f;0)0H0G350#7mfX00fU2i0{2M143i0we*0G0q971B001o0)1m0_971^0=0{5W0g0*0H0(0R2u2Rf@1^1,dE1D7N1V1Q040O2?0)2N100N0VgkgtgI0#7T0)0RbCf;f!f_f(fU0%00gjgzfZgigH0:1o2Y0Ngh2j2?b~0)0=gc97f%0HfK0/1@0)gh0T1mfZ0^0(0)0(gQ0!gQ0D0{f(0T0e2Ff%97f;0W0)0i2jgo1^gr0pe*f(5Wf*0wf,gO2th6f=0{2r2ug~fU7D1f2Q0U1ef;0Y17090+0r0+0P0J09dr9,0+2NgR0P0)eY7Tf@hnf%001f0V2W0JgC3p2`3C1}1+1-1/5#5P5N3afa3Hb:bOb=eIb@f03tb`dndpd(04efe|8EeNc4dPe2dRcre5bh3(dUfvc:e{dVc?8wcY0F6X0Y9ZcxhW4xdtca1{dweO5/i6ifb_6uiafDizbFeIiqa/a{d37=0`aqiM9=dNd*iFikd.a1c$9z9ddTihetbZchbCd%eI6CdO8md,7*i;e`euiua=eTi77qitira}9u9QdjbZiwdoiQ0qiAiciej39tiZb0e1i2ew04joi=dhf}0G2t65jke/7,jveWbbe_j6d4j8e@h%c jI9}ijaS7uiU7WjKddb#cZ9ae?aoe~i!jmcJjVjsjfb~iyjiiSjIiYdEjpjQd-3C6he4d;iX17ju5af95X2%5$2%5Rfu61gVf#0q000_0)1b0:2rh52T0%0R0G0~f_f!f(1 gH5+k3iZ0Wjxjz0+fp0WcM0WjMb1i0gb1f0)8Xf~3*h5fW0/kdf*0R2F0g0@2Rg?gy0H0)0T0R2d5X6ei05$cY1Fi0h;19fe0?0^0`04.

Parcours en profondeur suffixe

Compléter la méthode suffixe de la classe AB. Cette méthode renvoie la liste des valeurs des nœuds rencontrés lors du parcours en profondeur suffixe de l'arbre binaire représenté par l'objet en question.

Exemples

>>> vide = AB(None, None, None)
>>> ab_1 = AB(None, 1, None)
>>> ab = AB(None, 0, AB(ab_1, 2, None))
>>> vide.suffixe()
[]
>>> ab.suffixe()
[1, 2, 0]

Évaluations restantes : 10/10

.8709.128013:,êLkn9DàSA{vBsuO8;y7e[620w]r5_pag)R1IiUN/é=mhb.4x+jVoPdt c(}3qlf050)0x0*0I0O0;0q0+0,0;0I0q0q0T010*0O0H010406050q0r0U0U0I0E0v040l0%0;0r160%0h0+020I0U0H0u0+0L0x1g0E0:0r0x0q050R1d1f1h1j1b0H041H1O051R0R1R1T1O1b0)0O0o0~1012140V0O0J0V0;1+0V0*19050_0W0;0x1$1113011*1,1.1,0*1@1_1=0*0W0%0)1j1?0E1P0*0V0~1m0q0H0I0h140A011{1(010=0{0x0h1u0x1=2j2l2q1}2t1_2w0U2y040b0+0(0E0%0H0%0q0O1p1r0@2h0E0E0x0,2T1H2A0h1P0R2f2)0*2d2c2e0)2C141.0h2v2Q1=1Z1#0 1|2?0O2^0h291!1=0H2Y1P2%2)3a1c2k1r2~2r330E1g0;190+0M2$3e1a3d2B3g1}3i3k3m0A3p2l3r2%2=013w0I3l040+0/3A2(1b3D3u143G3I0+0Y3M3C3e3E3S3m0F3W3O3Y3Q3F0%3j3H3m0z3%3s3f1%3v3,3x3J0w3;3P3@3R3_3.3J0t3}3)3 3+3-3T0i453t473!040M0B4c3?2 483`0M3o1I3q3(4d4l4f0M3z4q3B4s4k3h413I0M3L4y3N3=3Z4D190M3V4H3X4t4C494M3$4P4A4K4T4g3:4W4J3*4v3|4$3~4u4L4g444+464-4Z0M4b4;4R3^4Z0A4i4`4B4|3`0A4p3a4X4(4.0A4x564%4e594G5c4,4S534O5h4=5j420A4V5m4{404}4#5s515u534*5x4Y534:5C584}4_5G5e4Z0/4 3c1U381H2|2,0)2:3E0,292I0?1!1P370x393q3W055Y0@5*5t010g193u5,5i1}0C3m5_5n3v0,190Q0%0x0r0)5~5;18040c3%0+6e0+5d4l5?040@0=685y015|3J6n3E0=0U190G0G312S6x6s3*6a0-6C470W6a0q0x0;6m4P6h2r6a0d3W6g5`3R190J0I0r0,0V0x6G4l6R6T6P3v190o3H650E6(6Q196S4P6U5 6W6k2N2S6?1}6a0K6c4W6f776{5;6I196K6M71140%190X7f3F6X6Z6#6%6`6,7g190T6+6V7l046Y6!6$6d786e7r017b047d6N3c7w7h047j6O7w0h6.6:0r6=7q7M7t7v6|7x6/1_7V7C7D7F7H7J7k7N7P7L7#7S6~0%707X7#7N7u7{5;7@0)6 0*3%0657476j5^7Q7#6q6g8b8061040m0p7k6a7556777F6j6l7k8d7k6u6w6y0h6A0G8l196F8f6o7-6L7K5+7w6*7 6o7@7z7o8C046_3a798O190E0I0,317p7=696^7!8019827_848F3E738n4r7D7E7w6j0O8J3B8W3Z8Y8!8$8+6o0%6q0O1G8N3E9719338:8V8q8h632^8S8@4z8_788q198}95917y7n7B9b3*9d04999u3*0g9j1q8%8K7#8m7*9p9q7R7m7A9J8 7F7}9E4e198j8S8E8(6o9G629I8S8U3q909F9H9l8;6D8*9z889;9T2(7F739N9p9r9C8~2(9/9Y7^7`9h7M989aaa7#9)049k9|5:6o9M769O7+9Qa89g9.9V7Z9_4u9Z8k9?476E7kagai9,9X6i9{aGaw2raE9+aA6)190Ka08_7F7@8Z8#9=ae5;9WaL6-ah64669#7k8P9xaj9~9^a!8X04aX94aP6@8TaH3h8-838SaSanap7#8H7ea{1}7:a-92aYaja64la$a?9va_aZ4r068p8{8-0xa4ak3E8ub93R0=191F0*0G0o0O0@a,bx7G6J8Ib29n3Na1bqa^0^7V0ha~1}b7btau7Obca^93bm9Uab9sadat8{aJ4Wbo6fa28sbIbw9%3Zbz7I0r0=2t0Za:8L8D7kbXbMaT8`af9sbtbg2rc6bIbbbI7@bBbDbFc29L8D74c89PcabR0*bTbV146a0y0Dcra22Ycv0EbUa%14cfb`9A7ib#blcna#cNci9R8RcgcScLa71db 0Oc19#b3bjcM040!cxbJ7cbLcWb!cTb$be7/cX9K8,arc`c?cYaxb}c#c%bI6Ec)b-7|19c-cI01czc5bKb8d12rchdja(cPc 7;c|a@7%6;8ScBb:bpctb@dm14b_dr6t6v046x0q2-6Bd6c4bIcKdE9@04cqb4cs5;8|cc7,dhbY7Yd0dQa7ckbEbGdM040-dT8oaocd1}6jcEcwdd0q2o04010a01cCbQ6L6K9mcrdydW8YbScGc.0q0I19d#7#d|19019$d(4l2R190ndgc:diendkc{3BaVbda`dB01dleva(8Q9yeCep040.7kej8T8eeJ0Oeqes7Ic;eCeEeyaqdoc=dqeZ7?7T7(7WeR19eMbIeO0deQeF14eKerdOd!dpcOb%cQ96ex9}aq8.a9e@01eKe/eJd}0Ke14$0R5.5)1Q5R0R5T1H0*5Vfn2.2*282a2,0I1^fifl5$1Nbu3*2Y0U0G0=0I0g0x0G0V0/191z1B1D1F0+bN2)1X1S040N0;0+bB0+0k0+9f0x0E0+fR0+102h1v1_0Z2S0Sf#1r0*1A0H0}2V0,0^f|0+0I0H370%7of)00f$2k0}2O163k0xe=0H0r991D001q0+1o0{991`0@0}5Y0h0,0I0*0S2w2Tf 1`1.dJ1F7PfW1O0P2^0+2P120O0WgsgBgP0%7V0+0SbEf|f,g1f:f$0)00grgHf+gqgO0=1q2!0Ogp2l2^c10+0@gk99f/0IfR0;1_0+gp0U1of+0`0*0+0*gX0#gX0E0}f:0U0e2Hf/99f|0X0+0j2lgw1`gz0qe=f:5Yf=0xf@gV2vhdf}0}2t2wh5f$7F1h2S0V1gf|0Z19090-0s0-0Q0K09d88 0-2PgY0Q0+dt7Vf huf/001h0W2Y0KgK3r2|3E1 1-1/1;5%5R5P3cfh3Jb=bQdAf7dDe(80b|c!c0f08=dNeCdPiealaRfUb;b5e9cud`c*6He|e$b#0Gihc$fK6Z0Z9#cAh%3Nisd?148rbs8t5}cib|iCb~ii0GiGbHimizeC8Mixd20|asioikdSirbP7#0,0M19030+0f0I0+0U0S2f5Z0+iVd4iF0r0Zg}8/g40rgR0+0e2-1`0Of=0S2H0hgBguh;hA3@1`8j0$cme%bOaUbQ9tdd9B9fc.inf3dad%i-4(bAdJcld,i%cpi:d=dZetehcRjHjFc}e#eXf2fCa7eHijc+jvj$d2j3iXiZd-emjIa7i+b2e7i9b6i$f7eYjXa@jZj~j#ezc~iAc@j.iEiYj6i!f77@j^d-iK1ad=iN7xkgj!jWj,a 04g50H2v67j;eU7.k7eCaWe e}c@h.e,f79 dUe89(eacFcHi)krkn4r1Hi7fjfy5TfB63g$f-0r000{0+iDhc2V0)0S0H10g1f,f:21gO5-5Z04i+0Xktkv0-fw0XcP0XkGb3i7gj1h0+8Zg63,hcf(0;k(jijk0_2Tg}fSi~j0gv6gi75(iikUk{h60rlsk{31lvfgk{h{1bfl0^0`0|04.

Compléments

Il est à noter qu'ici, il n'est pas possible de stocker None en tant que valeur dans un arbre binaire implémenté de cette façon. En effet, si l'argument valeur est None, l'instance interne de Noeud n'est jamais créée. Ce n'est généralement pas gênant, car il rare d'avoir besoin de stocker None en plus d'autres types de données dans le même arbre binaire, mais il peut être intéressant de garder ce détail à l'esprit.

Il est également possible de déclarer la classe Noeud à l'intérieur de la classe AB, de manière à ne pas l'exposer à l'utilisateur. Elle est alors un attribut de classe, qui peut être accédé depuis une instance avec self.Noeud (Nota: le comportement des attributs de classes vs instances a un fonctionnement particulier à python).
Dans ce cas, l'implantation de la méthode __init__ devient :

class AB:

    class Noeud:
        def __init__(self, gauche, valeur, droit):
            self.valeur = valeur
            self.gauche = None
            self.droit = None

    def __init__(self, gauche, racine, droit):
        if racine is not None:
            if gauche is None:
                gauche = AB(None, None, None)
            if droit is None:
                droit = AB(None, None, None)
            racine = self.Noeud(gauche, racine, droit)
        self.racine = racine