完整和完整的二叉树最大和最小索引？

Question

我不知道，如果我这得太多，但我不认为一般情况下的解决方案:(的

Answer 1

据我们存储具有在右子树更大的价值和更小的值的节点对于任何节点的左子树，节点在Bottom Right角将具有最大值并且节点在Bottom Left角将具有最小值

因此，现在您需要找到节点。 Complete and Full BST也存储在数组中，因此索引均匀地分布在点上ES。所以在这里我们需要移动Top to Bottom和Left to Right如果存在n节点，则将索引分配给从1开始到n的节点。

因此，如果我们写定树索引，

      1 
         / \ 
         2  3 
        / \ / \ 
        4  5 6  7 
        /\   ^^^-------------Largest value 
        8 9 
Smallest value----^^^ 

所以这里有8指数将具有最小和值将具有最大值为7索引节点的节点。

所以现在的问题是如何找到它。因此，考虑到我们有一个级别为l的树，那么最大值的索引将是2^level - 1，最小值将会是第2^level个索引。但是，如果total_nodes = 2^level-1，我们在这里获得的最大值的索引可能会给我们一个错误的答案。所以我们需要通过考虑total_nodes = n+1以不同的方式计算level。

int level = (int)(Math.ceil (Math.log(n)/Math.log(2))); //For index of smallest value; 
int smallest_index = (int) Math.pow (2,level); 

level = (int)(Math.ceil (Math.log(n+1)/Math.log(2))); //For index of largest value; 
int largest_index = (int) Math.pow (2,level) - 1; 

Answer 2

Sanket的答案基本上是正确的，但它最终的说法让我感到不舒服。谁在说两个四舍五入的（！）日志的四舍五入（！）比率不会圆整到只是略高于预期的整数？然后ceil将一直向上。也许它有效，但它基本上是偶然的，而不是设计。

它也可以“干净地”表示，而不需要考虑/担心这种事情，就按位算术而言。一切都保持一个整数，因此更容易推理。

最低项目的索引是在n的最高功率2中出现的，所以最高设置位。在Java中，甚至对于一个功能：Integer.highestOneBit，或者我们可以把它写：

int highestOneBit(int x) { 
    x |= x >> 16; 
    x |= x >> 8; 
    x |= x >> 4; 
    x |= x >> 2; 
    x |= x >> 1; 
    return x^(x >>> 1); 
} 

现在我们必须

indexOfLowest = highestOneBit(n); 
indexOfHighest = highestOneBit(n + 1) - 1; 

这还是假设为基础1指数（留下指数0未使用）你可以简单地将它全部抵消1，使它索引0。