Aller au contenu

Création d'arbre aléatoire de hauteur donnée

Exercice

Coder une fonction aléa_hauteur qui prend en paramètre h un entier positif et qui renvoie un arbre binaire aléatoire de hauteur h représenté à l'aide de la classe Noeud.

Dans cet exercice, pour chaque nœud :

  • La répartition des étiquettes doit être uniforme dans l'intervalle des entiers de [0..256[
  • Le sous-arbre de hauteur h - 1 sera aléatoirement à gauche ou à droite.
  • L'autre sous-arbre aura une hauteur uniformément répartie sur les entiers de [0..h-1].
  • Les sous-arbres seront obtenus récursivement avec aléa_hauteur.

⚠ Dans cet exercice, comme dans tout ce cours, on considère que la hauteur de l'arbre binaire vide vaut 0.

Un arbre binaire de hauteur 3

graph TB
    N0("11")
    N0 --> N1("42")
    N0 --> N2("11")
    N1 --> N11(" ")
    N1 --> N12("21")
    N12 --> N121(" ")
    N12 --> N122(" ")
    N2 --> N21(" ")
    N2 --> N22(" ")
###(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/.Tr;nbOylaeu)d63Am(P02-U],59fq7B8 N_o=pcwgv4F1kRéhtsSLC[i:050q0n0#0m0+0l0$0K0Q0l0m0$0$0O010#0+0P010406050$0o0u0u0m0f0k040%0N0l0o100N0h0K020m0u0P0g0K0Y0n1a0f0G0o0n0$050c17191b1d150P04051I1B1L0c1I150q0+0T0^0`0|0~0!0+0S0!0l1Z0!0#13050:0i0l0n1U0{0}011Y1!1$1!0#1,1.1*0#0f1J0#0!1:1W010F0=0n0h1o0n010^1g0$0P0m0h0~0y1*2g2i241=271.2a0u2c040a0K0w0f0N0P0N0$0+1j1l0.2e0f0f0n0Q2G1B2n0h1J0c222S1 21201+0q2p0~1$0h292D1*1R1T0_1;2$0+2(0h0N2,1*0P2L1J2Q2S2}162h1l2.252?0f1a0l130K0W2P3114302o331=3537390y3c2i3e2Q2#013j0m38040K0s3n2R153q3h0~3t3v0K0U3z3p313r3F390D3J3B3L3D3s0N363u390r3Q3f321V3i3V3k3w0H3!3C3%3E3)3X3w0J3-3S3/3U3W3G0E3^3g3`3N040W0x3 3$2/3{3*0W3b1C3d3R4048420W3m4d3o4f47343;3v0W3y4l3A3#3M4q130W3I4u3K4g4p3|4z3P4C4n4x4G433Z4J4w3T4i3,4P3.4h4y433@4U3_4W4M0W3~4!4E3(4M0y454C1M2{1B2,2V0q212!3T0Q2@2v0-1S1J2`0n2|3d3J054}0.554+0~0X0h130F2A0u574V250R395k4#345f040f2i0q0N5j4:5l1=5n3w5p5c015e130+1p3V0#3J0K4Q41135u0h0q5S0S0n3Q4K3T0X130.0F5E4o5B5o5z5q3i0F133u0Z0m0M0!0m1i0n0o0f5)3r12040v5 4R130!643`610p0,463r5C0K6g5O5-5F0$0q13016o6d3T6l396h1t0h0T0N0+1/0o1l1b0i2L0K0i2;0;6F5=0m0#6y6F2I5_5{5}0K674*5*0~6s3w6h0(1z0K0Z101x0/0#6%0$0n2A0h0#0K0.0@29106:0@6L6N0+2L0@2I0*0x0d0d0y0D0r0*6q3`6Z6h0K6o013Q7f5P485#040+5(4C5O5A3E665N7l250N130O0O7w7t010u0+134/2 7E616c4J7f7k7E7n2L0#5}0h7D5.5d0Q130L1k5X7O6h7x1=7n0n0?7(7K7Y017M7j7P6g7+7u040!0M0S5S0q7X5F7z047C7r7{3s7v887E850z836X7F7H437^7_895s7~0P0/2F8g3r85872}7s7=5s815V7:567L13636j8h8o68486a8l7P8n13805v8t3T8v8U5Q046L5^5`6-5}8L25618H7;5F8o7 818)1=8N7)8m7E5s8q105M8c7=8W8 8.5;0l5?8#6S5~8I608G8=7|8p8r8~8-8h8@2}067_7`8`130T3u5|998x89919v9p5t5v8C9d7?9c9a3T7G13784O9i9b040p8O7Q7=7n7p8X4h5R9B2i5W9D8+9D9I044k9M3T9k3d8y847A8w9.899(7J8E7=7@8^9n9o8z8R5`0Q0!8D3o89610C9V345$2A2Fa52R9/8h9x9?9z8S5T9#13a9928J138|8s9}9R5F7-7/ao047N9l9~axas040Sa2a4aBaq9ya0045U6y6-aa1=aj3oah3Mat9gaMaU7|am82aw7*7R5R0/7Va%8a047$5|a*9+699Fa`9W049r1.8(9Ga{04aNakaPaJ0oa3af5b9japa;5saRaeaB9P4P0c59544;bp0c4@1B0#4_bu2Y2T0m1-br4@1Hbd3r2L0u0M0F0m0X0n5^0s131t1v6+0@aD561O3e2,3r0m0q0u1k2F0+1k0K10611Hb!b$b(2G0z8}1}040A2(0^5_0h0Q1/170f6@5|0b1M3e1I0j1l170P2C6/b}1b0S0Z0K1.0Kb%0q0ocl2Ici0h0Z5u2G0K6~6O7(1P502-3`1@1#1%1)bF3T2r292b132x0%0Q0f116?0w0k221k5753bd2~56bocJ3`5H7o5K0f9h9`5F6f9D0h8A5v5x3!bn4~2Sc!4?5115cp3e1$040w0N6Tcscu6:0K6B0K6`6zc3cy701/58c}4/c(0Kd85Oc(4cc(0Cck1/0P1h0@2E1pcl1z6?dm2I3TcF1_1(2maP81c`b348850dc?9X5T9CdR8*a|c:8h9(9*d$9Nbl2 c|5a1Bd515d5d76Tde0i0N1g0Z29cx956Mczdwb+8q1i6(cRdk0K0,ds4~3rdKcHdN939A5TdQa}7y13dUdZ3i13a36yc0aB0v7beq7Z130V3u6/a$ar3r0X7!040e0f1yaB0Bd,bWc(d:0+d4eUd@c36B1/0F1k2Nb*6Ce06 6F6`6Pc50K0vdrdz0o0$0peaecdIcE1%dLcI8Qej5w5yemaVeodV04et0+evez9E62eyf57|0me%1k0M4cfhfeb6aXf1fj2G0Md)a68F04eP57d.brd;1Bd3bEca0K2`2B2D1/5wb b,ad0@bofS5x2h5ubB1AbX1Q1Seee~egc)48cL2t2vcPe80PcUcW0!cY4:c d-2 eS7E0Q0W13030K0)ed0tdw2L4}1E5T0Z7c7m5I7qaOeidPf4d*8Vf7fdc^dX9Zbca7d#fx7=d(bka;8v9=fr7E9^aBbV4maGaZ8Zfk0hfmeweQ4m89azeEfd9|aEa,aPfte(fvgO5Y89f g1g3ed0Idw4}2K2Mc/gQa-7oggb7gic_gkgv9:04epfo5sfafcfo8+fgglc*eJeCaAgUbfeG5!eJeLeNhefz6b8OfsgLgNhl0vgP4vg@7.gTh613gG3AgI65gKfufw2Rgt62hu145Z3`g)04g2g42I0)dw0$0#0kcle#b 2G2(0lgdabhFe(gz7AbgdWf39DdTf8h4gsfyexf8gZflfnh98MhfghaHh}gMhHf*d!hmh)erh+f^hzhKc{eS1O4=bsd1d00T3ebs0/0;0?04.