《数据结构》问题回答:why100个结点的完全二叉树叶子数为50.

? ?有同学问:为什么具有100个结点的完全二叉树的叶子节点数为50?

? ? 这个问题很有意思,谢谢这同同学的提问。现在分析一下。

? ?如果一棵完全二叉树有100个结点,我们根据以下两点:

? ? ?1.二叉树的性质:深度为k的二叉树,最多有2的k次方-1个结点。

? ? ?2.对于完全二叉树而言,叶子结点只能出现在最后两层,也就是说,完全二叉对左右子树深度差最多为1.

? ? ?可知,结点数100的完全二叉树,深度一定为:7,原因如下:

  • 如果深度为6,就算是满二叉树,也只有63(2的6次方-1=64-1=63)
  • 为7的话,如果是满树,则有点127个结点。现在是100个结点。说明,此时,共有7层,且最后一层(7层)只有100-63=37个叶子。

? ? ? ?因为是完全二叉树, 要么没有孩子,有必先有左孩子,所以可以推出:

  • ?37个叶子是第6层19个结点的孩子。
  • 前6层是满二叉树,因此6层共有32个结点(2的5次方)。因此,第6层叶子还有13个(32-19)。

? ? ? ? ? ?综上所述,结论成立。37+13=50.

? ? ? 还有就是99个叶子的完全不二叉树也是50个叶子呢。

相关文章

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注