我有一棵完美二叉树，即树上的每个节点要么是叶子节点，要么有两个子节点，而 都 叶子节点处于同一层次。每个节点都有一个深度优先的索引。
(例如在一棵有3个层次的树中，根节点的索引为0，第一子节点的索引为1，第一子节点的第一子节点的索引为2，第一子节点的第二子节点的索引为3，第二子节点的索引为4，第二子节点的第一子节点的索引为5，第二子节点的索引为6。
0
/ \
1 4
/ \ / \
2 3 5 6
)
我知道树的大小（节点数-最大级别），但只知道某个节点的索引，我需要计算它的级别（即它到根节点的距离）。我如何最有效地做到这一点？
让 i 是您要找的索引，并且 n 是总的节点数。
这个算法做你想做的事情。
level = 0
while i != 0 do
i--
n = (n-1)/2
i = i%n
level++
done
0是根的索引，如果 i = 0 那么你就达到了好的水平，否则你可以去掉根部，你会得到两个子树。n = (n-1)/2 更新的节点数是新树（是旧树的子树），而 i = i%n 只选择好的子树。
这里还有一个建议，可以让这个问题的解决变得更容易。
如果你用广度优先顺序的索引来标记节点，你可以在O(1)时间内计算出不需要任何遍历的层次。所以如果你要做多个查询，你可以做一个O(N)的BFT，每个查询都能在O(1)时间内得到解答。
级别的公式是。
level = floor(log(index + 1))
其中对数是基数2
在这棵树上试试吧。
0
/ \
/ \
1 2
/ \ / \
/ \ / \
3 4 5 6
干杯
好像直接在树上走应该是够高效的。
在算法的每一步，都要记住你所处节点的子树上的索引范围。范围的第一个值它是根节点，之后前一半是左边子树的范围，后一半应该是右边子树的范围。然后你可以递归向下移动，直到找到你的节点。
例如，让我们在一棵有15个元素的4层树中搜索以下内容
(root node)(left elements)(right elements)
Starting range: (0)(1 2 3 4 5 6 7)(8 9 10 11 12 13 14)
Go left : (1)(2 3 4)(5 6 7)
Go right : (5)(6)(7)
Found node, total depth 2
你应该可以通过一个简单的循环来实现，只需要使用几个变量来存储范围的开始和结束。如果你做了一些细微的改变，比如使用后序遍历或者从1开始而不是从0开始索引，你也应该能够很容易地适应这种情况。
未经测试。
int LevelFromIndex( int index, int count)
{
if (index == 0)
return 0;
if (index > (count - 1)/ 2)
index -= (count - 1) / 2;
return 1 + LevelFromIndex( index - 1, (count - 1) / 2);
}
这里 count 是树中节点的总数。
EDIT: 第1个尝试......只对BFS有效。
如果你说的完美二进制树是指具有堆状结构的二进制树，那么你可以用这个公式计算一个节点的父索引。
parentIndex = (index-1)/2
所以你可以重复这个公式，直到你到<=0为止 每次你循环的时候，你都会在树上上升一个级别。
EDIT: 尝试2.
我能想到的最好的方法是采取O(index+log n)，也就是O(n)。做一个DFS，直到你到达所需的索引，然后用一个父指针继续往上走，直到你到达根部，跟踪你已经往上走的次数。这假定每个节点上都有一个父指针。
如果你只有索引，你就无法找到深度。
假设你有一棵这样的树。
1
/ \
2 5
/ \
3 4
索引3的节点深度为2.
假设你有一棵这样的树。
1
/ \
2 3
/ \
4 5
索引3的节点有深度1。
你不能仅仅通过知道这两棵树的索引来区分它们。没有办法只通过知道索引就能找到离根的距离。
编辑：如果你指的是一棵完美的二叉树，如所有的叶子都是一样的深度，每个父节点都有两个子节点，那么你还是无法找到深度。
比较一下这两棵树。
1
/ \
2 3
1
/ \
2 5
/ \ / \
3 4 6 7
节点3的深度会随着树的高度而变化。
编辑2：如果你知道总树的高度，你就可以使用这种递归算法。
def distanceFromRoot(index, rootIndex, treeHeight):
if index == rootIndex:
return 0
leftIndex = rootIndex+1
rightIndex = rootIndex + 2**treeHeight
if index >= rightIndex:
return 1 + distanceFromRoot(index, rightIndex, treeHeight-1)
else:
return 1 + distanceFromRoot(index, leftIndex, treeHeight-1)
所以，我们有这样一棵树，有4层。
0 - 0th level
/ \
1 8 - 1th level
/ \ / \
2 5 9 12 - 2th level
/ \ /\ / \ / \
3 4 6 7 10 11 13 14 - 3th level
正如你所看到的，每个左边的孩子的根的指数增加了1（左=根+1），因为在DFS中左边的孩子总是先访问。第二个节点有左节点的索引，增加了左子树的大小（right = left + leftSize）。如果我们知道树的深度，我们就可以计算它的大小（size = 2^depth - 1）。至于左子树的深度等于父树的深度减少1，它的大小=2^(parentDepth - 1)-1。
所以现在我们有了一个算法--计算左边节点的索引，计算右边节点的索引。如果节点索引在其之间，则转到左节点，否则-转到右节点。
代码。
static int level(int index, int root, int treeDepth) {
if (index == root)
return 0;
if (treeDepth <= 0 /* no tree */ || treeDepth == 1 /* tree contains only root */)
throw new Exception("Unable to find node");
int left = root + 1;
int right = left + (int)Math.Pow(2, treeDepth - 1) - 1;
if (index == left || index == right)
return 1;
if (left < index && index < right)
return 1 + level(index, left, treeDepth - 1);
else
return 1 + level(index, right, treeDepth - 1);
}