《数据结构》问题回答：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个叶子呢。

（编辑：ASP站长）

【免责声明】本站内容转载自互联网，其相关言论仅代表作者个人观点绝非权威，不代表本站立场。如您发现内容存在版权问题，请提交相关链接至邮箱：bqsm@foxmail.com，我们将及时予以处理。