Aller au contenu

Un arbre binaire est-il parfait ?

Définition

Un arbre binaire est dit parfait si sa taille est maximale pour sa hauteur.

Toutes ses feuilles sont à la même profondeur et il n'en manque pas.

Un arbre binaire parfait

Pour alléger, il est inutile de dessiner les nil dans ce cas... Ils existent néanmoins !

graph TB
    N0("42")
    N0 --> N00("13")
    N0 --> N01("7")
    N00 --> N000("5")
    N00 --> N001("21")
    N01 --> N010("18")
    N01 --> N011("17")
    N000 --> N0000("2")
    N000 --> N0001("9")
    N001 --> N0010("4")
    N001 --> N0011("1")
    N010 --> N1000("6")
    N010 --> N1001("13")
    N011 --> N1010("13")
    N011 --> N1011("4")

Ici, un arbre parfait de hauteur \(h=4\),

  • il y a \(2^{4-1}=2^3 = 8\) feuilles,
  • il y a \(2^4-1=16-1 = 15\) nœuds.

Exercice

Coder une fonction est_parfait qui prend ab un arbre binaire en paramètre représenté à l'aide de la classe Noeud et qui renvoie un tuple (h, perfection) où h est la hauteur de ab et perfection un booléen :

  • True si ab est parfait,
  • False sinon.

⚠ On demande de coder une fonction qui est indépendante des fonctions hauteur et taille, donc sans utiliser directement une formule. On n'attend pas un simple test \(n = 2^h-1\) !

