设一棵完全二叉树共有500个结点,则在该二叉树中的叶子结点数为多少?
答案:3 悬赏:60 手机版
解决时间 2021-04-03 12:28
- 提问者网友：欲劫无渡
- 2021-04-03 00:21
设一棵完全二叉树共有500个结点,则在该二叉树中的叶子结点数为多少?
最佳答案
- 五星知识达人网友：空山清雨
- 2021-04-03 01:07
设二叉树有 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 个
全部回答
- 1楼网友：孤独的牧羊人
- 2021-04-03 02:59
250
- 2楼网友：第四晚心情
- 2021-04-03 02:37
250
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