2.4.7 #

解答 #

k = 2 时， 只可能出现在位置 2、3 上（根节点的子结点，深度为 2，根节点深度为 1）

k = 3 时， 可以直接是根节点的子结点（第 2 或第 3 位，深度为 2），

也可以是第二大元素的子结点（第 4~7 位，也就是深度为 3 的所有位置）

k = 4 时，

可以直接是根节点的子结点（深度为 2 的点）

也可以是第二大元素的子结点（深度为 3 的点）

也可以是第三大元素的子结点（深度为 4 的点）

故范围为第 2~15 位。

不难看出第 k 大元素只可能出现在深度＜k 的位置（$k \ge 2$）

即位置小于 $2 ^ k - 1, (k \ge 2)$