###(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 : ∞/∞
.129668.128013x/.Tr;nbOylaeêu)dV6çz3Am(Pô+02è-U,59fq!7B8 N_o=pcwgvF41kRIéhtsàSCDi:E050s0o0.0n0@0m0/0S0Y0m0n0/0/0W010.0@0X010406050/0q0z0z0n0g0l040;0V0m0q1a0V0i0S020n0z0X0h0S0*0o1k0g0N0q0o0/050d1h1j1l1n1f0X04051S1L1V0d1S1f0s0@0#121416180-0@0!0-0m1-0-0.1d050}0j0m0o1(1517011,1.1:1.0.1_1{1@0.0g1T0.0-1}1*010M0 0o0i1y0o01121q0/0X0n0i180F1@2q2s2e1 2h1{2k0z2m040b0S0B0g0V0X0V0/0@1t1v0{2o0g0g0o0Y2Q1L2x0i1T0d2c2$292b2a1^0s2z181:0i2j2N1@1#1%131~2:0@2=0i0V2_1@0X2V1T2!2$371g2r1v2{2f300g1k0m1d0S0(2Z3b1e3a2y3d1 3f3h3j0F3m2s3o2!2/013t0n3i040S0x3x2#1f3A3r183D3F0S0%3J3z3b3B3P3j0K3T3L3V3N3C0V3g3E3j0u3!3p3c1)3s3)3u3G0P3.3M3;3O3?3+3G0R3`3$3|3(3*3Q0L423q443X040(0E493:2|453@0(3l1M3n3#4a4i4c0(3w4n3y4p4h3e3~3F0(3I4v3K3/3W4A1d0(3S4E3U4q4z464J3Z4M1W351L2_2)0s2b2.3%0Y312F0`1$1T340o363n3T054%0{4/4O1 0)1d0{0M4;3{4i0Z3j4 434r0M1d1J0.0U2r0g0M0~0.544_181c040A5h4y3s1d0n0j5n3B5k0r0^4g3B523G0S5C5t3%0/0s1d015J5y5F5H5B5C1D0i0#0V0@1|1{0S0.0q0X5W0A0-0J0S0X0o5d2W2Q0r5L445G3j5C0S0H0S2d590S145`0n1s0o0q0g0S2S5r5:4i5=5O5^5)5+0M5-0@1u0S5|0q1v0j0V1q0,2j5(0f0g1I0S2O0S5r6j0/0.5)1l5e2P5(0$3E0/1|2O300i682f6a5@0S5J013!6S4G3%0i1d0y0Q0U0t0+0?0_3T0S6Y440V1d0W6-6/4i0)0Y1d0T1u0o6W5@6^2f4{040@4~4M6.503e5q5s78721 0V5A0@1K7e7a5p046$6(6*6,4T7m5j1d5x4M066S6X7u01742V5Y0g6O7l552f5k5m7t7K1 0z0@1d4f7O5i015k0J6@7C6`1d6t1I5E445v705D7#58106 7V5o7v047x377z7A7.7P3O1d0-0U0!7*4i7Y7!7 3C1d5*5d83600Y0-7=3779896;046?7J7W6!04595b6E5f857L1d7N397C8r677?3B8m0e8x7n0!8f8h8J7^5/7y7}7~8q810U0s8O7X1d7Z8p7@8a048c0M8W2K2P8i3n8k7W8m8o8j7f808s6B8u5d8w8F3%7M8Y8D7d8B8l1d8I904b4|8-0.8/3y8_8Z048Q7{8S8;8%8r0-888=6=9r8%7R4J9u8G1d0D9y6Z0j1d1k0c8Y929a4r8V849K8y048#8^8C8V8X9O1 7,8R8S9h8r8*6g1u9C6:9t8$3W8b6e8e0q8g9f2#9n8G5A2s9V9S899$9:0s9d9@3G9h7h5q0i9}8:9h9J968U04829N9~9s8n8@ab9Tag8W9I1d9k4o9m9h7E0|637Iaj8%ad4:ao9q9W7^9Ran9 9/5,2X6haAaE899Y7{1L4?4.4UaX0d4X1L0.4Za$2,2%5r1{2$4X1R4^8%2V0z0U5e0)0o0U0-0x1d1D1F1H1J0S7`4:1Y3o0{0}0 113%0s2s0!5+1d3L1i1F1n0t5+2O6i0z31760@6q5(0n0#2W6j2U62645S0m1uba2V2Zbk1P3o1S0I2=0S5e0v6i0,0m0,8L0i9e5)0V630S0g0,0/b#a25V1|340V1`0G2E655V0n6daN2Q6A6C2Sbr1#2h5+5}b_0M1uaO6i4=4(ag609e63aVcb6j1vca4@0-cdbC8}6F5g0daW2$1Z050q0m3o1:046i2V5R5T1|6l0@b22EbYc45 61b$2Sck4.8Ect6D160,ci6D0g1y0G290o8#cA1fcA1g291u0!041k7j2Zc.0ic:0S6ib/5Sb20S6l1|5+2Vb$6xcR04cTch0i005|2r115ccq99c*1Lcxb81$3B211/1;1?a;3B2B2j2l1d2H0;0Y0g1b6C0B0l2c9)4T4-a;384:ctaw4|0o77ae8%5A6.aH3C57cccO0gcp8 dT5u8z937car9jb54w7B890/2v04015Q5S5UcMcmd#b@6y0j5(c}0Vc d1bAd4646x6zdbdd15cZcq6V9Z8T8%74769*9Ld895aK8=7i7kaB3B7$046}2=d.d:3Kav7/047Fazep2f9w047U9l71eH0o7;eD7-7A9#9MeL7g9,ex6Z81cn63d%2Pd.8AaRaf8Ed)3%8Hd,048L9=8NdXaT8:9_4$0(1d030S0A0(0r0OeWd=af82aa3yf19+8ne!8`d ced$dgd(e:aCd+dX948Ye^fu9c5T9ed.atfgfh4i0Yf304f50A0Ff9fbeR89741~5+cre%9bapaiet8%8?amfgeYapff2#ac8!fk01d@5I0m001l0j2V0See6BcVeh5fej8jfF2ffHf4f60xfNekeXeHeJ7Hf.eN4mfV4i8m9B9-e(fX3.cscbaYa.4+1f1qcz0@1o0@120|6y0X5*0mf`b.2Kc~6vde65dcbB635(0Ydcf|c d75r0ee{9?cg4@b}f~e-0ddjcA0;gz0YgB0ngDeTgG5)gIe6gKeg0sgNeagQgS6CgUctgWa2fA7=cUef8~g(g*gx0a0S0=h065c7cM6Kcx1|c0bt0Y0nb|0:gC2M0g9e64602o2S2S5~c60ic8cjctfmbCg!4.0e0S0a1Ldj0dgva:0B1r110}0g0s5(5S0q11g:4-a92V0w0Sht1s0 7jc3d7290l6j0cg.0XcrcU2SbR6iht4%0i6B6u0@f_06hDc7b|d78tfpg(cU5e0Y2icK6Cht5c1a64cQhIe*fo8vihcb99cv1S0t5Tikd0bPby0gbpcji6c/042O1z1:2h6qc@2Kc_3G1Hgz5|290G11dR2hhqg.6j6CbUbW2sbZ7xcv2_do1;231=2w89dv2D2FdzdBdD2IdG0-dI39dK3/dM9gdOeH4}8YdV93dZifiwfUfrd*5le_e=jm91aseE1efcem1dh^eVg9jw9.agf.8?f.9piue,jl9g7CaDjMaLerfCfOeley1dgcaQf%7#6{047(a4fP7Wg4fJf6f8fag9dP8sh{0oh}jAeQ7}j;jXf.ez6IeU78g21 j+fKfMj/aUgp4@gr4Wgt05hT05cA0y9=e8d3bCg?0/hhb/0s0q8.0S1BgV7dh8f|igcrhc04bOd2gOebkq2Kkskukwh3kydakqegkBhQgx1fhScyhUb#640pc%5)hWb%1-k!620c5(6ih:1:6KiF6.ctc!h=hL3GbxbzklkHhi0Y1i2j0.6qhN0k1v5~b(l30X0Gf_3E3)11i.1{im6yby0Y5}1|6n1v2Bc%l8lahnbG2Vc!0S0j5UbY0C6C0A2j2oiP0,im0riz3oa!0|0~10lQb9lT0/04.