给定堆中有多少叶子及其级别
How many leaves are in a given heap and its level
我有一个问题，它是这样的：
存在最大堆二叉树。
假设在堆中最底层有 (2^2017)-2017 个节点。
A)堆中有多少层？
B)堆中的叶子有多少个？
谢谢
在最底层有 2x 个节点的完整二叉堆有 (x+1) 层。考虑这个堆：
1
2 3
4 5 6 7
底层有4（22）个节点，共3层。
如果底层已满，则叶子节点数与底层节点数相同。
在您的例子中，底层有 (22017)-2017 个叶节点。我们知道这一层可能的最大节点数是22017（因为最大值总是2的幂）。而且我们还知道，从上面的例子中，树中有 2018 层。
但是叶节点的个数不是(22017)-2017。考虑这个堆：
1
2 3
4 5 6 7
8 9
底层有两个叶子节点，底层有三个叶子节点（5、6、7）。
我想你会发现在你的情况下，叶子节点的数量是(22017)-2017 + 2017/2. 2017/2是上一层的叶节点数
我有一个问题，它是这样的：
存在最大堆二叉树。
假设在堆中最底层有 (2^2017)-2017 个节点。
A)堆中有多少层？
B)堆中的叶子有多少个？
谢谢
在最底层有 2x 个节点的完整二叉堆有 (x+1) 层。考虑这个堆：
1
2 3
4 5 6 7
底层有4（22）个节点，共3层。
如果底层已满，则叶子节点数与底层节点数相同。
在您的例子中，底层有 (22017)-2017 个叶节点。我们知道这一层可能的最大节点数是22017（因为最大值总是2的幂）。而且我们还知道，从上面的例子中，树中有 2018 层。
但是叶节点的个数不是(22017)-2017。考虑这个堆：
1
2 3
4 5 6 7
8 9
底层有两个叶子节点，底层有三个叶子节点（5、6、7）。
我想你会发现在你的情况下，叶子节点的数量是(22017)-2017 + 2017/2. 2017/2是上一层的叶节点数