taille récursive d'un arbre binaire (1)
Dans cet exercice, un arbre binaire de caractères est stocké sous la forme d’un
dictionnaire où les clefs sont les caractères des nœuds de l’arbre et les valeurs, pour
chaque clef, la liste des caractères des fils gauche et droit du nœud.
On utilise la valeur '' pour représenter un fils vide.
Par exemple, l’arbre
est stocké dans
Pythona = {'F':['B','G'], 'B':['A','D'], 'A':['',''], 'D':['C','E'], \
'C':['',''], 'E':['',''], 'G':['','I'], 'I':['','H'], \
'H':['','']}
Écrire une fonction récursive taille prenant en paramètres un arbre binaire arbre non vide
représenté par un dictionnaire comme vu ci-dessus et un caractère lettre. La fonction doit renvoyer la taille
de l'arbre, ou du sous arbre de arbre de sommet lettre.
On observe que, par exemple, arbre[lettre][0], respectivement
arbre[lettre][1], permet d’atteindre la clé du sous-arbre gauche, respectivement
droit, de l’arbre arbre de sommet lettre.
Exemple
Python Console Session>>> taille(a, 'F')
9
>>> taille(a, 'B')
5
>>> taille(a, 'I')
2
Compléter le code ci-dessous
.128013 kg[: r);S/(lo4y,b=ac1+ud3t2_Pevp-fh09mn]is 050y0E0A0t0P0m0Q0f0u0m0t0Q0Q0s010A0P0G010406050Q0x0M0M0t0g0p040j0n0m0x0+0n0N050k0=0@0_0{0:0G04051b141e0k1b0:0y0P0F0Z0#0%0)0#0N0c0x0t0c0E0H0G0p0A0J120f0J0P0c0J0m1G0J0A0.050U0r0m0E1n0$0(011F1H1J1H0A1P1R1N0A0g1c1B0Z0~0Q0G0t0N0)0B011T1p010I0W0E0N0t0M0E1N1/1;1_1V1|1R1 210.0a0f0D0g0n0G0n0Q0P110N0f0S1-0g0g0E0u2m14240N1c0k1B2z1)1+1*1O0y261q0P0N1~2j1N1k1m0!1U2J2L0N0n2P1N0G2s1c2x2z2$0;1:2n2R1`2V0g0^0m1N0t1E2s0I0)030C0C0u2W0E1J2U0n0H0B0H0v0.0v140t2%2*0/2)252,1V2.2:2=2@0E2_012{2}2 312M34340.0B3a3c1;3e2x2I013j0t2;1c2?0J2^2`2|2~0S3t2V3v0z0.0z3z2w3d0:3D3h0)3G3I053K3M3p3O3s2K3u350o0.0o3X153d1f2!142P2C0y1+2H3$013P221c3 1d3}2(3`3B05462#2*0f0P0y0)2|2x3v373J4j4l013.3Q3:3S35370f2a0E4m3r4w324p1N0k3b3f2+1o1V0b0.0S0I3Y3B0f4M3E0N0I0.0U0W1R4U2y4X440-040l4)4h3g4O3%0.0_0r2s4:4+4?014-0q4:4W3#4~0N0.1R1#4{4d4*542S4 0.0h0e4:0:5b4;2n4k4E4o351@4r5o4u4F304x335r1^4C4E463R5z3w2z3b0f5K534i444Q040P4T5l5M4=5e5604581)0E524}5e0n0.0s0s5$5d1`0Q4q02030z0L0i5=5@0i4|5.1V4-5i5l5k2(3D5u4n2*3T3l665w5F694B204D5v5E5y695I045L6o5U4N5e5P2s0A0x0g135T5%1`0M0P0.0K5j5}4i6b5q0H3?5t4t4v5x4H3=5B6g5D3/6R6L4J5J5L6A4P0.6u6w6y2$6q3E6C385-5N4~5)040w6;5V2-4#0V0m4(5l6$0)4-4/715~4@044_5a646=5e506`6r6|790g4`5#767d1`4-0d6H6{3i570T5!7s7h5 0.0O7r7n7t0)6/046F7E7z737B0h7g3E6@6_6z773F6}4%7m7c7F5f4.7y4Y4^7k7b3{7U7f7T7o7u7j7l7%4,0.7D7Z7L7V5Y7w7+4e7-7B7`7,7:7G6D04397K3E4-0O7O624|0k4g3|0E2z492A41142D8q0t1Q8l3~1l3e0k0S4$0X04.
# Tests(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)