Arbre binaire de recherche⚓︎

On donne une partie de la classe ABR pour implémenter les Arbres Binaires de Recherche sans doublon : un ensemble fini de nœuds, éventuellement vide, organisés de manière hiérarchique. C'est une arborescence d'éléments comparables.

Un ABR est une structure de nature récursive :

  • soit c'est un ABR vide,
  • soit il possède un nœud racine qui a les attributs :
    • gauche : un sous-ABR à gauche
    • element : un élément comparable aux autres
    • droite : un sous-ABR à droite
    • l'élément de la racine est strictement supérieur à celui du sous-ABR gauche (s'il est non vide)
    • l'élément de la racine est strictement inférieur à celui du sous-ABR droite (s'il est non vide)

Dans l'implémentation suivante :

  • Noeud est une classe qui possède trois attributs :

    • gauche
    • element
    • droite
    • On aurait pu utiliser aussi un tuple nommé...

  • ABR() initialise un ABR vide.

  • Un ABR, vide ou non, possède les méthodes dont le nom est explicite :
    • est_vide(self) qui renvoie un booléen
    • insere(self, element) qui agit sur l'ABR
    • est_present(self, element) qui renvoie un booléen
    • affichage_infixe(self) qui renvoie une chaine de caractère composée des affichages des éléments et du séparateur |, suite à un parcours infixe.
Exemples 
>>> nombres = ABR()
>>> nombres.est_vide()
True
>>> for x in [1, 3, 7, 9, 9]: nombres.insere(x)
>>> not nombres.est_vide()
True
>>> nombres.affichage_infixe()
'|1|3|7|9|'
>>> nombres.est_present(7)
True
>>> nombres.est_present(8)
False
>>> fruits_ranges = ABR()
>>> fruits_ranges.est_vide()
True
>>> panier = ["kiwi", "pomme", "abricot", "mangue", "poire"]
>>> for fruit in panier: fruits_ranges.insere(fruit)
>>> fruits_ranges.est_vide()
False
>>> fruits_ranges.affichage_infixe()
'|abricot|kiwi|mangue|poire|pomme|'
>>> fruits_ranges.est_present("pomme")
True
>>> fruits_ranges.est_present("cerise")
False

