Aller au contenu

Hauteur 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 hauteur de ab : 3

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 hauteur qui prend en paramètre ab un arbre binaire représenté à l'aide de la classe Noeud (et/ou None) et qui renvoie sa hauteur avec la convention que l'arbre binaire vide a une hauteur de 0.

###(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 : ∞/∞
.128013x,5/f.rnb No=ylaepcwgu)vd4613kRmhtsP(S0+2i:050z0r0I0q0Q0p0J0k0t0p0q0J0J0n010I0Q0s010406050J0w0G0G0q0h0o040M0m0p0w0,0m0i050e0?0^0`0|0;0s04051c151f0e1c0;0z0Q0y0!0$0(0*0H0Q0v0H0p1t0H0I0/050V0j0p0r1o0%0)011s1u1w1u0I1C1E1A0I0h1d0I0H1G1q010f0X0r0i0q0G0r010!0 0J0s0q0i0*0P1A1.1:1X1I1!1E1%1)0/0a0k0K0h0m0s0m0J0Q120i0k0T1,0h0h0r0t2a151^0i1d0e1V2n1S1U1T1B0z1`0*1w0i1$271A1l1n0#1H2x0Q2z0i0m2D1A0s2g1d2l2n2R0=1/2b2F1Y2K0h0_0p0/0C2k2V0:2U1_2X1I2Z2#0/0P2)1:2+2l2w012:0q2$040D2@2m0;2`2.0*2}2 0A322_2V2{380/0d3b343d362|0m2!2~0/0B3b1g2P152D2q0z1U2v3l0t2L1*1d3w1e3u2T162*053C0T2Q3k1p1I0E0/0T0f3s353R0*0u0/0k3X3Q2G2|0f0/0H0q110r0w0h3(2-3Z010.040L3@2W3_0i0/0q0j3~2{3{0x0R3i0k4b3%3Y3*0J1?04010F1$0y0m0Q1F0$0k3.3:3=2c1F43014a4c2,3 3*3T040Q3W3K2^4d3)2Y42444I2m4K3^3*0m3#4F0J3b4R4C1Y0E0t0/0l130r453l3{494P0:4c4=4Z2{4E2g0I3=144:4@3l0G0Q0/0N4z4b4B4^0/0r0Y4+4:574-0/4/2R064?4A4e4#0/4`4|4Y5e3_512%5r5m1I0m0/0O5w4L2/0j0/0_0b4,3_3{3}5d5x373-3/0I3;3?5N5D0*5L5J3*4104435Z1Y5z040g5(2/0/0v3/0t0H5c2T5O3`0/0x0c5C4S4M044s5S3=5-5X0/5M5^5W2|4N65015*5,5V5 5.040z24295@3L5_470x3i153N0r2n2O6w3v1m3x2q2t2o431E2n3w0;0e0T0V0X0J04.