[已解决]完全二叉树,叶节点为k,最下面一层的节点数目大于1，问树的深度

大可爱 · 发表于 2018-10-28 15:55:41

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

完全二叉树，叶节点为k,最下面一层的节点数目大于1，问树的深度。
大佬，如何解答。

最佳答案

月排行榜 / 总排行榜

爱学习的懒懒君

2018-10-28 16:59:29

本帖最后由爱学习的懒懒君于 2018-10-28 17:06 编辑

对于一个完全二叉树，叶节点分布在其倒数一二层
n层的完全二叉树，最少有2^(n - 2)个叶节点（最下面一层只有一个最左侧叶节点），题上要求最下面一层大于1就是最少2^(n - 2) + 1个
最多有2^(n - 1) - 1个叶节点（比n层二叉树少最右边一个叶节点）
所以看k落在哪个范围就可以求出n了

跳转到最佳答案楼层

爱学习的懒懒君 · 发表于 2018-10-28 16:59:29

本帖最后由爱学习的懒懒君于 2018-10-28 17:06 编辑

对于一个完全二叉树，叶节点分布在其倒数一二层
n层的完全二叉树，最少有2^(n - 2)个叶节点（最下面一层只有一个最左侧叶节点），题上要求最下面一层大于1就是最少2^(n - 2) + 1个
最多有2^(n - 1) - 1个叶节点（比n层二叉树少最右边一个叶节点）
所以看k落在哪个范围就可以求出n了

账号		自动登录	找回密码
密码			立即注册