Insertion dans un ABR (4)
Un arbre binaire est soit vide, représenté en Python par la valeur None
, soit un nœud,
contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance
de la classe Noeud
donnée ci-dessous.
Python |
---|
| class Noeud:
"""Classe représentant un noeud d'un arbre binaire"""
def __init__(self, etiquette, gauche, droit):
"""Crée un noeud de valeur etiquette avec
gauche et droit comme fils."""
self.etiquette = etiquette
self.gauche = gauche
self.droit = droit
def parcours(arbre, liste):
"""parcours récursivement l'arbre en ajoutant les étiquettes
de ses noeuds à la liste passée en argument en ordre infixe."""
if arbre != None:
parcours(arbre.gauche, liste)
liste.append(arbre.etiquette)
parcours(arbre.droit, liste)
return liste
|
La fonction récursive parcours
renvoie la liste des étiquettes des nœuds de l’arbre implé- menté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.
Compléter le code de la fonction insere
, qui prend en argument un arbre binaire de recherche arbre
représenté ainsi et une étiquette cle
, non présente dans l’arbre, et qui :
- renvoie une nouvelle feuille d’étiquette
cle
s’il est vide ;
- renvoie l’arbre après l’avoir modifié en insérant
cle
sinon ;
- garantit que l’arbre ainsi complété soit encore un arbre binaire de recherche.
Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci- dessous :
flowchart TD
A(5) --- B(2)
A --- C(7)
B --- D( )
B --- E(3)
linkStyle 2 stroke-width:0px;
style D opacity:0;
Compléter le script ci-dessous
.128013kg: r);SĂ©/q(N.lo4y,6b=ac15ud3t28_Pw7evp-fh09mnRis050C0L0E0x0W0p0X0e0y0p0x0X0X0w010E0W0N010406050X0B0T0T0x0f0s040i0q0p0B0=0q0U050k0|0~10120`0N04051i1b1l0k1i0`0C0W0M0*0,0.0:0,0U0c0B0x0c0L0O0N0s0E0Q190e0Q0W0c0Q0p1N0Q0E0^050#0v0p0L1u0-0/011M1O1Q1O0E1W1Y1U0E0f1j1I0*150X0N0x0U0:0F011!1w010P0%0L0U0x0T0L1U1_1{201$231Y26280^0a0e0I0f0q0N0q0X0W180U0e0Z1@0f0f0L0y2t1b2b0U1j0k1I2G1:1=1;1V0C2d1x0W0U252q1U1r1t0+1#2Q2S0U0q2W1U0N2z1j2E2G2-0{1`2u2Y212$0f0 0p1U0x1L2z0P0:030H0H0y2%0L1Q2#0q0O0z3b0^0e0z1b0x2.2;0_2:2c2?1$2^2`2|2~0L3001323436382T3b0O1~040e0F3h3j1{3l2E2P013q0x2{1j2}0Q2 3133350Z3A2$3C0D3e0D3I2D3k0`3M3o0:3P3R053T3V3w3X3z2R3B3c0r3e0r3*1c3,3m2=1v3p0q2_3Q3s3U3u3W3y3Z3|3#3c0A3e0A422-3-2;3N3;4c3^3x3Y374i3a3c0u3e0u4o443.473:493r3S3t3v4w3{393C0K3e0K4F3K4q3n4I3O4K4b4M4d4O3`4h4R3c0G3e0G4W2F4Y462Z4#4a3=3@4e3_4g4y4-0O0S3e0S4=3L4r3/4`4L3?4N4f4x3!4A3b0R0^0z0R574@4s4$4|5e4 5g4z3C0z0z5l3g0k3i3+4X455q4{4u4~4P4,3}3b3E0z3H5C3J4?5G5a4t4(4v4+515N0z3%045%5o5V4!5X5d4)5f4Q5$3 5)415S5E5U4H4_5.4}4*505h5x4l5)4n5`435F5}2@5r5J615v520z4C5)4E684p5,5~6d5Y5K5!633c0z4T5)4V6m4G595-6q5/5Z625w6v4/5)4;6A6a6C6p5I6r6f5=4j3b545)566N5|6P6c6R6F6s6H520F5k046-5+6b486(605;5M6V0F5z6/5B5D692F1m2+1b2W2J0C1=2O5a4x2V1s1j2*0L2,3k5{1j4x7i2c0W0C0:332E5x3s7p7r6+5$1 2h0L7x6g7z2G5D6=0:0b0^0Z0P7k0e6o2@0P0^2R0X0L2z7k7Q1$0@040m7Y7I3O0^100v7X717n4^217#0t7O7Z3:0^0+0L7(6$7!0^0g0d7k0`7/5G7w017s2;3C3E5d886t6I3D7A277C897y6{1U5`7)0J3e0e8u7~4Z4_0X0C0^020l0B0q0E0h8C8E8G8I8F0h7U7W1Z0,1u1Z0C1{0)0p02030D0S0h7,2z0e0v2R0$8(2w2z0y0Q7W8:7}7/852/3M8f0H7t3c5(8e7q8m7E6V3%0e7B7D6U5i908q7 0:8z8t8u2z2*0j7V0U0E0j0e1`0f0e8%0L0o848w2u8|8~0O5@91996`5i3 978k9F5#6V9D9d8x219g3F8u0e0V0!0q0B0f2S0e8X8Z8#9u0e0T2%0W230j0o8L8K8D8M9=0h9x868{928a1{3C659E939aa18j289L6u0Oa25S9U7P7)7K049.7^7)0U7+0f7-8@2-af9e010q0^0w0wakat0b0y0^0n19aq7j7)7#838^9y0e9A8b4B7v9~8n5i4C9Ja8a49G3C6j3Iaeae7_01ah2z0E9Z1a7/as9Q3paD0q0L0B0CaM5a7#7%9|atam047|a|4!7?aza=7JaC04aE2Sb54_b7a:a)aBa@beb0b9017#0gb87;1$0y6}030*2z0x2t2v8Y8!0h0B9#0Pa_0%1Y9{8`4raOa03c6xa38g524TaW8lbU5NbSad9Ubj0^377Vbf7=0^aK6nbn9zaS9B6KbTaT3C4/bXa98hb^b$a%a;bt7J7T7Nbial7{bLc8atav04020p8Gbs4sanapb,1$ce9wb;ck040!0W8D0!0EaG3Ka)aJ7O8_aHbOb?aP53aRb~5254b}aY9M5i6Xa$c2a%a)b29ucn0:cpcZ7*040c0x0B8?cj5aceayccbob28O7.bNboa~c$cXaoc^cFboc#cr5W0^c)c+8;c$bharcWcacz72aI81bMd0b=7x9B5mcKcPaadncObZ6Vdn7G9Tc2b(ct0(de7:3NcCaLcrbP0U5x6}b_945i5ya7bYb`6vdLc1cU8vc904cYd34!d2c_c4c%0C2n2sc-d$awd.5~7T0U7Vc cAdg7$c|cld_dfcd0^cqd(csd+0qd-d#bg0^7@c;d)b2b4e9b-04bra:cEd`cGdlcI5QdodtdO1~dsdS5O8p3idWdza,a.d;2@d~dCeme07ocHbQ3b902}8|dN5x9698dp8h5%ez3ldHeMdJ6v9DeQaSeSe(dQcL5?eZdcdZeFcod:edcsaEa_a{eh80d|e 0:0T0W0^67e4a}ebe@babldCcBfae`5abkbcaFd9dhdGe4dI64esex0z4lewe,3bac7Hb17+fbaue_dbdYc@fed{a f85-fCf2bpfgfGatf40^5RfMeaejdieneLepeN6ifsfxf)fwa56va#9PeefOfSd1fF3kc3csfIfmf1fXeGe?fPdaf`a)fU043)g3fnb:fpe$5xbSe*e/dubWeVetgfe;dY0xfDc/fDc?d@8Pf~fLdjcsgqga04ecf@d)g76zg0f0ekgcgzfq6Jf*f.3bb|glftc0fAc=f?g57)gsfhfNaigvd dDf9f gzd4g2gJ0:g43Kf{5ag75Bg=fQfZfogNge6vcSgheW6hcNgUf+cSf;gAgrf_g^e=f}gCgyf#f=g;g/b6fRg!fTf5045_g}bqf!eKdk8m9B6-gQaZ3chDf-hF3D6.3*gphe04c:gFf|g*fJatc{fPcXf~gEhrbog76lhwgb44e#f%e%3DdLh5gmhG5zhIcQ8cdUgXhmgBhRc.hf2Fg_g(hih)g.hlhdgCh!hg7)g76Mi6gLh+2/0k7m737h757e1b0E78iq2M2H0x1Xin0k76850Z0#0%0X04.
# Tests
(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)