设一颗完全二叉树共有699个结点,则在该二叉树中的叶子的结点数为多少?麻烦给出具体点的答案

来源:百度知道 编辑:UC知道 时间:2024/06/18 05:15:11
希望给出具体点的解答

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

完全二叉树就是除了最深的一层其他每层都是满的,假设该树有n层,第n层有x个节点,每个父节点有两个子节点
1+1*2+1*2*2+1*2*2*2+...+2^(n-2)+x=699
1+2+4+8+..+256=495
x=699-495=204
最下面一层有204个节点,即有204个叶子,然后倒数第二层有256-204/2=154个叶子
总共有358个叶子

log2(699)是9点几,也就是说加上叶子这棵二叉树总共有10层。第十层的全部是叶子,上面9层总共有2的9次方减1个节点也就是511个,所以最下面有699-511=188个叶子。第10层有188个叶子,每两个叶子链接一个父节点,也就是说第9层有188除以2等于94个父节点,剩下的是第9层的叶子。第9层有2的9-1次方也就是256个节点,除去94个父节点,剩下256-94=162个叶子。所以总共有188+162=350个叶子。

这个应该发到数学里面去
这是离散数学里面有的结论