Aller au contenu

Taille d'un arbre

Un arbre binaire

graph TB
    N0("11")
    N0 --> N1("42")
    N0 --> N2("11")
    N1 --> N11(" ")
    N1 --> N12("21")
    N12 --> N121(" ")
    N12 --> N122(" ")
    N2 --> N21(" ")
    N2 --> N22(" ")
🐍 Script Python
N_11_bis = Noeud(11)
N_21 = Noeud(21)
N_42 = Noeud(42, None, N_21)
N_11 = Noeud(11, N_42, N_11_bis)
ab = N_11

# La taille de ab : 4

Construction alternative

On peut aussi construire cet arbre avec le code Python :

🐍 Script Python
ab = Noeud(11)
ab.droite = Noeud(11)
ab.gauche = Noeud(42)
ab.gauche.droite = Noeud(21)

Exercice

Coder une fonction taille qui prend en paramètre ab un arbre binaire représenté à l'aide de la classe Noeud (et/ou None) et qui renvoie sa taille.

###(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 : ∞/∞
.1280135/f.rnb No=ylaepcwgu)vd4613kRmhtsP(S0+2i:050x0p0G0o0O0n0H0i0r0n0o0H0H0l010G0O0q010406050H0u0E0E0o0f0m040K0k0n0u0*0k0g050c0;0?0^0`0/0q04051a131d0c1a0/0x0O0w0Y0!0$0(0F0O0t0F0n1r0F0G0-050T0h0n0p1m0#0%011q1s1u1s0G1A1C1y0G0f1b0G0F1E1o010d0V0p0g0o0E0p010Y0}0H0q0o0g0(0N1y1,1.1V1G1Y1C1#1%0-0a0i0I0f0k0q0k0H0O100g0i0R1*0f0f0p0r28131?0g1b0c1T2l1Q1S1R1z0x1^0(1u0g1!251y1j1l0Z1F2v0O2x0g0k2B1y0q2e1b2j2l2P0:1-292D1W2I0f0@0n0-0A2i2T0.2S1@2V1G2X2Z0-0N2%1.2)2j2u012.0o2!040B2=2k0/2^2,0(2{2}0y302@2T2_360-0b39323b342`0k2Y2|0-0z391e2N132B2o0x1S2t3j0r2J1(1b3u1c3s2R142(053A0R2O3i1n1G0C0-0R0d3q333P0(0s0-0i3V3O2E2`0d0-0T0V1C3$2+3X010,040J3/2U3;0g0-0o0h3_2_3?0v0P3g0i463#3W3(0H1;04010D1!0w0k0O1D0!0i3,0n1C2a1D3~0145472*3`3(3R040O3U3I2?483%2W3}3 4D2k4F3:3(0k3Z4A0H394M4x1W0C0r0-0j110p403j3?444K0.474-4U2_4z2e0G0u0f124+4/3j0E0O0-0L4u464w4:0-0p0W4$4+534(0-4*2P064.4v494W0-4=4@4_2P4{3;4}2#4T5a3;0k0-0M5t5i2-3+0U4o582R5A0(3?3^595H2`4I4%5v0-0e5P3(3|040t0o0u0r0F5F3J5M425z4G1G5w045y4`5u5U5C3-5$2?5;1W5J5T4H043~5}5,5R61353S22275^2k5`1G5)4+0/0c3L0p2l2M6i3t1k3v2o2r2m3~1C2l3u6f0R4n0H04.