Aller au contenu

Parcours en largeur d'arbre binaire presque complet à gauche

Définition

Un arbre binaire est (presque) complet à gauche s'il possède toutes ses feuilles presque à la même profondeur (à 1 près). De plus les feuilles manquantes éventuelles sont toutes du même côté, à droite.

Propriété

Lors d'un parcours en largeur d'un arbre presque complet à gauche, on rencontre tous les nœuds, ensuite les nil.

Réciproquement, on peut reconstruire un unique arbre binaire presque complet à gauche à partir d'une liste d'étiquettes.

Un arbre presque complet à gauche

Pour alléger, il est inutile de dessiner certains 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(" ")
    N011 --> N1010(" ")
    N011 --> N1011(" ")
🐍 Script Python
liste_largeur = [42, 13, 7, 5, 21, 18, 17, 2, 9, 4, 1, 6]

Ci-dessus, la liste des étiquettes issue du parcours en largeur de l'arbre. On peut alors reconstruire sans équivoque cet arbre binaire presque complet à gauche.

Exercice

Coder une fonction parcours_complet qui prend ab un arbre binaire et qui renvoie valeurs, la liste des étiquettes issues du parcours en largeur de ab.

  • ab est un arbre binaire représenté avec la classe Noeud.
  • ⚠ Si ab n'est pas (presque) complet à gauche, la fonction devra renvoyer le booléen False. ⚠
