Autour des arbres binaires (1)

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 vides par une instance de la classe ABVide, ne possédant aucun attribut.

On représente quant à eux les arbres binaires non vides par une classe AB caractérisée par trois attributs :

  • valeur est à la valeur portée par la racine ;
  • gauche est un objet de type AB ou ABVide, et représente le sous-arbre gauche de l'arbre ;
  • droit est un objet de type AB ou ABVide, et représente le sous-arbre droit de l'arbre.
Les classes ABVide et AB 
class ABVide:
    def __init__(self):
        pass  # le constructeur n'effectue aucune action

    def est_vide(self):
        return True

    def __str__(self):
        return "∅"

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

    def est_vide(self):
        return False

    def __str__(self):
        return f"({self.gauche}, {self.valeur}, {self.droit})"
Créer un arbre binaire

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

Utiliser ces classes afin de représenter les deux arbres binaires ci-dessous (par commodité, on ne représente pas les arbres vides) :

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

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

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

.1280135tf4)2r3,sBao iug0V8m1P6pnl7he=cyv9A(S/b_dk050Q0E0c0m0p0B0k0o0G0B0m0k0k0F010c0p0z010406050k0q0v0v0m0h0H040M0n0B0q0,0n0A050N0?0^0`0|0;0z04151c051f0N1f1h1c0;0Q0p0I0!0$0(0*0D0p0r0D0B1v0D0c0/050V0O0B0E1q0%0)011u1w1y1w0c1E1G1C0c0O0n0Q0|1D0h1d0c0D0!0 0k0z0m0A0*0g011I1s010d0X0E0A0m0v0E1C1*1,1;1K1@1G1`1|0/0a0o0x0h0n0z0n0k0p120A0o0T1(0h0h0E0G2h151 0A1d0N1$2u0c1!1Z1#0Q210*1y0A1_2e1C1n1p0#1J2E0p2G0A1W1o1C0z2n1d2s2u2Y0=1+2i2M1=2R0h0_0B0/0o0w2r2$0:2#202(1K2*2,2.0g2;1,2?2s2D012{0m2-040o0i2 2t0;322_0*35370o0e3b312$333h2.0b3l3d3n3f340n2+362.0y3s2@2%1r2`3x2|380C3C3e3F3g3H3z380u3L3u3N3w3y3i0J3T2^3V3p040w0s3!3E2N3W3I0w2:162=3t3#3-3%0w2~3=303@3,2)3P370w3a3}3c3D3o420/0w3k462u2V0E2u2K2x0Q2B330G1W1}1d4j1g2W3D2Z2=054o0T2X3U3_0/0m0O0P452Y0o483v0n0/0F3l4K3M4D040K0l3l4L3V0.040L4X4S1=0v0p0/4I4x4(1K4!0j4Q4Y4T4V0t0p0T4%4C1=4!0L0f4=4e4R4~2`0/4_4{0E4}3^4 0/510f3+3o4E4G3;4J4@1=4N044P545o574U4W4e5u0*505c401K4*4b5C334;4?4/3g5k4H5H3v5J5t5L34580l4`4|5y5T500f5h4e3 5j044F0P4d5n5T5q5s5/565M5w5P4Z5f5`3-5F045.4.5@015R5?5d5v595Y2!5!5f525K630A5V5X5b5Z635#5%2Y5)3v6h5+4G3r5S635;6f675^4V5}5e4#6D5E4+046v6b6m0/53665D6B5W5a6G5A6d6O2=556A5U5w6j6U646d6o3?5z6#5,3|6P336y6w6!6s6C6l6!5B6{6Q015 6:626|6N6z6 6s5,61306-656Y6-786u6(4!6+3~7f5N2P0c766=4O7q6r5V7i5|6~335 3*7y5Q756@775N5m736 7d306Z7G6t0P727b6c047k3c6q3$5N0D7t3V6?6;7u5_7C5{6F7+3-0k1/041L017w046X7M7m6$6T7.6E517`2t7N5*696k6L744#5$5i7)5,0R7#3-7%7e5T6_5x887K7x8n337:0/010R7@7 4:7E7(7Y7}6a7J5I6W8g2)6i7~8q7D8a7V3m6^5N878j6x7s7F858m8E8M4$8x0*8s7=1}7^82387|5,7!8$6)7_8H686S8D7S6M8N8c8B5,0d8@0*8i7{8k7v8;6}8L3V8(1?8w9a3-7L837|867^81926.4G8f980/8O7X4T5,0O9n949i967*9f806(9c0O9e8Z7,8,847)9k9r8a9L8.4G8S8{899t9S0P0G9y8V8A4^8Y9V8o7-9D1K9c0G9I9*8F8?8W8d4G919P9R9B9O9-6V8}5(9Y0k2y9#5r9n8l9l9F7;010m9;2t7c8z8T8Q7P9x9|a95N9!9P9X0N4z4h1e4u0N4s2v4l152y2x1V1X2x4F1G4i1o2?az0U0W0Y04.
Taille

Compléter les méthodes taille des deux classes ABVide et AB. Ces deux méthodes renvoient la taille de l'arbre binaire représenté par l'objet en question.

Exemples 
>>> vide = ABVide()
>>> trois = AB(3, ABVide(), ABVide())
>>> deux = AB(2, trois, ABVide())
>>> un = AB(1, ABVide(), ABVide())
>>> ab = AB(0, un, deux)
>>> vide.taille()
0
>>> ab.taille()
4

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

.128013.87095tf4{)}+2rFT3,sBao iug0V8m1P6pnl7h.e=cy:v9A(wS/b_dk050Z0L0d0s0v0H0q0u0N0H0s0q0q0M010d0v0F010406050q0w0B0B0s0l0O040V0t0H0w0^0t0G050W0 1113150}0F041e1l051o0W1o1q1l0}0Z0v0Q0-0/0;0?0J0v0x0J0H1E0J0d0{050(0X0H0L1z0:0=011D1F1H1F0d1N1P1L0d0X0t0Z151M0l1m0d0J0-180q0F0s0G0?0k011R1B010e0*0L0G0s0B0L1L1?1^1}1T201P23250{0a0u0D0l0t0F0t0q0v1b0G0u0$1;0l0l0L0N2q1e280G1m0W1/2D0d1-1,1.0Z2a0?1H0G222n1L1w1y0.1S2N0v2P0G1)1x1L0F2w1m2B2D2+0~1@2r2V1~2!0l120H0{0u0C2A2/0|2.292;1T2?2^2`0k2}1^2 2B2M01340s2_040u0o382C0}3b320?3e3g0u0f3k3a2/3c3q2`0c3u3m3w3o3d0t2@3f2`0E3B302:1A333G353h0I3L3n3O3p3Q3I3h0A3U3D3W3F3H3r0R3$313(3y040C0y3-3N2W3)3R0C2|1f2~3C3.3_3:0C373~39403^2=3Y3g0C3j463l3M3x4b0{0C3t4f3v414a3*4k3A4n484i4r3;3K4u4h3E433T4A3V424j3;3#4F3%4H4x0C3,4L4p3P4x0k3?4R494T3R0k3}2+4v4C4I0k454%4B3/4*4e4-4G4q4!4m4=4M4@3Z0k4t4`4S3X4U4z504Y524!4E554w4!4K2-1r2)1e2T2G0Z2K3c0N1)261m5i1p5g5e2-5n0$2*4{1T0!0{323u4.3_0U2`5E4?330N0{0S0r0z0v0$5J5z0?0`040P3B0u5!0u5F1~5B040$0e5T51015H3h5-561 0B0{0Y0Y2Y2p5`5=3c5W0T5 3E0X5W0q0L0H5,4n5%1T5W0h5Y4u5#6i5$5K0?5)1@0;3u5!6c0?0N0C0{030u1P1;0G0q2H0w2y0L0w0l0u0G000L0e0e2x0d0w1Q0s6E0w2P0u0s2y0v1c3B066i6s015)5+633(5:5$6b6l3d0e0{0L6C0Y0Q5R0L6-3_616 1~650{6769726d0{6f5Z6j6r6=5)2w6Q0l1d4n6k5U6*5M040n0l6R6$6(7f0{6,6;7n6/783p6@040(0*1P7C01717z5.7404766a2-6=6e6g4%7d7e7n7g0%6H7k2+7m5.0B0v0{4W4%6%5#6)6+6M7J7B7M5?0e5^045`6C0l5~7`600{62836466687R2~6)7U7c7d7=0{7h7$6q6)0q1{04010b016$4(3(5)5D876.5I8y427p5O7J5W7V3 7v7Z7x7@8B1~7_7S7n7|5_5{0G5}0Y8F857J7O7Q8Y040p8l6=0G0{0Q3f6G0l8%8)7l6)8,040x6T0N0J6~8N798(8*7n8_0Z2k2p8%7b6h7X6)8#8a7J0t0{0K7J8_8.1P6H935.9h040M9p5?9l8/9o9b8g6=9e77900?9r9j9E3d0{8{6E8~9u3c9r9t8@8+9K8|9N9z6j9d899D8Q9q9i9k7x970d9O3E9Q9-3/9*0t984u7:7Y5.7?8b396)8P8c8+7E6_0d6{6}8%869$5?9C9}2C8d7a8H477X7)5?7!7i7%2~ak3c0!7p0m3f677u7;7w5*8Maa3ca09~a20{7G0H7I9I7LaC88759faLag8f9Yaz8j7j9:3_7+4kaY1~9r0ja$1Tac9g9(9I8_9L8}8 aN3(9G9)7F0)aJa?a17n610ha*9F0{a)9S7na,9Ia_a/9=9@a@3_bbbf2=aHa|aKbi910Tb29^8J9{8Lad5y5.aEae6=8S7~0Y8082bn5V8Z9Ib9bG7KaS9Xbsal8i7#aXb75.0q0s0{bv8m8o01a9a bV7,040g8!9!bZ6=bhb(9v9U9Ma~aF7n2o0{0i7J8n0{0p6:bLb|b+b-aP9#b=9Pa.bL9w9n8;9Ic5b~ch8oc2b b*b,bJb.a-049Hcdbd9,chb*cjc48o0h8s4A0W5w0L2D2(cI5h1x5j2G2I2E1(1*2G0s1OcL0W5i0}cY0%a|0q04.
Hauteur

Compléter les méthodes hauteur des deux classes ABVide et AB. Ces deux méthodes renvoient la hauteur de l'arbre binaire représenté par l'objet en question.

Exemples 
>>> vide = ABVide()
>>> trois = AB(3, ABVide(), ABVide())
>>> deux = AB(2, trois, ABVide())
>>> un = AB(1, ABVide(), ABVide())
>>> ab = AB(0, un, deux)
>>> vide.hauteur()
0
>>> ab.hauteur()
3

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

.128013.87095tf4{)}+2rFT3,sBao iug0Vx8m1P6pnl7h.e=cy:v9A(wS/b_dk050!0M0d0s0v0I0q0u0O0I0s0q0q0N010d0v0G010406050q0w0C0C0s0l0P040W0t0I0w0_0t0H050X101214160~0G041f1m051p0X1p1r1m0~0!0v0R0.0:0=0@0K0v0x0K0I1F0K0d0|050)0Y0I0M1A0;0?011E1G1I1G0d1O1Q1M0d0Y0t0!161N0l1n0d0K0.190q0G0s0H0@0k011S1C010e0+0M0H0s0C0M1M1@1_1~1U211Q24260|0a0u0E0l0t0G0t0q0v1c0H0u0%1=0l0l0M0O2r1f290H1n0X1:2E0d1.1-1/0!2b0@1I0H232o1M1x1z0/1T2O0v2Q0H1*1y1M0G2x1n2C2E2,0 1^2s2W1 2#0l130I0|0u0D2B2:0}2/2a2=1U2@2_2{0k2~1_302C2N01350s2`040u0o392D0~3c330@3f3h0u0f3l3b2:3d3r2{0c3v3n3x3p3e0t2^3g2{0F3C312;1B343H363i0J3M3o3P3q3R3J3i0B3V3E3X3G3I3s0S3%323)3z040D0y3.3O2X3*3S0D2}1g2 3D3/3`3;0D383 3a413_2?3Z3h0D3k473m3N3y4c0|0D3u4g3w424b3+4l3B4o494j4s3=3L4v4i3F443U4B3W434k3=3$4G3(4I4y0D3-4M4q3Q4y0k3@4S4a4U3S0k3~2,4w4D4J0k464(4C3:4+4f4.4H4r4#4n4?4N4^3!0k4u4{4T3Y4V4A514Z534#4F564x4#4L2.1s2*1f2U2H0!2L3d0O1*271n5j1q5h5f2.5o0%2+4|1U0#0|333v4/3`0V2{5F4@340O0|0T0r0z0v0%5K5A0@0{040Q3C0u5#0u5G1 5C040%0e5U52015I3i5.57200C0|0Z0Z2Z2q5{5?3d5X0U603F0Y5X0q0M0I5-4o5(1U5X0h5Z4v5$6j5%5L0@5*1^0=3v5#6d0@0O0D0|030u1Q1=0H0q2I0w2z0M0w0l0u0H000M0e0e2y0d0w1R0s6F0w2Q0u0s2z0v1d3C066j6t015*5,643)5;5%6c6m3e0e0|0M6D0Z0R5S0M6.3`62701 660|686a736e0|6g5!6k6s6?5*2x6R0l1e4o6l5V6+5N040n0l6S6%6)7g0|6-6=7o6:793q6^040K6U0d6H0l7D01727A5/7504776b2.6?6f6h4(7e7f7o7h0(6I7l2,7n5/0C0v0|4X4(6(5$6*6,6N7M7C7P5@0e5_045{6D0l5 7}610|63866567697U2 6*7X7d7e7^0|7i7)6r6*0q1|04010b016%4)3)5*5E8a6/5J8B437q5P7M5X7Y407w7$7y7`8E1 7|7V7o7 5`5|0H5~0Z8I887M7R7T8#040p8o6?0H0|0R3g7K8*8,7m6*8/040x6U0O0K6 8Q7a8+8-7o8{0!2l2q8*7c6i7!6*8(8d7M0t0|0L7M8{8;1Q6I955/9j040N9r5@9n8=9q9d8j6?9g78920@9t9l9G3e0|8}6F909w3d9t9v8_8.9M8~9P9B6k9f8c9F8T9s9k9m7y990d9Q3F9S9/3:9,0t9a4v7?7#5/7_8e3a6*8S8f8.7F6`0d6|6~8*899(5@9E9 2D8g7b8K487!7,5@7%7j7*2 am3d0#7q0m3g687v7@7x5+8Pac3da2a0a40|7H1b8?9K7OaE8b769haNai8i9!aB8m7k9=3`7.4la!1 9t0ja(340Y0|130Aaa8%9$af5z9)049JaP9?8|9X91a}3`9I9+7G7IaMb21 620h8^7+9#aR9%a37ob49K979-9i9*blaJb79Ab9930U0h0haz9|an8Oa^a18Dbu0@8V810Z8385bG7N8$9Kae9baj3mal8k04aYaq3aas3F0q0s0|bD6?8q0|01abbi5/2p0|0ga?bgb*bjbpbN8{9N8 b1b:5@b=040i7Mb,8+6;bNc4b@bQa@boa{b59ob8c23dc4c69Kc80pcaclb$7/04cdbNbR9Kbkb}9@9_cbcvcocb8r0h8v4B0X5x0M2E2)cP5i1y5k2H2J2F1)1+2H0s1PcS0X5j0~c)0(0*0,04.
Parcours en largeur

Compléter les méthodes largeur des deux classes ABVide et AB. Ces deux méthodes renvoient 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 = ABVide()
>>> vide = ABVide()
>>> trois = AB(3, ABVide(), ABVide())
>>> deux = AB(2, trois, ABVide())
>>> un = AB(1, ABVide(), ABVide())
>>> ab = AB(0, un, deux)
>>> vide.largeur()
[]
>>> ab.largeur()
[0, 1, 2, 3]

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

.128013.87095[4})2FR,Ba iVèà8m16l7.e:9A;S/dktf{I«rjT3sogu0]PpOn»h=céyv(wq_b050G0z0I0m0o0w0R0n0(0w0m0R0R0%010I0o0Y010406050R0U0t0t0m0N0*040E0S0w0U140S0!0n020m0t0Y0D0n0j0z1e0N0.0U0z0R050F1b1d1f1h190Y041F1M051P0F1P1R1M190G0o0+0|0~10120$0o0T0$0w1)0$0I17050@0:0w0z1!0 11011(1*1,1*0I1=1@1:0I0:0S0G1h1;0N1N0I0$0|1k0R0Y0m0!120h011_1$010J0_0z0!1s0z1:2h2j2o1{2r1@2u0t2w040a0n0X0N0S0Y0S0R0o1n1p0=2f0N0N0z0(2R1F2y0!1N0F2d2%0I2b2a2c0G2A121,0!2t2O1:1X1Z0}1`2;0o2?0!271Y1:0Y2W1N2#2%381a2i1p2|2p310N1e0w170n0u2!3c183b2z3e1{3g3i3k0h3n2j3p2#2:013u0m3j040n0Q3y2$193B3s123E3G0n0e3K3A3c3C3Q3k0c3U3M3W3O3D0S3h3F3k0v3#3q3d1#3t3*3v3H0x3/3N3=3P3@3,3H0s3{3%3}3)3+3R0B433r453Y040u0V4a3;2}463^0u3m1G3o3$4b4j4d0u3x4o3z4q4i3f3 3G0u3J4w3L3:3X4B170u3T4F3V4r4A474K3!4N4y4I4R4e3.4U4H3(4t3`4!3|4s4J4e424)444+4X0u494/4P3?4X0h4g4^4z4`3^0h4n384V4$4,0h4v544#4c574E5a4*4Q514M5f4:5h400h4T5k4_3~4{4Z5q4 5s514(5v4W514.5A564{4@5E5c4X0Q4}5I4;3^0Q534p5b5O400Q595S5g505V5e5Y5l5!3G0Q5j5%5r4k5V5p5-5w5/5*5u5=5B5V5z5`5F5P5D3o1O361F2`2*0G2.3C0(272G0;1Y1N350z37624N056b0=6j5.0H173s3U5T2p0-3k6u5Z3P0(170C0l0p0o0=6z5(1216040A3#0n6Q0n6v1{6r040=0J6J5.6x3H6Z5?0J0t170/0/2 2Q6,6%3C6M0,6;3(0:6M0R0z0w6Y6l6A016M0g6O4U6R776S716V2i103U6Q6T120(0u17030n1@2f0!0R2+0U2Y0z0U0N0n0!000z0J0J2X0I1C0n0m7s0U2?7G2Y0o1o3#06777g016V6X6^456#6S706K3D0J171D0I0/0+6H0z7W4j6?7/2p6`176|6~7=1{737554786R7S6V2W7E0N0!7e826C040P0N1C7P7R7a177V7!6!6y8k5?0!7%040~0N0T7u0N7{6L176@8n3C7@047_6 3a717}6P80797#830?7v874N8M5.6M0d0W8f818h6W7A8x017Y8%6)6+0/7q0N6:8B3(7;8;458D8F8%8J768L8217848Q88710R2m04010b017P55456V6t8@4j8)9g3f8a6E8{177~4p8g8N8i8$9j1{9i8H7#8+046,6.7*0/9n048A9y5.8_6}8G628I170k937#0!170+3F8v9G9R8S7S9U040T7H0(0$7.9v8y049!388T8o8i2L2Q9G748K807S9L7`9.010S170y8%9%9W1@7v9S5.a4040%ac9@04a99Y8}9~71a09N3z7Saea6a29%9)7s9,ah3Caeag9#71aw9*azam789 6{9M8%ata79^0S9`aE7#aCaA4$aRaT547Q8Z9s8#aq2$7S9x9O9T8q7)7+7-9G9Ia.9KaMa19J5?8|7 8~8!9186aX9d8a0i3F6|8Y7f8!8ja}3Ca-araF8q8s8uaba28?bf6_a{a*6pa~179|aJ9r5.9%2W1b0w0@0Ib54jaWaU8U170d8%apaOa5aQaj9Xbnbq456M8Xbya%bA172C9-9=as17aDb*aF170i2sa@0g9}aKb/04b(bQ04aubW4s7(8pb=bo8zbObsb}b a_aiax9+b)cb6=bwb^bzaib|a2aPavc2cmc02pbpcgbr7^aNcnbRcp6W9_bGc504b@b!bca(0-1(1@bH2p0S6#31cEb.9Tb%c4cs1{cocY3P7(7qa=6IcF0,bxb08Lb#ai0mcOcZb,c?c$b{cXcv45c!c}c1a)c|bi7#6?cHc.c/9?3C6V0obtda3(cQ17cSc_3D17c=czb~bSa;7,c*c#728zc-9qd9ancV04bC0UbE0mcTd0cPcAdu9%0m0Y0Y2t0Ga@bSdnduc d4b$bTaa8wcFd7dydzck3XcWcNdocadXai2tcrdI7|c6cBdUd@12dWa+b`cdaIdu73cjd)9$d,cfd:aBdKd|dl04d=d3d d5d_dLdmc9bS0GcD9{e5cJ6q908Pb4bKaidDdFdH4xa$et5?7U9udubhei5.9A6,8.8:e3ekedbPd$9p4xc/8 dCew8RcU5.0R0mb%8%951701a^ea3(2P170Kc7cxa|edd~bud+9(aHe9eL5?e?040fe,960k7Zduf5e^a2eUdVece;4c9VbUd#fc0o17f7a2e-9:fbedfde_8EcyfhdpcBepaSeCf33Cf5frfc960g9a4!0F6n6i63fS0F661F0I68fX2,2(26282*0m1?fU661Le~3(2W0t0/0J0m0H0z0/0$0Q171x1z1B1D0neWa+1S3p1M0L0w0n7)0n0)9)1@2F0!0I0n2N100of+0n2T0M0n2+0^0I0z7w0#0|0$0mg10nak7v0n0O0U7q1^dN0N0q0{7n0G0)b(gh0Ifaf*0S1m0o102jgj0r0|0?gv0n0R1kgY1ogkgX7w0~0n0t0)2d6c6SfR8r1fbmd#g}gp1^g?3s1^6m6c049mfQh9g31O3p2`3C1}1+1-1/6g643a6lh2c:db9tbta,8mdLbkg aleR9Hfy8`eVesdffke!bDbFdkbJe%bv048WhHe7c{d-hPebafdk9%b;hWedd6hTb`d?fjbIfifHaYefc3h%h-cteSh^1{fgh(cicIhI4j6VcLeh6$71dh04djeye h,h:c~h/f/hJdra?c+dxeXe6b`d{3zi1dJhZibh;idihh.fCeld2h@ie7:dwhHd*h;eAhMd.dTdOdQdSd`encBgEfnh~cGiHhs3(6V0J3*h!cqg#hN6#2 dkcuh{c`iqiEitd/i?3t17e1f2iyh_9:i(04i=i~c@iAed9%fEa!iWim3Ld)b_a(ddi+di0SfGi6dBd=i*iMcBijdtiWc,g418jeeYh+i5b+j6i:eeegiDj49/e:i_c`jogieri0eZb3e$3oisi`hKdEiL5ahc6ofT2%f-1Q040Z0Ugb0!6b2Wfae)7p7m0m0n267s7nh82T3(hj1 1.2xa(i$iVarj#6iheg61W1Yhi1-k2hm1Qho6k3ahreFhta)8%eKjI7$17blhBjuhEfAjbjweEjfdYiKdGhNc^ivbXbMbZd8iIhJixjVd}kJhXh;h$i}7Sh)jQjAjHjCi^kt9%jGkY9PhDffc8d$h*cKcMi}kSa3cRjkj1ixk(dqc(dsk-ej9HjcjxiodBj3k`hOjUhUk i7ighU6XjBk.c,iYkoiJ1DjYkHjqiBdNdP0!dRc+dTiSiBiUjPkOb1jgdeask|jlk`dMlCj7i{f1lPjEk+l2ikhCjvlokEclllaVlib`k,iQlvlTjLeei|lFd(d9eZjhkKbIlLj1j3l0fDeqlulQeflWjtjEd6kCjyiZkQl%adl)jnh?l4bLk/l-m2lUaZjlkZh lGlp9dev85jTirhUkGjl19k92%6hj(6fmC0=0@0_0R04.
Parcours en profondeur préfixe

Compléter les méthodes prefixe des deux classes ABVide et AB. Ces deux méthodes renvoient 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 = ABVide()
>>> vide = ABVide()
>>> trois = AB(3, ABVide(), ABVide())
>>> deux = AB(2, trois, ABVide())
>>> un = AB(1, ABVide(), ABVide())
>>> ab = AB(0, un, deux)
>>> vide.prefixe()
[]
>>> ab.prefixe()
[0, 1, 2, 3]

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

.128013.87095[4})2FR,Ba iVà8m16l7.e:9A;US/dktf{+IrjT3sogu0x]PpONnh=céyvêD(wq_b050G0y0I0m0o0v0R0n0)0v0m0R0R0(010I0o0Z010406050R0U0s0s0m0N0+040E0S0v0U170S0$0n020m0s0Z0C0n0j0y1h0N0;0U0y0R050F1e1g1i1k1c0Z041I1P051S0F1S1U1P1c0G0o0,0 1113150%0o0T0%0v1,0%0I1a050`0?0v0y1%1214011+1-1/1-0I1^1`1?0I0?0S0G1k1@0N1Q0I0%0 1n0R0Z0m0$150h011|1)010J0|0y0$1v0y1?2k2m2r1~2u1`2x0s2z040a0n0Y0N0S0Z0S0R0o1q1s0^2i0N0N0y0)2U1I2B0$1Q0F2g2*0I2e2d2f0G2D151/0$2w2R1?1!1$101}2@0o2_0$2a1#1?0Z2Z1Q2(2*3b1d2l1s2 2s340N1h0v1a0n0t2%3f1b3e2C3h1~3j3l3n0h3q2m3s2(2?013x0m3m040n0Q3B2)1c3E3v153H3J0n0e3N3D3f3F3T3n0c3X3P3Z3R3G0S3k3I3n0u3(3t3g1(3w3-3y3K0w3=3Q3^3S3`3/3K0r3~3*403,3.3U0A463u483#040t0V4d3@30493{0t3p1J3r3)4e4m4g0t3A4r3C4t4l3i423J0t3M4z3O3?3!4E1a0t3W4I3Y4u4D4a4N3%4Q4B4L4U4h3;4X4K3+4w3}4%3 4v4M4h454,474.4!0t4c4=4S3_4!0h4j4{4C4}3{0h4q3b4Y4)4/0h4y574(4f5a4H5d4-4T544P5i4?5k430h4W5n4|414~4$5t525v544+5y4Z544;3d1V391I2}2-0G2;3F0)2a2J0@1#1Q380y3a3r3X055Q0^5Y5u010H1a3v5!5j1~0:3n5.5o3w0)1a0B0l0p0o0^5?5)19040z3(0n660n5e4m5+040^0J605z015;3K6f3F0J0s1a0=0=322T6p6k3+620/6u480?620R0y0v6e4Q692s620g644X676N685/156b2l133X666H1~0)0t1a030n1`2i0$0R2.0U2#0y0U0N0n0$000y0J0J2!0I1F0n0m6-0U2_6~2#0o1r3(066N6X6R1a6d6y4m6i686G6Q3G0J1a1G0I0=0,5~0y7e6I1a6x7i5@156A1a6C6E7t1~6J6L576O677a5*1a2Z6|0N0$6V7L0H5_040P0N1F77797j6b7d7x5)7g7E3S7l045W2u0W7s7)6g6w7,017A047C6F3d7j7G657J6P7y7M047O6:7R4Q85611a0d0X7!7K7$7c6^7`7+7@6l6n046p6+0N6t8p6v7v7`7|7~7`826M847T7N0_8a7S7j0R2p04010b017758486b5-8x488o80860$7V5{8D1a7H4s7#867%8m8Y7f5=8=2s6m6o6q0$6s0=8*047w8#5)8B6D7 5Z811a0k8L8$1a0,3I6/0N909b8c7L0$1a0T6 0)0%7?937^9a9c5)9n6c2O2T906K837J7L957D8^1~0S1a0x7`9z9f1`6:9x6g9M040(9U3!9e9g9T8F9G7j9I973C7L9W9O9K3S9o9q9s9Z3+9W9Y9l7j9z9p6-9^9(6O9H6B967`9/9P7c9B0I9_489{ae4vab0S9C4X788j8/8l9,2)7L8!988$7.7n7p7r9092av94a69J9u3F8E7I8G8k888J7Qah2s7U1a0i3I6C8i6WaM7(aH3+au9-9~7.7:0o7=aB8AaFar5(9v049Ea38.5)6b89aP9}86620da/7Ba79;01a9b69Q9$9ib6628ha 5)9W0LaQ1~9+a89Naa04a09r9taD9Vbob91aa+a-bd7v0gbk15bibE7{a:bn049:a#4fajalbN4mb8bR3iby2Z7;bta(b0bCaX8d6g8:a;at8@bU2E8r8t2.8wb.157_b6bmbBa@8,4A84b(3Fa|aO8b3bc13+0R0m1ab+8M8O01aCb!5)2S1a0Kb37}b5b@b7bwcp9 9@bZas8M0o1a0f7`8N9a7hcpcj04clb`bJb6bTbu9!049R9hcBcy04cAb6cC040kcEcNc8cTcIcpb{cpcMch6g9z0GaccSczcB8O0g8S4%0F5$5X1R5J0F5L1I0I5Nd32/2+292b2-0m1_c~d15U1Oa=3F2Z0s0=0J0m0H0y0=0%0Q1a1A1C1E1G0nb~as1V3s1P0M0v0n7n0n0q6=0S0I0y6;dx6%0m2i1w1`0W2T0*dH1sdN1w0~2W0)0_dN6~0Z380Sbs6=6@6+0n6T0n2P173l0ycZ0Z0U0o0R1E001r0n1p0|e11{0^0~5Q8%0m0I0*2x2Ud%1{1/6+1G9:1Y1T040D722Q130o0?e8egd@0S6:0n0*7qdN6;d)11dHd?0G00e7emdOe6720s0*2g5R6~0$2_7=0n0G2m0~1`ek0U0W2Ddy5#5R048)c|e;dH0I68c}e=5|aAe@5%e$0yd e1dRdx0v6(e50s1pdO0{e`0IeC0OeC0Ne)dS0s0-2I6%e1dN0x0n0.e(0 1{0)12cZeK5QdU0ydWeA2w0nd#0Z0~2u2x6(dI7L1i2T0%1hdN0W1a090/09fV0%fz0v0K0!0f0/0#0g09bD8c0/2QeDfR0NfTfVfFfYf-f:6VcQ6:d%fw0v001i0?2Z0gep3s2}3F201.1:1=5V5J5H3de|a`b)aq8nb-c#4fa*bXa,cvdi8y91cm8Cb|a^aK9)apaN7Pc53rc76zcKc+crguai8sbzdq6 0WaB8gf;57anaYgJa!gT2sa%cwaw6ogW0=gYa.cJb4aGg,7F9wbgc.1a0}adgFdA1bc08H040oa;gObS6i34h3c6a5g`cc86c,g/9y7m6+az5 b|0/gG8-c0aoho04h2bKbMg|9=040md-2w0Gg^c)gQhEcqbLbpg2bccp6J9Fhxhicng{c-3FhmgAbObqcuhCbp0=g=g@htbphBgFhWh79*hNh#9`gSh|h)c:akhghOh%9mg;gx7=g?e,hLhO9zh?hU1ag$hwgIa{8IgLbHie6+3=f0de5W2*5L1cd10_0{0}04.
Parcours en profondeur infixe

Compléter les méthodes infixe des deux classes ABVide et AB. Ces deux méthodes renvoient 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 = ABVide()
>>> vide = ABVide()
>>> trois = AB(3, ABVide(), ABVide())
>>> deux = AB(2, trois, ABVide())
>>> un = AB(1, ABVide(), ABVide())
>>> ab = AB(0, un, deux)
>>> vide.infixe()
[]
>>> ab.prefixe()
[1, 0, 3, 2]

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

.128013.87095[4})2FR,Ba iVà8m16l7.e:9A;US/dktf{+IrjT3sogu0x]PpONnh=céyvêD(wq_b050G0y0I0m0o0v0R0n0)0v0m0R0R0(010I0o0Z010406050R0U0s0s0m0N0+040E0S0v0U170S0$0n020m0s0Z0C0n0j0y1h0N0;0U0y0R050F1e1g1i1k1c0Z041I1P051S0F1S1U1P1c0G0o0,0 1113150%0o0T0%0v1,0%0I1a050`0?0v0y1%1214011+1-1/1-0I1^1`1?0I0?0S0G1k1@0N1Q0I0%0 1n0R0Z0m0$150h011|1)010J0|0y0$1v0y1?2k2m2r1~2u1`2x0s2z040a0n0Y0N0S0Z0S0R0o1q1s0^2i0N0N0y0)2U1I2B0$1Q0F2g2*0I2e2d2f0G2D151/0$2w2R1?1!1$101}2@0o2_0$2a1#1?0Z2Z1Q2(2*3b1d2l1s2 2s340N1h0v1a0n0t2%3f1b3e2C3h1~3j3l3n0h3q2m3s2(2?013x0m3m040n0Q3B2)1c3E3v153H3J0n0e3N3D3f3F3T3n0c3X3P3Z3R3G0S3k3I3n0u3(3t3g1(3w3-3y3K0w3=3Q3^3S3`3/3K0r3~3*403,3.3U0A463u483#040t0V4d3@30493{0t3p1J3r3)4e4m4g0t3A4r3C4t4l3i423J0t3M4z3O3?3!4E1a0t3W4I3Y4u4D4a4N3%4Q4B4L4U4h3;4X4K3+4w3}4%3 4v4M4h454,474.4!0t4c4=4S3_4!0h4j4{4C4}3{0h4q3b4Y4)4/0h4y574(4f5a4H5d4-4T544P5i4?5k430h4W5n4|414~4$5t525v544+5y4Z544;3d1V391I2}2-0G2;3F0)2a2J0@1#1Q380y3a3r3X055Q0^5Y5u010H1a3v5!5j1~0:3n5.5o3w0)1a0B0l0p0o0^5?5)19040z3(0n660n5e4m5+040^0J605z015;3K6f3F0J0s1a0=0=322T6p6k3+620/6u480?620R0y0v6e4Q692s620g644X676N685/156b2l133X666H1~0)0t1a030n1`2i0$0R2.0U2#0y0U0N0n0$000y0J0J2!0I1F0n0m6-0U2_6~2#0o1r3(066N6X6R1a6d6y4m6i686G6Q3G0J1a1G0I0=0,5~0y7e6I1a6x7i5@156A1a6C6E7t1~6J6L576O677a5*1a2Z6|0N0$6V7L0H5_040P0N1F77797j6b7d7x5)7g7E3S7l04322u0W7s7)6g6w7,017A047C6F3d7j7G657J6P7y7M047O6:7R4Q85611a0d0X7!7K7$7c6^7`7+7@6l6n046p6+0N6t8p6v7v7`7|7~7`826M847T7N0_8a7S7j0R2p04010b017758486b5-8x488o80860$7V5{8D1a7H4s7#867%8m8Y7f5=8=2s6m6o6q0$6s0=8*047w8#5)8B6D7 5Z811a0k8L8$1a0,3I6/0N909b8c7L0$1a0T6 0)0%7?937^9a9c5)9n6c2O2T906K837J7L957D8^1~0S1a0x7`9z9f1`6:9x6g9M040(9U3!9e9g9T8F9G7j9I973C7L9W9O9K3S9o9q9s9Z3+9W9Y9l7j9z9p6-9^9(6O9H6B967`9/9P7c9B0I9_489{ae4vab0S9C4X788j8/8l9,2)7L8!988$7.7n7p7r9092av94a69J9u3F8E7I8G8k888J7Qah2s7U1a0i3I6C8i6WaM7(aH3+au9-9~7.7:0o7=aB8AaFar5(9v049Ea38.5)6b89aP9}869+a89Naa04a09r9taD9Vb39;3G1aa+a-bc6w0gaQ9L1a0Lbk15620da/7Ba7bca9bc9Q9$9ibh1a8ha 5)9WbnbE6gb1bvbba#4fajalbN4mbwbR3ibe0$7;b8a(86biaX8d6g8:a;at8@bU2E8r8t2.8wb.bp8zbcbKb@01aJ8-aLapaN7P8b3bb(3F0R0m1ab+8M8O01aCb!5)2S1a0Kbs7}bub|bTb99!b59@bZas8M0o1a0f7`8N9a7hb|ci04ckb`a:b2049:b|by9SbAcEcx04czbccB040kcDcq3+cFcHb|b{c!afbMc*ai9AakadcVcScUcE8O0g8S4%0F5$5X1R5J0F5L1I0I5Nd42/2+292b2-0m1_c d25U1Oa=3F2Z0s0=0J0m0H0y0=0%0Q1a1A1C1E1G0n8,9-1V3s1P0M0v0n7n0n0q6=0S0I0y6;dy6%0m2i1w1`0W2T0*dI1sdO1w0~2W0)0_dO6~0Z380Sb76=6@6+0n6T0n2P173l0ycY0Z0U0o0R1E001r0n1p0|e21{0^0~5Q8%0m0I0*2x2Ud(1{1/6+1G9:1Y1T040D722Q130o0?e9ehd^0S6:0n0*7qdO6;d*11dId@0G00e8endPe7720s0*2g5R6~0$2_7=0n0G2m0~1`el0U0W2Ddz5#5R048)c}e=dI0I68c~e?5|aAe^5%e%0ye0e2dSdy0v6(e60s1pdP0{e{0IeD0OeD0Ne*dT0s0-2I6%e2dO0x0n0.e)0 1{0)12cYeL5QdV0ydXeB2w0nd$0Z0~2u2x6(dJ7L1i2T0%1hdO0W1a090/09fW0%fA0v0K0!0f0/0#0g09bj8c0/2QeEfS0NfUfWfGfZf.f;6V9R9hd(fx0v001i0?2Z0geq3s2}3F201.1:1=5V5J5H3de}a`b)aq8nb-c-3ia*bXa,cudj8y91cl8CbBa@dB3O84c63+a|aOc43rgL6zcJbLcLb48|bY0=6 0WaB8gf=57anaYc1a!gv5:gucg6gbX6obfdrg!a.cIbtaGg.b^cXbobd040}c;b|b~4AgK8H7/a;gRbS6i34h6gQa5g}cb86cpg;cray7q5 gG0/a^aKgKg+aEhlcKcMg h3b6a2coc,hp4)g@gy7=gZe-g{cN1ah59D9Fhy9mhT6+hCb40md.2w0GhRhEc)hKc+gVbx9#cPhVa_c0hAcmg~h.bShJcv9dc/bQhEhoi09yhMgYg`hub4hUgGg(b 9)c1a}gP3ChebVh4h!c|e}d0df5Ldi0#dNeSe40|0n1e6_2Tf3e%0*0Z11d*6;eL2272e;5%h50xh%0Zh)0/dd0xg36:f=e}d 1i0n0NiT3-e{dLg70odV0*2I0$0`2UiFeLeVeX2WiP5X5WbY1Ie}gd1cd20_0{0}04.
Parcours en profondeur suffixe

Compléter les méthodes suffixe des deux classes ABVide et AB. Ces deux méthodes renvoient 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 = ABVide()
>>> vide = ABVide()
>>> trois = AB(3, ABVide(), ABVide())
>>> deux = AB(2, trois, ABVide())
>>> un = AB(1, ABVide(), ABVide())
>>> ab = AB(0, un, deux)
>>> vide.suffixe()
[]
>>> ab.suffixe()
[1, 3, 2, 0]

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

.128013.87095[4})2FR,Ba iVà8m16l7.e:9A;US/dktf{+IrjT3sogu0x]PpNOnh=céyvêD(wq_b050G0y0I0m0o0v0R0n0)0v0m0R0R0(010I0o0Z010406050R0U0s0s0m0N0+040E0S0v0U170S0$0n020m0s0Z0C0n0j0y1h0N0;0U0y0R050F1e1g1i1k1c0Z041I1P051S0F1S1U1P1c0G0o0,0 1113150%0o0T0%0v1,0%0I1a050`0?0v0y1%1214011+1-1/1-0I1^1`1?0I0?0S0G1k1@0N1Q0I0%0 1n0R0Z0m0$150h011|1)010J0|0y0$1v0y1?2k2m2r1~2u1`2x0s2z040a0n0Y0N0S0Z0S0R0o1q1s0^2i0N0N0y0)2U1I2B0$1Q0F2g2*0I2e2d2f0G2D151/0$2w2R1?1!1$101}2@0o2_0$2a1#1?0Z2Z1Q2(2*3b1d2l1s2 2s340N1h0v1a0n0t2%3f1b3e2C3h1~3j3l3n0h3q2m3s2(2?013x0m3m040n0Q3B2)1c3E3v153H3J0n0e3N3D3f3F3T3n0c3X3P3Z3R3G0S3k3I3n0u3(3t3g1(3w3-3y3K0w3=3Q3^3S3`3/3K0r3~3*403,3.3U0A463u483#040t0V4d3@30493{0t3p1J3r3)4e4m4g0t3A4r3C4t4l3i423J0t3M4z3O3?3!4E1a0t3W4I3Y4u4D4a4N3%4Q4B4L4U4h3;4X4K3+4w3}4%3 4v4M4h454,474.4!0t4c4=4S3_4!0h4j4{4C4}3{0h4q3b4Y4)4/0h4y574(4f5a4H5d4-4T544P5i4?5k430h4W5n4|414~4$5t525v544+5y4Z544;5D594~4`5H5f4!0Q505L4@3{0Q564s5e5R430Q5c3r1R391I2}2-0G2;3F0)2a2J0@1#1Q380y3a5#4Q055.0^5_5u010H1a3v3X5W2s0:3n655j3w0)1a0B0l0p0o0^6a5o1~19040z3(0n6r0n661~62040^0J6k60683K6A5z2t0s1a0=0=322T6J6E3F6n0/6O3+0?6n0R0y0v6z5{6b156n0g6p4X6s6+6t6#611a2l133X6r6u150)0t1a030n1`2i0$0R2.0U2#0y0U0N0n0$000y0J0J2!0I1F0n0m740U2_7i2#0o1r3(066+6^6/6x7c6S486C6t6!6l3S0J1a1G0I0=0,6i0y7y4m6Q7N2s6U1a6W6Y7Q6m1a6(6q6,6@6.6w2Z7g0N0$6?7u0H6d040P0N1F7r7t7%1a6y7W157A7}3G7F041e7d0o0W7M7C607P896F7S836X6Z3d6.6%6)577#7$7D7v7)777,4Q6-8p6n0d0X7^6s7.7{7x8c3F7 8F3+0J6H046J720N6N8I488b8i8p8e7U8h5#8j7Y8l4s8n8v607(0_8s7-6.0R2p04010b017r58486w648R4m8H8U600$7:6f806n8$4A7_8p6w7|8~67699e2E8L6J6L7I0=961a6R9h158W8g9o040k8.8p0$1a0,3I760N9v9x8u7u9A040T7j0)0%88916F0S1a0(807/1a0!1r9Q8Z8w1a9H3b8)6F9K0G2O2T809T049V9r617:9Z2_9v7Z6*8n7u9t7V9^9=0x809K9C1`779y609=9@9*9J9B9Dab9 7#8C040o8Y3C9+3!1a9M749Pac9S6C0o1H9I7%9`9!9v983O8(9a92au9NaxaD8paeayat046f6h6j9^6Q0g7!am7`aoaq2)as4)7{9/0IaT3+0SaAaCagaE9YaGaZ1aaI1baK8B6.9-a/a;48aSaQaMaV6g7L9v0/a#al6,a16V9ua41aa69^9Kav9O9#ar7ub8a_9zaNawbtaJa06.a2a*5 9Sbna7a.0S9:b9bI9?b64vbLbN577sb29b8DbG7u909$92827H7Jbda}049q9R3FbF9}a bWa%bY048r7+bR2s9X040i3I6W8A8o8*bZ80b$3C9J82842u87be80b=b-9~8mbDb`b|8tbx60cjb:a=bJbpbzbs9;cwcu4f7T0U85cgb-bfb~1~9=0LcK9sbka3cC4ma5bK6xb5bm04bocS3icEcGbBbH6P9pbgcrbPcNbOc+040dcicQb!6.cUcx04a99E9v8z4Xb^a,8{c89^ca2)7u8K6I0=8O8Qc#7Xb.c^7Tbldh6$8#a$bia(cpcO010R0m1ac`8p8:1a01b/b%6F2S1a0Kdk8fcRdF3Fc|dn3GcyaPdQdH040f80dB9w7BdU0odIdK8XcAcZcVc akd$1adX9^dZ0kd#dN3+dVdJ9^ctd`b7cBe0bScWbMa:d?d%dWdY8;0g8^4%0F5}5^5$ei0F5)1I0I5+en2/2+292b2-0m1_ek5)1Oc*3+2Z0s0=0J0m0H0y0=0%0Q1a1A1C1E1G0na 1R3s1P0M0v0n7H0n0q790S0I0y78eQ6~0m2i1w1`0W2T0*eZ1se)1w0~2W0)0_e)7i0Z380Sbs797b720n6;0n2P173l0yd^0Z0UaB1E001r0n1p0|aB1{0^0~5.930m0I0*2x2Ue|1{1/721Gbo1Y1T040D7m2Q130o0?fpfxf90S770n0*7Ke)78e~11eZf80G00fofDe*fn7m0s0*2g5/7i0$2_870n0G2m0~1`fB0U0W2DeR5|5/bb1Ieh3K0_6tg8aWb,g8f`0yfhaBe-eQ0v6 fm0s1pe*0{0I0n0IfT0OfT0Nf}e.0s0-2I6~aBe)0x0n0.f|0 1{0)12d^f#5.e:0ye=fR2wgu1B0Z0~2u2x6 e!7u1i2T0%1he)0W1a090/09g.0%gO0v0K0#0f0/0!0g09c-3r0n0/2QfUg*0Ng,g.gUg;g h26?d.gzf`gL0v001i0?2Z0gfG3s2}3F201.1:1=5?5%3d5{gfbXc77wdz6B9gdQ0$cdcFcfc)7u8Te37Rc_b?dqaL6F8+7*cqh4bjdldMcbc{e2h+by8Mce86eJ7j0Wbe8yh34Ad4an9ddQd9eB4f82dehOh=0=h@chd~hVb-9)h%b31a0}e7dQ8khXhFhZ1aapdua?1a34ijif8VicdQdPhT3w7G72b+aYikc,b@b1c68diyiB15iAh.babrdTiO01iQdaigh:i687i8g0iahLih729}imb_csiNiRbPc!iVb4e6d+i@i=aUi5c(i%h^cIcViii-bh8(ah04j5cYi|iYh/0mf22w0Gi)iVd i}cvd,c}hij6cmi/iob{8,b}c;a-jai,efg8ej2*ezfI9ZfY0nfk0|0nh;gt2W0G0*0Z11e~78f#227mg45~ii0xjg0Zji0/ew0xhibgg8fg1i0n0Nj)3-gte$hm0oe:0*2I0$0`2Ugg0~f/f;fsgbg55@hPg7g5fb0Uka5~32kdegg5hs1cel0_0{0}04.



Compléments

L'implémentation utilisée ici propose une particularité en termes de codage : si on observe attentivement les différentes méthodes qui ont été implémentées, on se rend compte que :

  • Les méthodes de la classe ABVide ne comportent que les cas de base des algorithmes récursifs.
  • Les méthodes de la classe AB ne comportent que les cas récursifs des algorithmes.

On n'a donc plus besoin ici d'utiliser de conditions, car c'est la construction de l'arbre, avec un type d'objet ou l'autre, qui va d'une certaine façon "coder en dur" les conditions des algorithmes directement dans la structure de données.



Il est possible de gagner un peu en empreinte mémoire sur ce type d'approche en réutilisant toujours le même objet ABVide() pour tous les arbres vides. Cet objet est alors un "singleton". Il peut par exemple être déclaré en tant que constante globale (ici, VIDE) et est ensuite utilisé dans le constructeur des objets ABVide() lorsqu'il manque l'un ou l'autre des sous-arbres en argument.

class ABVide:
    def est_vide(self):
        return True

    def __str__(self):
        return "∅"

VIDE = ABVide()

class AB:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = VIDE if gauche is None else gauche
        self.droit = VIDE if droit is None else droit

Remarque : il n'est en fait pas nécessaire d'implémenter la méthode __init__ dans la classe ABVide, puisque rien n'y est fait de particulier.