设一棵完全二叉树共有500个结点,则在该二叉树中的叶子结点数为多少?
展开全部
设二叉树有 h 层
2^0+2^1+...+2^(h-1) >= 500
2^h >=501
h>= 9
前8层有结点 2^8-1= 255个, 第9层有结点 500-255 = 245个, 这245个都是叶子结点
第8层有结点 2^(8-1) = 128 个, 其中有 245/2=123个有孩子, 128-123=5个为叶子结点
所以叶子一共有 245+5 = 250 个
2^0+2^1+...+2^(h-1) >= 500
2^h >=501
h>= 9
前8层有结点 2^8-1= 255个, 第9层有结点 500-255 = 245个, 这245个都是叶子结点
第8层有结点 2^(8-1) = 128 个, 其中有 245/2=123个有孩子, 128-123=5个为叶子结点
所以叶子一共有 245+5 = 250 个
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
250
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