###(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 : ∞/∞
.339.128013x/.Tr;nbOylaeu)dV63m(P+02è-U],59fq!78 N_o=pcwgv4F1kRéhtsSàLC[ji:E050r0o0(0n0:0m0)0N0T0m0n0)0)0R010(0:0S010406050)0p0v0v0n0g0l040*0Q0m0p160Q0i0N020n0v0S0h0N0#0o1g0g0J0p0o0)050d1d1f1h1j1b0S04051O1H1R0d1O1b0r0:0W0~1012140%0:0V0%0m1)0%0(19050_0j0m0o1!1113011(1*1,1*0(1=1@1:0(0g1P0(0%1_1$010I0{0o0i1u0o010~1m0)0S0n0i140A1:2m2o2a1{2d1@2g0v2i040b0N0x0g0Q0S0Q0)0:1p1r0@2k0g0g0o0T2M1H2t0i1P0d282Y2527261;0r2v141,0i2f2J1:1X1Z0 1`2,0:2.0i0Q2=1:0S2R1P2W2Y331c2n1r2@2b2|0g1g0m190N0Z2V371a362u391{3b3d3f0A3i2o3k2W2+013p0n3e040N0u3t2X1b3w3n143z3B0N0X3F3v373x3L3f0G3P3H3R3J3y0Q3c3A3f0t3W3l381#3o3#3q3C0L3*3I3-3K3/3%3C0M3?3Y3^3!3$3M0H3~3m403T040Z0z453,2^413:0Z3h1I3j3X464e480Z3s4j3u4l4d3a3`3B0Z3E4r3G3+3S4w190Z3O4A3Q4m4v424F3V4I4t4D4M493)4P4C3Z4o3=4V3@4n4E493}4!3 4$4S0Z444*4K3.4S0A4b4:4u4=3:0A4i334Q4X4%0A4q4 4W47524z554#4L4|4H5a4+5c3{0A4O5f4;3_4?4U5l4`5n4|4Z5q4R4|4)5v514?4/5z574S0u4^5D4,3:0u4~4k565J3{0u545N5b4{5Q595T5g5V3B0u5e5Y5m4f5Q5k5(5r5*5#5p5-5w5Q5u5=5A5K5y5_5E5K5C5}5P3B0X5H3j1S311H2=2#0r272*3Z0T2}2B0?1Y1P300o32664I056g0@6o5)0!0i190I2G0v3P5O2b0U3f6C5U3K6x046g0m1@2T0:1q1G6q6I016F3C6H5Z146w190:1v3#0(3P0N6D3o190@1D0o3W50400!193n6Y5)6W6,6T6Z3y0T190Y2e6|5.18040;3W0N7d6,6U0)2r04010-3-1^751@0N0o0I2d0T0n0T1^0n0W2S0N1@0}0I7v0{2L0$0}2O0x0l281q016?7e7f716_040@0I773x6~7Y3Z0I0v190P0P2`2L7*7#40790w7/4e0j790)0o0m7X705)790q7b4P7R7R6-147^197`7|7?2b0Q190e8c6.047*0r0n0_6+86018e040R8o6U6K6:1E8h147;0q7Q7e8p7U7W8z6V6G7~5.0i0I191F0(0P0W0:0@8I7;8I88048a7}356U80824 848E6U7U2R0(0p0g0i8u718Z8#8I8r8g8L3S7)0P8l8n4I7S5)8r0R8t958p8w0o6;8W190w8C4P06858.6/7r8I7!8 4X8O042f2x6=9s7:9h8Y7_7{8$668(190F8^5)6K250p0T9g04817c8,965.8`9E8|8f8I6K8k8m0n9Z048~8%716K0n0S0S2f0r9Q7=9z4n199N9P9`2b808D7d8F9o9F3u8p9r9-9L9u0r0$9x9^9C899Y9 1{8)9T8,a4040:a62X9V3x9X8bak148}9#8P0)8R8T8Vay018B8*4k9U84ap0g0`7`9K8M2B0s3A1E0=2Q3#agaH7h19017o1^aF1^0K7PaHa1839UaO0^8=8@9b6Uawas6u5.aAaH9$929(9*9,9G9.192I0S1@0I6*a:9h9j4 066@4e8G9paHa9b8abba1h6g8=0)0P6g1v1@bfaa789Bb2190n0j9Q9S4_7Z3f8Ea$0ra(01a/5I2b0)bR3C7e1z0i0W0Q0:7n3A7`0N2K0NbI0N0i008Q0N2n0}6m0)6;2kbA0^0N0+0N0V0n9O0%0ob74s8pbXbO7d0*2`1q0F0N2Rb$b(1^107B0:aD1^0@0}0$166;211F0N2Ob:1d2L1^c20p1r2n0gbv0g0}2f7B1h0V0o8=c94B7gbY7RbTbUaL8-b9040W3AcScMaS3x98c-3Z790.0Eanau4X890pcEc:40c/a{c%a*9^bic#a38vc{c}aHb1bD909v8N76bg049_ddc`04bIbKc^9c6y7,c~4ed033c_6^73040Yb+9y8+c$6v190U1(1@du8d6W2|bC3jdy9{8!c|0(dEbrb09!bG9vaD8S8UdXa79HdjbLdFaod8042|cS9@d197199adxdrdUdadlc d!e1dTadafdi9ic^9m7T6$a~dS3a19d?0pd^d}6U0Q6WcqdM1{0!dA0O1qd*2X8p79aK4saMeb9Lds0i0:eqazd{eI01es190f0g8ya=d:ec9v0|ewa 3xezeaa?9naqeed~2deG9QeA3GeCe$eU8:a_eLeNdBdDe#eTeEc(c*bwb6aBdn9;9?a#e4egd=0Qd@f2d#c)1@8=dpeSeCd~cDdWfdf88i9wdhfp8AbFft3yehfbejfodYdec4c6eXey19d5eBe:ef8ifmfGeme3fCdmfrdLe8f3eiekfSe29+f30r2Ge0f!4ea;d/fM6!19e?8?eL6Kffc+6S550d6s6n67f 0d6a1H0(6cg42(2ZbI1@2Y6a1NeY3Z2R0v0P7E0!0o0P0%0u191z1B6;0}e.2Y1V6j2?400n0r0v1q2L6Q1r16791N3xgBgDeG2M0C160(231k1m1ogGb/0mdW8?8m1Y1^0)2o7Ddhgx1O0,008U0$1^b@0rb?1v2e0g7Bcz0i0aej7Jg*0NcH1^0S2e0N0wh5cpcr2E7M0%1qb-0p7s2L0q7q0(cAg(c|0W2Rb/7z0Th41r2`1X7w0~7{c|0Nb}0m00hhc5aP2LcAae0{0$0e0Ncf7Bg:0ihAcs0$b_b,co7u2n0T7HhpcPb^2eci0Tb?aDhF1Eh,0S7`ej0Q0C9x7qh=a,8~gx2=3x1}1+1-1/gf409x2z2B2D0*0T0g17ho7L7Na`356ma 3466f~iabma59q8Kfw8NbtcK0Qbwby0Qb dQd+718Xd#dodid.616Ecd6 fwcc7jbTb#b%b)0NdCeWb-0:b/0jb;h;hob_b^2Rb|h@bzbcc0c2fE0Tc7cU4J5.iV7Rcf2|0icickiZcn0nhcdWhpcucw1Ecy7J7xi+fOc1hxb^buiDcM7q1r100gcRcT4c3xj17ecZdqd;fOeLdwdRfH04c?jDc%jFdbfRiJe~9:9=hWf7f+f9iNfwf-d6f/fxaq0PfYjGeKd_5.0v0:1965fKd7c%e+eHj.c.j-el7TdAi$aRfjapdJfsjId;0:j*fzfZ3uj%8r02gZ0hf@0j192yjWjR8Md9fniOgv9le;e~j+j|3ZjHkefldVfPiK190.f3kakyj!19c@fjeDkqj)kLk8718r0yd|kU5)j:4Fe|j%7Uarf@fyfckzc eof{kZ5.e_eu2.e-k%kQdej`j,8se^dAePeRf.k|3Z7U7{k3kM7ak{dGk?edk+04k~dikufLaNe%f=ink=3xe_k2eXkve:kDf*kpj}f$iMf5jVfWd#kTlAkAjQexd;i{c7fil5kwkRjOfwdcjX8ijTf6lGizk,fAjPlCl$7Vf)kslbfJe/lelsf;a^f?k.f,kHfXkcfBlJ47kmbI7{e^6ya!l`f9lIat8pen6$lqkCjEkEm5e(lhma6Xemk:jGdO0QiImb8.etev9QkOf|itg0gc6kge0D1r0Ib(0}7pcJcL0}7vc70W0$ci0{0N0lb/b/0p0NgD2`0}cH6,f~i51-1 1.2sk019k^fGf}6h3Cc2coe+h+6rm^jOitcihh7Cjs0m0B7zhu7A7p2x25csh3h$iG300$c70i2K1qhR0k1rg)hMad0/c21Dg:0mi,mWcOjai/c5m!7GcS0enI1S3kg2mEgygLgCgE2McA2ocR0g19gK3ZgMnRgGgQ2LgT0Oh611cj2fb%0l0og|m~6tlu1Hn1m!aQi:0Qb%6;g|hbn;2Rfh1U3k1OmG2k2Obc0pb`2G0I1Fnm0i2.nyhK0`hocv0$h+0@1ghWn;hx1^mI0i6Phh1D0:cinE1,cSh+j70Qn:n=itn^m@6tci30n~0Qb}o22Qc+n90ToR1h7q0c1Ai^0N82g-1Pm*3Zi6m-i9aOaQeXj%2.19aV1n0oaY2G0gkolM71a%7jg/1h0jhtb=b@i/0wb{6;hmi@bBjmlO2ilQ6pmBo6ge1c251q0V04mG0:6;2A0ibCpu0ipwb^jqi(bAarb)g|n4dWaD0)cigD160Ib^0$8l0V0Q0Vpz1Eci2|odhu6Rh4161,7`pNja0)gVnS7y7An?6noOiti2nLgd690^0`0|04.