设一棵完全二叉树共有700个结点,求该二叉树中叶子结点的个数。

来源:百度知道 编辑:UC知道 时间:2024/06/17 14:46:31
想各位朋友求助~~

根据“二叉树的第i层至多有2^(i − 1)个结点;深度为k的二叉树至多有2^k − 1个结点(根结点的深度为1)”这个性质:
因为2^9-1 < 700 < 2^10-1 ,所以这个完全二叉树的深度是10,前9层是一个满二叉树,
这样的话,前九层的结点就有2^9-1=511个;而第九层的结点数是2^(9-1)=256
所以第十层的叶子结点数是700-511=189个;
现在来算第九层的叶子结点个数。
由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结点。因为第十层有189个,所以应该去掉第九层中的(189+1)/2=95个;
所以,第九层的叶子结点个数是256-95=161,加上第十层有189个,最后结果是350个。

对完全二叉树而言,度为1的结点只能为0或1.设X,Y,Z分别为叶子结点、单支结点数、双支结点数的个数。则:
当Y=0时,700=X+0+Z=2Z+1,Z结果不为整数,故错。
当Y=1时,700=X+1+Z=2Z+2,Z=349.则:X=349+1=350.即叶子结点数为:350.
(二叉树中:叶子结点数=双支结点数+1.)

对完全二叉树而言,度为1的结点只能为0或1.设X,Y,Z分别为叶子结点、单支结点数、双支结点数的个数。则:
当Y=0时,700=X+0+Z=2Z+1,Z结果不为整数,故错。
当Y=1时,700=X+1+Z=2Z+2,Z=349.则:X=349+1=350.即叶子结点数为:350.
(二叉树中:叶子结点数=双支结点数+1.) 不用谢了。。。。 我算了老半天,累死我了!

(700+1)/2,取整数下限
即350

如果没错的话是189个。。。。