Aller au contenu

Un arbre binaire est-il un peigne à droite ?

Peigne à droite

On dit qu'un arbre binaire est un peigne à droite, si pour tout nœud, le sous-arbre à gauche est vide.

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

# ab n'est pas un peigne à droite

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 est_peigne_droite qui prend en paramètre ab un arbre binaire représenté à l'aide de la classe Noeud (et/ou None) et qui renvoie un booléen : True si ab est un peigne à droite, False sinon.

###(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.T78rnb N_o=ylaepcwgu)vd46F13kRméhtsP(S2i:050B0t0M0s0S0r0N0l0v0r0s0N0N0p010M0S0u010406050N0y0J0J0s0i0q040Q0o0r0y0.0o0j050c0^0`0|0~0?0u04051e171h0c1e0?0B0S0A0$0(0*0,0L0S0x0L0r1v0L0M0;050X0k0r0t1q0)0+011u1w1y1w0M1E1G1C0M0i1f0M0L1I1s010d0Z0t0j0s0J0t010$110N0u0s0j0,0R1C1:1=1Z1K1$1G1)1+0;0a0l0O0i0o0u0o0N0S140j0l0V1.0i0i0t0v2c171`0j1f0c1X2p1U1W1V1D0B1|0,1y0j1(291C1n1p0%1J2z0S2B0j0o2F1C0u2i1f2n2p2T0@1;2d2H1!2M0i0{0r0;0F2m2X0=2W1{2Z1K2#2%0;0R2+1=2-2n2y012=0s2(040G2_2o0?2|2:0,2 310C342{2X2}3a0;0b3d363f382~0o2$300;0D3k2.2Y1r2;3p2?040g3u373x393z3r040h3d1i2R172F2s0B1W2x3n0v2N1,1f3P1g3N2V182,053V0V2S3m3F010H0;0V0d3L3E2I010w0;0l3@3-3_0j0d0;0t0N0M0n0u0t1v2B0n0B262b0t3~2/3.0:040P4h3w400;0s0k4n2}4k0z0T3k0l4z3}3^1!0N1^04010I1(0A0o0S1H0y2d0k0o110K1(014y4A3v2}3:040S3?3%2`4B3 2!4q4s4(2o4*4i3_0o3{4#0N3d4;4o1!0H0v0;0m154g4/3,4=1!4k4x55064A5d4|4Z0;2i0M0y0i16555f3n4 0;0f0i0y542T5c4X4C1K4!0t1y4%2T5o3.0j4-4t3n0o0;0e5K5H0;0x0s0y0v0L5v2,5G4?4^0S4`5n4Y5L4^2M0M4{5)3.5q04522B5P3_594W5e5Z4~5h0W5k5m5F5/3_5;0E300N5X2`5x4z645~045C695^580;5a5w5|6d5z0,4!5i615.6q2~434547490x4b4d4L0M6a2o6e1K4k4m556J395J6N6w5M045O6R4+2;3;4e6G6j6K0;0z3u0c3*0t2p2Q6-3O1o3Q2s2v2q4r1G2p3P0?0c0V0X0Z0N04.