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

.12801342Any6g3p )rPv1=oa_ckmiu5B(,eVtsShl970bf8/d050R0D0F0s0x0J0G0k0u0J0s0G0G0q010F0x0j010406050G0y0w0w0s0m0f040H0r0J0y0,0r0e050Q0?0^0`0|0;0j04151c051f0Q1f1h1c0;0R0x0o0!0$0(0*0I0x0h0I0J1v0I0F0/050V0N0J0D1q0%0)011u1w1y1w0F1E1G1C0F0N0r0R0|1D0m1d0F0I0!0 0G0j0s0e0*0c011I1s010O0X0D0e0s0w0D1C1*1,1;1K1@1G1`1|0/0a0k0n0m0r0j0r0G0x120e0k0T1(0m0m0D0u2h151 0e1d0Q1$2u0F1!1Z1#0R210*1y0e1_2e1C1n1p0#1J2E0x2G0e1W1o1C0j2n1d2s2u2Y0=1+2i2M1=2R0m0_0J0/0k0p2r2$0:2#202(1K2*2,2.0c2;1,2?2s2D012{0s2-040k0i2 2t0;322_0*35370k0b3b312$333h2.0z3l3d3n3f340r2+362.0g3s2@2%1r2`3x2|380L3C3e3F3g3H3z380P3L3u3N3w3y3i0K3T2^3V3p040p0M3!3E2N3W3I0p2:162=3t3#3-3%0p2~3=303@3,2)3P370p3a3}3c3D3o420/0p3k462u2V0D2u2K2x0R2B330u1W1}1d4j1g2W3D2Z2=054o0T2X3U3_0/0s0N0t452Y0k483v0r0/0q3l4K3M4D040d0A3l4L3V0.040B4X4S1=0w0x0/4I4x4(1K4!0C4Q4Y4T4V0E0x0T4%4C1=4!0B0l4=4e4R4~2`0/4_4{0D4}3^4 0/510l3+3o4E4G3;4J4@1=4N044P545o574U4W4e5u0*505c401K4*4b5C334;4?4/3g5k4H5H3v5J5t5L34580A4`4|5y5T500l5h4e3 5j044F0t4d5n5T5q5s5/565M5w5P4Z5f5`3-5F045.4.5@015R5?5d5v595Y2!5!5f525K630e5V5X5b5Z635#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~7f5N2P0F766=4O7q6r5V7i5|6~335 3*7y5Q756@775N5m736 7d306Z7G6t0t727b6c047k3c6q3$5N0I7t3V6?6;7u5_7C5{6F7+3-0G1/041L017w046X7M7m6$6T7.6E517`2t7N5*696k6L744#5$5i7)5,0v7#3-7%7e5T6_5x887K7x8n337:0/010v7@7 4:7E7(7Y7}6a7J5I6W8g2)6i7~8q7D8a7V3m6^5N878j6x7s7F858m8E8M4$8x0*8s7=1}7^82387|5,7!8$6)7_8H686S8D7S6M8N8c8B5,0O8@0*8i7{8k7v8;6}8L3V8(1?8w9a3-7L837|867^81926.4G8f980/8O7X4T5,0N9n949i967*9f806(9c0N9e8Z7,8,847)9k9r8a9L8.4G8S8{899t9S0t0u9y8V8A4^8Y9V8o7-9D1K9c0u9I9*8F8?8W8d4G919P9R9B9O9-6V8}5(9Y0G2y9#5r9n8l9l9F7;010s9;2t7c8z8T8Q7P9x9|a95N9!9P9X0Q4z4h1e4u0Q4s2v4l152y2x1V1X2x4F1G4i1o2?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

.8709.12801342Any6gF3p )TrPv1=oa_{ckm}iu5B(,eV:tsShl970w+bf8./d050!0I0L0v0C0P0M0m0y0P0v0M0M0t010L0C0l010406050M0D0A0A0v0p0g040N0u0P0D0^0u0f050Z0 1113150}0l041e1l051o0Z1o1q1l0}0!0C0r0-0/0;0?0O0C0i0O0P1E0O0L0{050(0V0P0I1z0:0=011D1F1H1F0L1N1P1L0L0V0u0!151M0p1m0L0O0-180M0l0v0f0?0d011R1B010W0*0I0f0v0A0I1L1?1^1}1T201P23250{0b0m0q0p0u0l0u0M0C1b0f0m0$1;0p0p0I0y2q1e280f1m0Z1/2D0L1-1,1.0!2a0?1H0f222n1L1w1y0.1S2N0C2P0f1)1x1L0l2w1m2B2D2+0~1@2r2V1~2!0p120P0{0m0s2A2/0|2.292;1T2?2^2`0d2}1^2 2B2M01340v2_040m0k382C0}3b320?3e3g0m0c3k3a2/3c3q2`0E3u3m3w3o3d0u2@3f2`0h3B302:1A333G353h0R3L3n3O3p3Q3I3h0X3U3D3W3F3H3r0Q3$313(3y040s0S3-3N2W3)3R0s2|1f2~3C3.3_3:0s373~39403^2=3Y3g0s3j463l3M3x4b0{0s3t4f3v414a3*4k3A4n484i4r3;3K4u4h3E433T4A3V424j3;3#4F3%4H4x0s3,4L4p3P4x0d3?4R494T3R0d3}2+4v4C4I0d454%4B3/4*4e4-4G4q4!4m4=4M4@3Z0d4t4`4S3X4U4z504Y524!4E554w4!4K2-1r2)1e2T2G0!2K3c0y1)261m5i1p5g5e2-5n0$2*4{1T0z0{323u4.3_0T2`5E4?330y0{0e0F0J0C0$5J5z0?0`040K3B0m5!0m5F1~5B040$0W5T51015H3h5-561 0A0{0w0w2Y2p5`5=3c5W0G5 3E0V5W0M0I0P5,4n5%1T5W0n5Y4u5#6i5$5K0?5)1@0;3u5!6c0?0y0s0{030m1P1;0f0M2H0D2y0I0D0p0m0f000I0W0W2x0L0D1Q0v6E0D2P0m0v2y0C1c3B066i6s015)5+633(5:5$6b6l3d0W0{0I6C0w0r5R0I6-3_616 1~650{6769726d0{6f5Z6j6r6=5)2w6Q0p1d4n6k5U6*5M040o0p6R6$6(7f0{6,6;7n6/783p6@040(0*1P7C01717z5.7404766a2-6=6e6g4%7d7e7n7g0%6H7k2+7m5.0A0C0{4W4%6%5#6)6+6M7J7B7M5?0W5^045`6C0p5~7`600{62836466687R2~6)7U7c7d7=0{7h7$6q6)0M1{04010a016$4(3(5)5D876.5I8y427p5O7J5W7V3 7v7Z7x7@8B1~7_7S7n7|5_5{0f5}0w8F857J7O7Q8Y040H8l6=0f0{0r3f6G0p8%8)7l6)8,040i6T0y0O6~8N798(8*7n8_0!2k2p8%7b6h7X6)8#8a7J0u0{0Y7J8_8.1P6H935.9h040t9p5?9l8/9o9b8g6=9e77900?9r9j9E3d0{8{6E8~9u3c9r9t8@8+9K8|9N9z6j9d899D8Q9q9i9k7x970L9O3E9Q9-3/9*0u984u7:7Y5.7?8b396)8P8c8+7E6_0L6{6}8%869$5?9C9}2C8d7a8H477X7)5?7!7i7%2~ak3c0z7p0j3f677u7;7w5*8Maa3ca09~a20{7G0P7I9I7LaC88759faLag8f9Yaz8j7j9:3_7+4kaY1~9r0Ua$1Tac9g9(9I8_9L8}8 aN3(9G9)7F0)aJa?a17n610na*9F0{a)9S7na,9Ia_a/9=9@a@3_bbbf2=aHa|aKbi910Gb29^8J9{8Lad5y5.aEae6=8S7~0w8082bn5V8Z9Ib9bG7KaS9Xbsal8i7#aXb75.0M0v0{bv8m8o01a9a bV7,040x8!9!bZ6=bhb(9v9U9Ma~aF7n2o0{0B7J8n0{0H6:bLb|b+b-aP9#b=9Pa.bL9w9n8;9Ic5b~ch8oc2b b*b,bJb.a-049Hcdbd9,chb*cjc48o0n8s4A0Z5w0I2D2(cI5h1x5j2G2I2E1(1*2G0v1OcL0Z5i0}cY0%a|0M04.
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

.8709.12801342Any6gF3p )TrPv1=xoa_{ckm}iu5B(,eV:tsShl970w+bf8./d050#0J0M0w0D0Q0N0m0z0Q0w0N0N0t010M0D0l010406050N0E0B0B0w0p0g040O0v0Q0E0_0v0f050!101214160~0l041f1m051p0!1p1r1m0~0#0D0r0.0:0=0@0P0D0i0P0Q1F0P0M0|050)0W0Q0J1A0;0?011E1G1I1G0M1O1Q1M0M0W0v0#161N0p1n0M0P0.190N0l0w0f0@0d011S1C010X0+0J0f0w0B0J1M1@1_1~1U211Q24260|0b0m0q0p0v0l0v0N0D1c0f0m0%1=0p0p0J0z2r1f290f1n0!1:2E0M1.1-1/0#2b0@1I0f232o1M1x1z0/1T2O0D2Q0f1*1y1M0l2x1n2C2E2,0 1^2s2W1 2#0p130Q0|0m0s2B2:0}2/2a2=1U2@2_2{0d2~1_302C2N01350w2`040m0k392D0~3c330@3f3h0m0c3l3b2:3d3r2{0F3v3n3x3p3e0v2^3g2{0h3C312;1B343H363i0S3M3o3P3q3R3J3i0Y3V3E3X3G3I3s0R3%323)3z040s0T3.3O2X3*3S0s2}1g2 3D3/3`3;0s383 3a413_2?3Z3h0s3k473m3N3y4c0|0s3u4g3w424b3+4l3B4o494j4s3=3L4v4i3F443U4B3W434k3=3$4G3(4I4y0s3-4M4q3Q4y0d3@4S4a4U3S0d3~2,4w4D4J0d464(4C3:4+4f4.4H4r4#4n4?4N4^3!0d4u4{4T3Y4V4A514Z534#4F564x4#4L2.1s2*1f2U2H0#2L3d0z1*271n5j1q5h5f2.5o0%2+4|1U0A0|333v4/3`0U2{5F4@340z0|0e0G0K0D0%5K5A0@0{040L3C0m5#0m5G1 5C040%0X5U52015I3i5.57200B0|0x0x2Z2q5{5?3d5X0H603F0W5X0N0J0Q5-4o5(1U5X0n5Z4v5$6j5%5L0@5*1^0=3v5#6d0@0z0s0|030m1Q1=0f0N2I0E2z0J0E0p0m0f000J0X0X2y0M0E1R0w6F0E2Q0m0w2z0D1d3C066j6t015*5,643)5;5%6c6m3e0X0|0J6D0x0r5S0J6.3`62701 660|686a736e0|6g5!6k6s6?5*2x6R0p1e4o6l5V6+5N040o0p6S6%6)7g0|6-6=7o6:793q6^040P6U0M6H0p7D01727A5/7504776b2.6?6f6h4(7e7f7o7h0(6I7l2,7n5/0B0D0|4X4(6(5$6*6,6N7M7C7P5@0X5_045{6D0p5 7}610|63866567697U2 6*7X7d7e7^0|7i7)6r6*0N1|04010a016%4)3)5*5E8a6/5J8B437q5P7M5X7Y407w7$7y7`8E1 7|7V7o7 5`5|0f5~0x8I887M7R7T8#040I8o6?0f0|0r3g7K8*8,7m6*8/040i6U0z0P6 8Q7a8+8-7o8{0#2l2q8*7c6i7!6*8(8d7M0v0|0Z7M8{8;1Q6I955/9j040t9r5@9n8=9q9d8j6?9g78920@9t9l9G3e0|8}6F909w3d9t9v8_8.9M8~9P9B6k9f8c9F8T9s9k9m7y990M9Q3F9S9/3:9,0v9a4v7?7#5/7_8e3a6*8S8f8.7F6`0M6|6~8*899(5@9E9 2D8g7b8K487!7,5@7%7j7*2 am3d0A7q0j3g687v7@7x5+8Pac3da2a0a40|7H1b8?9K7OaE8b769haNai8i9!aB8m7k9=3`7.4la!1 9t0Va(340W0|130uaa8%9$af5z9)049JaP9?8|9X91a}3`9I9+7G7IaMb21 620n8^7+9#aR9%a37ob49K979-9i9*blaJb79Ab9930H0n0naz9|an8Oa^a18Dbu0@8V810x8385bG7N8$9Kae9baj3mal8k04aYaq3aas3F0N0w0|bD6?8q0|01abbi5/2p0|0ya?bgb*bjbpbN8{9N8 b1b:5@b=040C7Mb,8+6;bNc4b@bQa@boa{b59ob8c23dc4c69Kc80Icaclb$7/04cdbNbR9Kbkb}9@9_cbcvcocb8r0n8v4B0!5x0J2E2)cP5i1y5k2H2J2F1)1+2H0w1PcS0!5j0~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.870942AnygFI )TrPq;joàè{u5(,V:éts]h07w8f/63pOv1=«a_ckm}iBe»S9l[Rb.d050:0%0D0V0#0+0E0k0X0+0V0E0E0T010D0#0P010406050E0w0Z0Z0V0n0g040)0s0+0w140s0f0k020V0Z0P0q0k0-0%1e0n0p0w0%0E050M1b1d1f1h190P041F1M051P0M1P1R1M190:0#0R0|0~10120G0#0h0G0+1)0G0D17050@0.0+0%1!0 11011(1*1,1*0D1=1@1:0D0.0s0:1h1;0n1N0D0G0|1k0E0P0V0f120d011_1$010L0_0%0f1s0%1:2h2j2o1{2r1@2u0Z2w040a0k0o0n0s0P0s0E0#1n1p0=2f0n0n0%0X2R1F2y0f1N0M2d2%0D2b2a2c0:2A121,0f2t2O1:1X1Z0}1`2;0#2?0f271Y1:0P2W1N2#2%381a2i1p2|2p310n1e0+170k0S2!3c183b2z3e1{3g3i3k0d3n2j3p2#2:013u0V3j040k0O3y2$193B3s123E3G0k0c3K3A3c3C3Q3k0x3U3M3W3O3D0s3h3F3k0N3#3q3d1#3t3*3v3H0I3/3N3=3P3@3,3H0K3{3%3}3)3+3R0*433r453Y040S0H4a3;2}463^0S3m1G3o3$4b4j4d0S3x4o3z4q4i3f3 3G0S3J4w3L3:3X4B170S3T4F3V4r4A474K3!4N4y4I4R4e3.4U4H3(4t3`4!3|4s4J4e424)444+4X0S494/4P3?4X0d4g4^4z4`3^0d4n384V4$4,0d4v544#4c574E5a4*4Q514M5f4:5h400d4T5k4_3~4{4Z5q4 5s514(5v4W514.5A564{4@5E5c4X0O4}5I4;3^0O534p5b5O400O595S5g505V5e5Y5l5!3G0O5j5%5r4k5V5p5-5w5/5*5u5=5B5V5z5`5F5P5D3o1O361F2`2*0:2.3C0X272G0;1Y1N350%37624N056b0=6j5.0Y173s3U5T2p0J3k6u5Z3P0X170e0$0A0#0=6z5(1216040B3#0k6Q0k6v1{6r040=0L6J5.6x3H6Z5?0L0Z170W0W2 2Q6,6%3C6M0y6;3(0.6M0E0%0+6Y6l6A016M0l6O4U6R776S716V2i103U6Q6T120X0S17030k1@2f0f0E2+0w2Y0%0w0n0k0f000%0L0L2X0D1C0k0V7s0w2?7G2Y0#1o3#06777g016V6X6^456#6S706K3D0L171D0D0W0R6H0%7W4j6?7/2p6`176|6~7=1{737554786R7S6V2W7E0n0f7e826C040m0n1C7P7R7a177V7!6!6y8k5?0f7%040~0n0h7u0n7{6L176@8n3C7@047_6 3a717}6P80797#830?7v874N8M5.6M0,0F8f818h6W7A8x017Y8%6)6+0W7q0n6:8B3(7;8;458D8F8%8J768L8217848Q88710E2m04010b017P55456V6t8@4j8)9g3f8a6E8{177~4p8g8N8i8$9j1{9i8H7#8+046,6.7*0W9n048A9y5.8_6}8G628I170z937#0f170R3F8v9G9R8S7S9U040h7H0X0G7.9v8y049!388T8o8i2L2Q9G748K807S9L7`9.010s170/8%9%9W1@7v9S5.a4040Tac9@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%2W1b0+0@0Db54jaWaU8U170,8%apaOa5aQaj9Xbnbq456M8Xbya%bA172C9-9=as17aDb*aF170i2sa@0l9}aKb/04b(bQ04aubW4s7(8pb=bo8zbObsb}b a_aiax9+b)cb6=bwb^bzaib|a2aPavc2cmc02pbpcgbr7^aNcnbRcp6W9_bGc504b@b!bca(0J1(1@bH2p0s6#31cEb.9Tb%c4cs1{cocY3P7(7qa=6IcF0ybxb08Lb#ai0VcOcZb,c?c$b{cXcv45c!c}c1a)c|bi7#6?cHc.c/9?3C6V0#btda3(cQ17cSc_3D17c=czb~bSa;7,c*c#728zc-9qd9ancV04bC0wbE0VcTd0cPcAdu9%0V0P0P2t0:a@bSdnduc d4b$bTaa8wcFd7dydzck3XcWcNdocadXai2tcrdI7|c6cBdUd@12dWa+b`cdaIdu73cjd)9$d,cfd:aBdKd|dl04d=d3d d5d_dLdmc9bS0:cD9{e5cJ6q908Pb4bKaidDdFdH4xa$et5?7U9udubhei5.9A6,8.8:e3ekedbPd$9p4xc/8 dCew8RcU5.0E0Vb%8%951701a^ea3(2P170vc7cxa|edd~bud+9(aHe9eL5?e?040!e,960z7Zduf5e^a2eUdVece;4c9VbUd#fc0#17f7a2e-9:fbedfde_8EcyfhdpcBepaSeCf33Cf5frfc960l9a4!0M6n6i63fS0M661F0D68fX2,2(26282*0V1?fU661Le~3(2W0Z0W0L0V0Y0%0W0G0O171x1z1B1D0keWa+1S3p1M0j0+0k7)0k0C9)1@2F0f0D0k2N100#f+0k2T0U0k2+0^0D0%7w0(0|0G0Vg10kak7v0k0r0w7q1^dN0n0u0{7n0:0Cb(gh0Dfaf*0s1m0#102jgj0t0|0?gv0k0E1kgY1ogkgX7w0~0k0Z0C2d6c6SfR8r1fbmd#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(6V0L3*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-1Q040Q0wgb0f6b2Wfae)7p7m0V0k267s7nh82T3(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,iYkoiJ1DjYkHjqiBdNdP0fdRc+dTiSiBiUjPkOb1jgdeask|jlk`dMlCj7i{f1lPjEk+l2ikhCjvlokEclllaVlib`k,iQlvlTjLeei|lFd(d9eZjhkKbIlLj1j3l0fDeqlulQeflWjtjEd6kCjyiZkQl%adl)jnh?l4bLk/l-m2lUaZjlkZh lGlp9dev85jTirhUkGjl19k92%6hj(6fmC0=0@0_0E04.
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.870942AnygFIN )TrPq;joà{êu5(,V:éts]h07w+8f/U63pODv1x=a_ckm}iBeS9l[Rb.d050?0+0E0Z0)0.0F0l0#0.0Z0F0F0Y010E0)0S010406050F0x0%0%0Z0o0g040,0t0.0x170t0f0l020Z0%0S0r0l0:0+1h0o0q0x0+0F050O1e1g1i1k1c0S041I1P051S0O1S1U1P1c0?0)0V0 1113150H0)0h0H0.1,0H0E1a050`0;0.0+1%1214011+1-1/1-0E1^1`1?0E0;0t0?1k1@0o1Q0E0H0 1n0F0S0Z0f150d011|1)010N0|0+0f1v0+1?2k2m2r1~2u1`2x0%2z040a0l0p0o0t0S0t0F0)1q1s0^2i0o0o0+0#2U1I2B0f1Q0O2g2*0E2e2d2f0?2D151/0f2w2R1?1!1$101}2@0)2_0f2a1#1?0S2Z1Q2(2*3b1d2l1s2 2s340o1h0.1a0l0W2%3f1b3e2C3h1~3j3l3n0d3q2m3s2(2?013x0Z3m040l0R3B2)1c3E3v153H3J0l0c3N3D3f3F3T3n0y3X3P3Z3R3G0t3k3I3n0Q3(3t3g1(3w3-3y3K0J3=3Q3^3S3`3/3K0M3~3*403,3.3U0-463u483#040W0I4d3@30493{0W3p1J3r3)4e4m4g0W3A4r3C4t4l3i423J0W3M4z3O3?3!4E1a0W3W4I3Y4u4D4a4N3%4Q4B4L4U4h3;4X4K3+4w3}4%3 4v4M4h454,474.4!0W4c4=4S3_4!0d4j4{4C4}3{0d4q3b4Y4)4/0d4y574(4f5a4H5d4-4T544P5i4?5k430d4W5n4|414~4$5t525v544+5y4Z544;3d1V391I2}2-0?2;3F0#2a2J0@1#1Q380+3a3r3X055Q0^5Y5u010$1a3v5!5j1~0K3n5.5o3w0#1a0e0*0B0)0^5?5)19040C3(0l660l5e4m5+040^0N605z015;3K6f3F0N0%1a0!0!322T6p6k3+620z6u480;620F0+0.6e4Q692s620m644X676N685/156b2l133X666H1~0#0W1a030l1`2i0f0F2.0x2#0+0x0o0l0f000+0N0N2!0E1F0l0Z6-0x2_6~2#0)1r3(066N6X6R1a6d6y4m6i686G6Q3G0N1a1G0E0!0V5~0+7e6I1a6x7i5@156A1a6C6E7t1~6J6L576O677a5*1a2Z6|0o0f6V7L0$5_040n0o1F77797j6b7d7x5)7g7E3S7l045W2u0X7s7)6g6w7,017A047C6F3d7j7G657J6P7y7M047O6:7R4Q85611a0/0G7!7K7$7c6^7`7+7@6l6n046p6+0o6t8p6v7v7`7|7~7`826M847T7N0_8a7S7j0F2p04010b017758486b5-8x488o80860f7V5{8D1a7H4s7#867%8m8Y7f5=8=2s6m6o6q0f6s0!8*047w8#5)8B6D7 5Z811a0A8L8$1a0V3I6/0o909b8c7L0f1a0h6 0#0H7?937^9a9c5)9n6c2O2T906K837J7L957D8^1~0t1a0=7`9z9f1`6:9x6g9M040Y9U3!9e9g9T8F9G7j9I973C7L9W9O9K3S9o9q9s9Z3+9W9Y9l7j9z9p6-9^9(6O9H6B967`9/9P7c9B0E9_489{ae4vab0t9C4X788j8/8l9,2)7L8!988$7.7n7p7r9092av94a69J9u3F8E7I8G8k888J7Qah2s7U1a0i3I6C8i6WaM7(aH3+au9-9~7.7:0)7=aB8AaFar5(9v049Ea38.5)6b89aP9}86620/a/7Ba79;01a9b69Q9$9ib6628ha 5)9W0LaQ1~9+a89Naa04a09r9taD9Vbob91aa+a-bd7v0mbk15bibE7{a:bn049:a#4fajalbN4mb8bR3iby2Z7;bta(b0bCaX8d6g8:a;at8@bU2E8r8t2.8wb.157_b6bmbBa@8,4A84b(3Fa|aO8b3bc13+0F0Z1ab+8M8O01aCb!5)2S1a0vb37}b5b@b7bwcp9 9@bZas8M0)1a0(7`8N9a7hcpcj04clb`bJb6bTbu9!049R9hcBcy04cAb6cC040AcEcNc8cTcIcpb{cpcMch6g9z0?accSczcB8O0m8S4%0O5$5X1R5J0O5L1I0E5Nd32/2+292b2-0Z1_c~d15U1Oa=3F2Z0%0!0N0Z0$0+0!0H0R1a1A1C1E1G0lb~as1V3s1P0j0.0l7n0l0u6=0t0E0+6;dx6%0Z2i1w1`0X2T0DdH1sdN1w0~2W0#0_dN6~0S380tbs6=6@6+0l6T0l2P173l0+cZ0S0x0)0F1E001r0l1p0|e11{0^0~5Q8%0Z0E0D2x2Ud%1{1/6+1G9:1Y1T040P722Q130)0;e8egd@0t6:0l0D7qdN6;d)11dHd?0?00e7emdOe6720%0D2g5R6~0f2_7=0l0?2m0~1`ek0x0X2Ddy5#5R048)c|e;dH0E68c}e=5|aAe@5%e$0+d e1dRdx0.6(e50%1pdO0{e`0EeC0seC0oe)dS0%0w2I6%e1dN0=0l0Ue(0 1{0#12cZeK5QdU0+dWeA2w0ld#0S0~2u2x6(dI7L1i2T0H1hdN0X1a090z09fV0Hfz0.0v0T0(0z0k0m09bD8c0z2QeDfR0ofTfVfFfYf-f:6VcQ6:d%fw0.001i0;2Z0mep3s2}3F201.1:1=5V5J5H3de|a`b)aq8nb-c#4fa*bXa,cvdi8y91cm8Cb|a^aK9)apaN7Pc53rc76zcKc+crguai8sbzdq6 0XaB8gf;57anaYgJa!gT2sa%cwaw6ogW0!gYa.cJb4aGg,7F9wbgc.1a0}adgFdA1bc08H040)a;gObS6i34h3c6a5g`cc86c,g/9y7m6+az5 b|0zgG8-c0aoho04h2bKbMg|9=040Zd-2w0?g^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.870942AnygFIN )TrPq;joà{êu5(,V:éts]h07w+8f/U63pODv1x=a_ckm}iBeS9l[Rb.d050?0+0E0Z0)0.0F0l0#0.0Z0F0F0Y010E0)0S010406050F0x0%0%0Z0o0g040,0t0.0x170t0f0l020Z0%0S0r0l0:0+1h0o0q0x0+0F050O1e1g1i1k1c0S041I1P051S0O1S1U1P1c0?0)0V0 1113150H0)0h0H0.1,0H0E1a050`0;0.0+1%1214011+1-1/1-0E1^1`1?0E0;0t0?1k1@0o1Q0E0H0 1n0F0S0Z0f150d011|1)010N0|0+0f1v0+1?2k2m2r1~2u1`2x0%2z040a0l0p0o0t0S0t0F0)1q1s0^2i0o0o0+0#2U1I2B0f1Q0O2g2*0E2e2d2f0?2D151/0f2w2R1?1!1$101}2@0)2_0f2a1#1?0S2Z1Q2(2*3b1d2l1s2 2s340o1h0.1a0l0W2%3f1b3e2C3h1~3j3l3n0d3q2m3s2(2?013x0Z3m040l0R3B2)1c3E3v153H3J0l0c3N3D3f3F3T3n0y3X3P3Z3R3G0t3k3I3n0Q3(3t3g1(3w3-3y3K0J3=3Q3^3S3`3/3K0M3~3*403,3.3U0-463u483#040W0I4d3@30493{0W3p1J3r3)4e4m4g0W3A4r3C4t4l3i423J0W3M4z3O3?3!4E1a0W3W4I3Y4u4D4a4N3%4Q4B4L4U4h3;4X4K3+4w3}4%3 4v4M4h454,474.4!0W4c4=4S3_4!0d4j4{4C4}3{0d4q3b4Y4)4/0d4y574(4f5a4H5d4-4T544P5i4?5k430d4W5n4|414~4$5t525v544+5y4Z544;3d1V391I2}2-0?2;3F0#2a2J0@1#1Q380+3a3r3X055Q0^5Y5u010$1a3v5!5j1~0K3n5.5o3w0#1a0e0*0B0)0^5?5)19040C3(0l660l5e4m5+040^0N605z015;3K6f3F0N0%1a0!0!322T6p6k3+620z6u480;620F0+0.6e4Q692s620m644X676N685/156b2l133X666H1~0#0W1a030l1`2i0f0F2.0x2#0+0x0o0l0f000+0N0N2!0E1F0l0Z6-0x2_6~2#0)1r3(066N6X6R1a6d6y4m6i686G6Q3G0N1a1G0E0!0V5~0+7e6I1a6x7i5@156A1a6C6E7t1~6J6L576O677a5*1a2Z6|0o0f6V7L0$5_040n0o1F77797j6b7d7x5)7g7E3S7l04322u0X7s7)6g6w7,017A047C6F3d7j7G657J6P7y7M047O6:7R4Q85611a0/0G7!7K7$7c6^7`7+7@6l6n046p6+0o6t8p6v7v7`7|7~7`826M847T7N0_8a7S7j0F2p04010b017758486b5-8x488o80860f7V5{8D1a7H4s7#867%8m8Y7f5=8=2s6m6o6q0f6s0!8*047w8#5)8B6D7 5Z811a0A8L8$1a0V3I6/0o909b8c7L0f1a0h6 0#0H7?937^9a9c5)9n6c2O2T906K837J7L957D8^1~0t1a0=7`9z9f1`6:9x6g9M040Y9U3!9e9g9T8F9G7j9I973C7L9W9O9K3S9o9q9s9Z3+9W9Y9l7j9z9p6-9^9(6O9H6B967`9/9P7c9B0E9_489{ae4vab0t9C4X788j8/8l9,2)7L8!988$7.7n7p7r9092av94a69J9u3F8E7I8G8k888J7Qah2s7U1a0i3I6C8i6WaM7(aH3+au9-9~7.7:0)7=aB8AaFar5(9v049Ea38.5)6b89aP9}869+a89Naa04a09r9taD9Vb39;3G1aa+a-bc6w0maQ9L1a0Lbk15620/a/7Ba7bca9bc9Q9$9ibh1a8ha 5)9WbnbE6gb1bvbba#4fajalbN4mbwbR3ibe0f7;b8a(86biaX8d6g8:a;at8@bU2E8r8t2.8wb.bp8zbcbKb@01aJ8-aLapaN7P8b3bb(3F0F0Z1ab+8M8O01aCb!5)2S1a0vbs7}bub|bTb99!b59@bZas8M0)1a0(7`8N9a7hb|ci04ckb`a:b2049:b|by9SbAcEcx04czbccB040AcDcq3+cFcHb|b{c!afbMc*ai9AakadcVcScUcE8O0m8S4%0O5$5X1R5J0O5L1I0E5Nd42/2+292b2-0Z1_c d25U1Oa=3F2Z0%0!0N0Z0$0+0!0H0R1a1A1C1E1G0l8,9-1V3s1P0j0.0l7n0l0u6=0t0E0+6;dy6%0Z2i1w1`0X2T0DdI1sdO1w0~2W0#0_dO6~0S380tb76=6@6+0l6T0l2P173l0+cY0S0x0)0F1E001r0l1p0|e21{0^0~5Q8%0Z0E0D2x2Ud(1{1/6+1G9:1Y1T040P722Q130)0;e9ehd^0t6:0l0D7qdO6;d*11dId@0?00e8endPe7720%0D2g5R6~0f2_7=0l0?2m0~1`el0x0X2Ddz5#5R048)c}e=dI0E68c~e?5|aAe^5%e%0+e0e2dSdy0.6(e60%1pdP0{e{0EeD0seD0oe*dT0%0w2I6%e2dO0=0l0Ue)0 1{0#12cYeL5QdV0+dXeB2w0ld$0S0~2u2x6(dJ7L1i2T0H1hdO0X1a090z09fW0HfA0.0v0T0(0z0k0m09bj8c0z2QeEfS0ofUfWfGfZf.f;6V9R9hd(fx0.001i0;2Z0meq3s2}3F201.1:1=5V5J5H3de}a`b)aq8nb-c-3ia*bXa,cudj8y91cl8CbBa@dB3O84c63+a|aOc43rgL6zcJbLcLb48|bY0!6 0XaB8gf=57anaYc1a!gv5:gucg6gbX6obfdrg!a.cIbtaGg.b^cXbobd040}c;b|b~4AgK8H7/a;gRbS6i34h6gQa5g}cb86cpg;cray7q5 gG0za^aKgKg+aEhlcKcMg h3b6a2coc,hp4)g@gy7=gZe-g{cN1ah59D9Fhy9mhT6+hCb40Zd.2w0?hRhEc)hKc+gVbx9#cPhVa_c0hAcmg~h.bShJcv9dc/bQhEhoi09yhMgYg`hub4hUgGg(b 9)c1a}gP3ChebVh4h!c|e}d0df5Ldi0kdNeSe40|0l1e6_2Tf3e%0D0S11d*6;eL2272e;5%h50=h%0Sh)0zdd0=g36:f=e}d 1i0l0oiT3-e{dLg70)dV0D2I0f0`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.870942AnygFIN )TrPq;joà{êu5(,V:éts]h07w+8f/U63pODv1x=a_ckm}iBeS9l[Rb.d050?0+0E0Z0)0.0F0l0#0.0Z0F0F0Y010E0)0S010406050F0x0%0%0Z0o0g040,0t0.0x170t0f0l020Z0%0S0r0l0:0+1h0o0q0x0+0F050O1e1g1i1k1c0S041I1P051S0O1S1U1P1c0?0)0V0 1113150H0)0h0H0.1,0H0E1a050`0;0.0+1%1214011+1-1/1-0E1^1`1?0E0;0t0?1k1@0o1Q0E0H0 1n0F0S0Z0f150d011|1)010N0|0+0f1v0+1?2k2m2r1~2u1`2x0%2z040a0l0p0o0t0S0t0F0)1q1s0^2i0o0o0+0#2U1I2B0f1Q0O2g2*0E2e2d2f0?2D151/0f2w2R1?1!1$101}2@0)2_0f2a1#1?0S2Z1Q2(2*3b1d2l1s2 2s340o1h0.1a0l0W2%3f1b3e2C3h1~3j3l3n0d3q2m3s2(2?013x0Z3m040l0R3B2)1c3E3v153H3J0l0c3N3D3f3F3T3n0y3X3P3Z3R3G0t3k3I3n0Q3(3t3g1(3w3-3y3K0J3=3Q3^3S3`3/3K0M3~3*403,3.3U0-463u483#040W0I4d3@30493{0W3p1J3r3)4e4m4g0W3A4r3C4t4l3i423J0W3M4z3O3?3!4E1a0W3W4I3Y4u4D4a4N3%4Q4B4L4U4h3;4X4K3+4w3}4%3 4v4M4h454,474.4!0W4c4=4S3_4!0d4j4{4C4}3{0d4q3b4Y4)4/0d4y574(4f5a4H5d4-4T544P5i4?5k430d4W5n4|414~4$5t525v544+5y4Z544;5D594~4`5H5f4!0R505L4@3{0R564s5e5R430R5c3r1R391I2}2-0?2;3F0#2a2J0@1#1Q380+3a5#4Q055.0^5_5u010$1a3v3X5W2s0K3n655j3w0#1a0e0*0B0)0^6a5o1~19040C3(0l6r0l661~62040^0N6k60683K6A5z2t0%1a0!0!322T6J6E3F6n0z6O3+0;6n0F0+0.6z5{6b156n0m6p4X6s6+6t6#611a2l133X6r6u150#0W1a030l1`2i0f0F2.0x2#0+0x0o0l0f000+0N0N2!0E1F0l0Z740x2_7i2#0)1r3(066+6^6/6x7c6S486C6t6!6l3S0N1a1G0E0!0V6i0+7y4m6Q7N2s6U1a6W6Y7Q6m1a6(6q6,6@6.6w2Z7g0o0f6?7u0$6d040n0o1F7r7t7%1a6y7W157A7}3G7F041e7d0)0X7M7C607P896F7S836X6Z3d6.6%6)577#7$7D7v7)777,4Q6-8p6n0/0G7^6s7.7{7x8c3F7 8F3+0N6H046J720o6N8I488b8i8p8e7U8h5#8j7Y8l4s8n8v607(0_8s7-6.0F2p04010b017r58486w648R4m8H8U600f7:6f806n8$4A7_8p6w7|8~67699e2E8L6J6L7I0!961a6R9h158W8g9o040A8.8p0f1a0V3I760o9v9x8u7u9A040h7j0#0H88916F0t1a0Y807/1a0k1r9Q8Z8w1a9H3b8)6F9K0?2O2T809T049V9r617:9Z2_9v7Z6*8n7u9t7V9^9=0=809K9C1`779y609=9@9*9J9B9Dab9 7#8C040)8Y3C9+3!1a9M749Pac9S6C0)1H9I7%9`9!9v983O8(9a92au9NaxaD8paeayat046f6h6j9^6Q0m7!am7`aoaq2)as4)7{9/0EaT3+0taAaCagaE9YaGaZ1aaI1baK8B6.9-a/a;48aSaQaMaV6g7L9v0za#al6,a16V9ua41aa69^9Kav9O9#ar7ub8a_9zaNawbtaJa06.a2a*5 9Sbna7a.0t9:b9bI9?b64vbLbN577sb29b8DbG7u909$92827H7Jbda}049q9R3FbF9}a bWa%bY048r7+bR2s9X040i3I6W8A8o8*bZ80b$3C9J82842u87be80b=b-9~8mbDb`b|8tbx60cjb:a=bJbpbzbs9;cwcu4f7T0x85cgb-bfb~1~9=0LcK9sbka3cC4ma5bK6xb5bm04bocS3icEcGbBbH6P9pbgcrbPcNbOc+040/cicQb!6.cUcx04a99E9v8z4Xb^a,8{c89^ca2)7u8K6I0!8O8Qc#7Xb.c^7Tbldh6$8#a$bia(cpcO010F0Z1ac`8p8:1a01b/b%6F2S1a0vdk8fcRdF3Fc|dn3GcyaPdQdH040(80dB9w7BdU0)dIdK8XcAcZcVc akd$1adX9^dZ0Ad#dN3+dVdJ9^ctd`b7cBe0bScWbMa:d?d%dWdY8;0m8^4%0O5}5^5$ei0O5)1I0E5+en2/2+292b2-0Z1_ek5)1Oc*3+2Z0%0!0N0Z0$0+0!0H0R1a1A1C1E1G0la 1R3s1P0j0.0l7H0l0u790t0E0+78eQ6~0Z2i1w1`0X2T0DeZ1se)1w0~2W0#0_e)7i0S380tbs797b720l6;0l2P173l0+d^0S0xaB1E001r0l1p0|aB1{0^0~5.930Z0E0D2x2Ue|1{1/721Gbo1Y1T040P7m2Q130)0;fpfxf90t770l0D7Ke)78e~11eZf80?00fofDe*fn7m0%0D2g5/7i0f2_870l0?2m0~1`fB0x0X2DeR5|5/bb1Ieh3K0_6tg8aWb,g8f`0+fhaBe-eQ0.6 fm0%1pe*0{0E0l0EfT0sfT0of}e.0%0w2I6~aBe)0=0l0Uf|0 1{0#12d^f#5.e:0+e=fR2wgu1B0S0~2u2x6 e!7u1i2T0H1he)0X1a090z09g.0HgO0.0v0T0(0z0k0m09c-3r0l0z2QfUg*0og,g.gUg;g h26?d.gzf`gL0.001i0;2Z0mfG3s2}3F201.1:1=5?5%3d5{gfbXc77wdz6B9gdQ0fcdcFcfc)7u8Te37Rc_b?dqaL6F8+7*cqh4bjdldMcbc{e2h+by8Mce86eJ7j0Xbe8yh34Ad4an9ddQd9eB4f82dehOh=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/0Zf22w0?i)iVd i}cvd,c}hij6cmi/iob{8,b}c;a-jai,efg8ej2*ezfI9ZfY0lfk0|0lh;gt2W0?0D0S11e~78f#227mg45~ii0=jg0Sji0zew0=hibgg8fg1i0l0oj)3-gte$hm0)e:0D2I0f0`2Ugg0~f/f;fsgbg55@hPg7g5fb0xka5~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.