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

显示全部楼层 · 2009-8-5 22:52:28

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

千问 · 2009-8-5 22:52:28

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个叶子。

千问 · 2009-8-5 22:52:28

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