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
.128013l(9 _4:;=vm26-uS8w.Rs3/fr7gebhpPicé0N5qa,onkyd1)t050U0C0X0O0H0b0v0e0I0b0O0v0v0j010X0H0F010406050v0p0l0l0O0z0T040q0Q0b0p0=0Q0R050x0|0~10120`0F04051i1b1l0x1i0`0U0H0k0*0,0.0:0,0R0B0p0O0B0C0o0F0T0X0E190e0E0H0B0E0b1N0E0X0^050#0D0b0C1u0-0/011M1O1Q1O0X1W1Y1U0X0z1j1I0*150v0F0O0R0:0m011!1w010y0%0C0R0O0l0C1U1_1{201$231Y26280^0a0e0G0z0Q0F0Q0v0H180R0e0Z1@0z0z0C0I2t1b2b0R1j0x1I2G1:1=1;1V0U2d1x0H0R252q1U1r1t0+1#2Q2S0R0Q2W1U0F2z1j2E2G2-0{1`2u2Y212$0z0 0b1U0O1L2z0y0:030f0f0I2%0C1Q2#0Q0o0V3b0^0e0V1b0O2.2;0_2:2c2?1$2^2`2|2~0C3001323436382T3b0o1~040e0m3h3j1{3l2E2P013q0O2{1j2}0E2 3133350Z3A2$3C0w3e0w3I2D3k0`3M3o0:3P3R053T3V3w3X3z2R3B3c0g3e0g3*1c3,3m2=1v3p0Q2_3Q3s3U3u3W3y3Z3|3#3c0M3e0M422-3-2;3N3;4c3^3x3Y374i3a3c0n3e0n4o443.473:493r3S3t3v4w3{393C0A3e0A4F3K4q3n4I3O4K4b4M4d4O3`4h4R3c0r3e0r4W2F4Y462Z4#4a3=3@4e3_4g4y4-0o0d3e0d4=3L4r3/4`4L3?4N4f4x3!4A3b0K0^0V0K574@4s4$4|5e4 5g4z3C0V0V5l3g0x3i3+4X455q4{4u4~4P4,3}3b3E0V3H5C3J4?5G5a4t4(4v4+515N0V3%045%5o5V4!5X5d4)5f4Q5$3 5)415S5E5U4H4_5.4}4*505h5x4l5)4n5`435F5}2@5r5J615v520V4C5)4E684p5,5~6d5Y5K5!633c0V4T5)4V6m4G595-6q5/5Z625w6v4/5)4;6A6a6C6p5I6r6f5=4j3b545)566N5|6P6c6R6F6s6H520m5k046-5+6b486(605;5M6V0m5z6/5B5D692F1m2+1b2W2J0U1=2O5a4x2V1s1j2*0C2,3k5{1j4x7i2c0H0U0:332E5x3s7p7r6+5$1 2h0C7x6g7z2G5D6=0:0S0^0Z0y7k6o210s3e7O7I3O0y0^2R0v0C2z7T6$1$0@040c7$4Z5~0^100D7#717n4^217)0P7k0e7P3p0^0+0C7,7^7(0^0W0h7k0`7?5G7w017s2;3C3E5d8d6t6I3D7A277C8e7y6{1U5`7U7R3F0e8z833N0v0U0^020N0p0Q0X0i8G8I8K8M8J0i7Y7!1Z0,1u1Z0U1{0)0b02030w0d0i7:2z0e0D2R0$8,2w2z0I0E7!8@827?8a2/3M8k0f7t3c5(8j7q8r7E6V3%0e7B7D6U5i948v7%0:8D3e8z0e2z2*0J7Z0R0X0J0e1`0z0e8+0C0t898B90920o5@959d6`5i3 9b8p9J5#6V9H9h7-219k8y8z0u0!0Q0p0z2S0e8#8%8)9z0e0l2%0H230J0t8P8O8H8Q9^0i9C8b8 968f1{3C659I979ea48o289P6u0oa55S9m7}7U7K049;7|7~3:7/0z7;8{2-ai9i010Q0^0j0janaj0I0^0L19at7j7U7)888|9Da1918g4B7vaP985i4C9Naba79K3C6j3Iahahao01ak2z0X9$1a7?av9U7 04aG0C0p0U8B5a7)7+9 aw0R801Ya~4!7`aCaw0SaEa_aHb74_b9a=a+bcaFbfb2a@0:7)0Wbabp010I6}030*2z0O2t2v8$8(0i0p9(0ya{0%b6aNbo2u9EaR0o6xa68l524TaY8qbV5NbTag9mbk0^377Zbg7_0^aM6nbO0ebQa34.aTac8m4/bYb{526Ka(a)8Aaj7X7Nbj7Ub40481bt840:ay04020b8Kcd4saqasb-1$cg9Bb=5Wb*0=8H0!0XaI3Ka+aL7|8}aJ4rb@0R3C6XbU8s5i54b~a!9QcO8u3ic3c3a+ca9zcpcf0^cs8~b30^0B0O0p8`cl5acgaBc8c*al0R7Z7=c)bub0c#3Ocnc|cGbucrd0cac,c.8^d0biaucYb5cA72aK869~c}bPaP9F5mb`cRaddqcQb!6Vdq7G9Xa)b)04b+dh7@3NcDbNdmb?dobR5ydrdw5idOdvcN5x6}c2cWb(c9d2dFa+d6ct5-7L2n2sc:4!c=d.7.c_c{d$dj7*d7d#d0d(dKcu040Ud,0Xdc0^7{c@bucaccd)bhdka=cFcBa07xdp8i2}90aV5x1~dTeo6v8ib%cXc504a.a:d;2@d|dJd4dnejdN94emaUa86v9a9cds8m5%cU3lb=cI5x9HeKb 5?aabZdU6v9S7Hc^0OeBcqaze.apbea{a}ecb.d`e_1$0l0H0^67d b8e6e;a,bdaG2Se504e7deaDbmf9e|bqeeb;dKeW6va5eZeQ6h4lereM3bafe+e97/f5d:e8ced1d?8Tfab1f2d=e-fh01dd3ka?fDe~0^5RfJe`bseEehcHdMb^3ba%fpdQ5xaXePf*6va%9TfDcZfAe:fCcmfFd3fZc~0^fIeFf`fLfV85fbf5fS043)fMbrdlg1fm3bbTf)e(gge$e!dxb$fxf=fzf_c;f^fdc^8Sf|diawc fMf?gbf4gs4!g86zg4fi04fXfkgef#cJ6JdPgj0Vb}f-gUc1f;g2f@04c?gvfyf{d^gAf d{04g3g1a gFg)fRe 5)fagN44eVgQ5xcLgies6Wglfq5$cLg!e0g;3KfQ3NfBg^f`gxg,f~e{gKfEhcgzhlfcfPa+g85_hngcfYhqeG8r9F6-gTh4hEfta#3chEdzdfg:g$g(htd!g+fHg/hpdGg?g6gG4_g86lhxfjg~flh0hKdWh3fu6|h6f.3DdWhad*hOh!21hghRgwc`fGgEhmg=h`hWcCg@h bug86Mh(gMgdcB0x7m737h757e1b0X78io2M2H0O1Xil0x768a0Z0#0%0v04.
# Tests
(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)