為什么在任意一棵二叉樹中，葉結(jié)點(diǎn)的個(gè)數(shù)為n1,度為2的結(jié)點(diǎn)數(shù)為n2，則n1=n2+1

上面說的是滿二叉樹，人家問的是任意二叉樹！

這個(gè)問題書上證明了，求分支數(shù)，然后就得到結(jié)果了。

對一顆n高的樹來說，葉節(jié)點(diǎn)只存在于第n層，二叉樹第n層的節(jié)點(diǎn)數(shù)=2^(n-1)，所以一顆滿二叉樹第n層節(jié)點(diǎn)數(shù)為2^(n-1)，除第n層外的所有節(jié)點(diǎn)都是度2的節(jié)點(diǎn)，總數(shù)為2^n-1 - 2^(n-1)

2^(n-1) - [2^n-1 - 2^(n-1)] - = 2^n - 2^n + 1 = 1

每個(gè)葉節(jié)若增加一個(gè)子節(jié)點(diǎn)，則該節(jié)點(diǎn)變?yōu)槎?節(jié)點(diǎn)，度2節(jié)點(diǎn)數(shù)不變，同時(shí)增加的子節(jié)點(diǎn)變?yōu)樾碌娜~節(jié)點(diǎn)，所以仍有關(guān)系式n1=n2+1，若增加到2個(gè)子節(jié)點(diǎn)，則度2節(jié)點(diǎn)數(shù)增1，葉節(jié)點(diǎn)數(shù)也增1，關(guān)系式還是不變?yōu)閚1=n2+1

所以可得