http://blog.csdn.net/yixueming/article/details/42033421
完全二叉树是一种很特别的树,很多性质和特性值得我们关注。下在就来关注一下叶子数目。
如果一树是是完全二叉树,结点数为n,叶子是多少呢?现设结点总数为n,度为2和0结点数分别为n2和n0。下面讨论叶子数目。即计算n0值。
我们根据完全二叉树的概念,可以知道,完全二叉树有两种可能:
1.一种是:没有度为1的结点,只有度为2和0的结点 此时有: n=n2+n0 (1)
根据二叉对性质知:n0=n2+1 (2)
联立(1)和(2)得:
n0=n+1/2
2.一种是:有1个度为1的结点,其它度为1和0.
此时有:
n=
n2+
n0+1 (1)
根据二叉对性质知:
n0=
n2+1 (2)
联立(1)和(2)得:
n0=n/2
再进一步分析上面两种答案,我们知道,完全二叉树叶子只能出现在最后两层。也就是说,如果共有k+1层,则前k层一定是满树,对于满树知道结点数为2的k次方减1,为奇数。
对于情况1,第k+1层是偶数个叶子。
所以,情况1,n一定为奇数。
对于情况2,第k+1层是奇数个叶子,所以,
情况2,n一定为偶数。
因此得出结论,对于结点数为n的完全二树,叶子数目是:
当n为奇数时:n0=n+1/2
当n为偶数时:n0=n/2