Compléter les méthodes ci-dessous.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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 : 5/5
.128013lSetdA5!f18umaèg,_F/R=in 6)yà|qPhcN(bsx.p4r;C90"ovT+w7B3k:é 2I030907080i0r050G0$0C050i0G0G0q0Q080r0J0Q020t030G0g0h0h0i0L0w02060R050g0{0R0s030o12141618100J02031o1h1r0o1o10090r0S0:0=0@0_0B0r0k0B051F0B080~030+0F05071A0?0^0Q1E1G1I1G081O1Q1M080L1p080B0:1b0G0J0i0s0_0%0Q1S1C0Q0d0-070s0i0h071M1.1:1^1U1{1Q1~200~040$0A0L0R0J0R0G0r1e0s0$0)1,0L0L070C2l1h230s1p0o1*2y1'1)1(1N09250_1I0s1}2i1M1x1z0;1T2I0r2K0s0R2O1M0J2r1p2w2y2$111/2m2Q1_2V0L15050~0$0e2v2)0 2(242+1U2-2/2;0%2@1:2_2w2H0Q2~0i2:020$0Y322x10352|0_383a0$0K3e342)363k2;0b3o3g3q3i370R2.392;0u3v2`2*1B2}3A2 3b0W3F3h3I3j3K3C3b0f3O3x3Q3z3B3l0O3W2{3Y3s020e0P3%3H2R3Z3L0e2?1i2^3w3'3/3)0e313@333_3.2,3S3a0e3d3 3f3G3r440~0e3n483p3`433!4d3u4g414b4k3*3E4n4a3y3|3N4t3P3{4c3*3V4y3X4A4q0e3$4E4i3J4q0%3,4K424M3L0%3?2$4o4v4B0%3~4W4u3(4Z474$4z4j4T4f4*4F4,3T0%4m4/4L3R4N4s4^4R4`4T4x4}4p4T4D524Y4N4J564'4q0Y4P5a4G3L0Y4V3^4%5g3T0Y4#5k4+4S5n4)5q4:5s3a0Y4.5v4_3:5n4@5B4~5D5y4|5G535n515L575h555P5b5h595T5m3a0K5e5X4;5Z5j405l5%0~0K5p5)5r4 3T0K5u5/5w5;5Z5A5^5C3)0K5F5}5H5 5K625M5Z5O665Q5=5S6a5U5=5W6e5Y0~0b5#6i5+020b5(495:5I6k5.2x1s2!1h2O2B091)2G3y0C2W211p6B1q6z2'4g036H0)2#5_0Q0Z0~2|3o0$5*2}0C0~0D0R070g093o6#0_0}020!3v0$6@6!6t6W020)0d6Z6.1`0h0~0m0m2T2k746-6t6:0E796U0F6:0G07056~6P7a0~0l6 6t0s0~0k0i0g0C0B077d5C6:7o4g6_6U7r027i07200s087z5H7B7p7F0~092f2k7y7l6U6:0v6=4n6^7%7E5C7f0~7h7j7N360R0~0I7.4v7s7u7w7W2$7(5H7:020q7Q5~7^7v7x6?7'6@707*027,7k2'6t7 7=7X837H1Q7K7M7D707 818p7q0~7I8n87888a7g7i8e2^8q7;7?3(7S7U087{2^7}7/0~8s7|707G7T0R7V3v0t4X3Y6{6Y8t7F6%020a0X0p8H3/6:7#4W7%700G1?02000z0g0R080M0N3I1R8+0p0$0M0$0G1:0/090R0g1P1f8{8}8 8Y8?6`7S078D338O3y0d7202747608788j7O0~7c9A368b8d8.1_7Z8;3^88896t8^0~9h8~0M0'0s2k0r390r7h0g0L9S9j7$9N8A7+8C9I1U8h9.3j0~0L0i0C2T8M9q8F80825H0Z8)6(2K9k6^706{6}9 3r0d8v0G9y0S0r0)9;0Q7baj9G9-9E3y9K8y7'8@8_9'0M0p1}0S8W1R0g2m0F0R1b0#1}awas9l6U6{2r089$1g8'7)8B7-ap3Y9:aX3{9?9^9`aa3y0R0V0~9!a(8#a21f9{3f0taM5Ca89oa.3{ac022T7h2rajala!1_anaW8f7Y7na|2,8v8m1}8ob97A0~7!aLa69Pav8|9T9V0G0j2r989a2n9d9f2maD0$0#050#8naK9)8z9ma 9p2x9r3Yb7bN6T5CaZbi63adafaha=bT9B020EblbJ9N9O7eaVbS9}8ibW3ra$9_a4aT7~8Qbc2}6'6)6+b39Caj7G94c2b'0v7C8S8u8l7Jbgc7ca8N8T0~c6b51U7b0v0vbmb,a_be0rbSbPa#cd8xb`8P8`059(cbb-9,b88E8g8Gcm9=029@b^b#b:c4bece7Lc79L40b+a^5HbRajbVcK7RcPa%b_b=a)cMc/8I027t85cScL02b;c*8kb007b2cNakc3d37G8wcfd37Zcrcx1_6{7icvb}cOd8cXcBc:8`0kcFci6tc'd3c)33cjc,cRc(c;c~bXczd9c=8/0~cZ3fc#bncH8caodG1_dv6xcccQa'dudBdwcc8V8XdXc|cUa 0sb1c`bab'd(dkbhdC36dbb*c$36df0.d,bj6;dcd_6G0e0~010:0?2n00010Y0O0M0#7t1I080#e0dMct021/0@6Zdd1U0Ce302e59c0s0C0$en2n1R9c9e051f0$0ca5csa09ncw8Ta~07ae0m2ZeQdFd=aqd5dQ1UdteZ6/bbdmc?d:c7b)8=9*bo9Rbq8 ay0saA0raCaEaGbFaJe;0Mdca7a,eNdsb.dAd'd6bY0magaida9Ce,9MdLeq0_aO0*aRdi6V8)0n397hf1bLdgf4c+e*e(3/7 00cEf0fAb6f6d%c}dZc+dVc.eWaYdYdTfybfdle$d4d d^e.aN9?fm0LaScGaUcIb/c{fKfS8kfNd}b{f8fW7Gc^7`f7f.b$b?7HeReT7hfVfPdHd.f9dEg4fLd~cqfZeKd`cufx8kfzf)f?00dpfFgl9FfIfWdSf~7@dydWgtfRgve)fUd;gbb%dJ0 fifj6Vf$aQf'foe#g5dRgAdxf;f|d(d#8LgWg8eQ9yg2eVgFd?eYgRb~g9gEf/b%gde-bKf#8lftfefYg?c#70ese4e69be9ebedef2keigeatbLaPfnfG1Ua10~0T0L0gb#8Ze18#eMfo0sa~0i0d1{7w0i0k0775hs0r0Hf=g*g7fWgQg)eX02fgc!f!5C9Q8`e e?e^e`1Rhx9`0$0x0$huhw7x9%e fug^dhhf0_hJg:cCf}dxg$fbb!c7b(gHa@fif2cPf%f(dr6UhRaw0ybIg}ho3/d{g`fW8:ejgf3yflgNi39|7mhHfhgJiibQgsg,0_gugUc-hFdnh?ccf`86fJd(h%0rhxhzhB1{hEh{g=iqir9}0Uhr0F7+1'h{amiuhKfQf@iv37b@gyi(ixccgki(d@iah c{iUh.0Qh:gBfBgTdUizg!f^8J8WgZiGg8iIiKhA2TiNiA3YcoihgKi;5k0o6R072yeT2y6L2z6D1h2Cjt0i1Pjm6A1y2_0o0)0+0-0G02.