求在一个有N个节点的正规二叉树中的叶子数M，我自己只能举例找规律求出来M=(N+1)/2；可是具体证明就不知道该从何入手了，请大家帮帮忙，给个证明思路。

不好意思，是正则二叉树，嘿嘿

什么叫正则二叉树.
我可以证明完全二叉树的.

[此贴子已经被作者于2007-11-10 22:25:15编辑过]

不过MS一般二叉树没有这个规律

如果是完全二叉树,我再来证明

二叉树?是什么,没听说过啊,去找找资料先

假设总结点是N个
度为i的结点个数分别是Ni个,则N=N0+N1+N2
根据完全二叉树N1最多为1
由由二叉树是由树枝来连接的,所以N=1+N1+2*N2(其中1表示根不要任何树枝来连接,度为i,必定发出i个树枝)
结合两个式子消除N2,得到N=1+N1+2*(N-N0-N1)化简得到
2*N0=1+N-N1;由N1<=1,所以得到N0=(N+1)/2 //可以证明N1=1时,N是偶数,相反N1=0,N是奇数