我有一个完美的二叉树，即树中的每个节点要么是叶节点，要么有两个子节点，并且所有叶节点都在同一级别。每个节点都有一个深度优先顺序的索引。
（例如，在具有 3 个级别的树中，根节点的索引为 0
，第一个子节点具有 1，第一个子节点的第一个子节点具有 2，第一个子节点的第二个子节点具有 3，第二个子节点具有 4，第二个子节点的第一个子节点具有索引 6。 0
/
1 4
/ /
2 3 5 6
）
我知道树的大小（节点数/最大级别），但只知道特定节点的索引，我需要计算它的级别（即它到根节点的距离）。如何最有效地做到这一点？
这是另一个建议，可以使这个问题的解决方案更容易：
如果用广度优先顺序的索引标记节点，则可以计算级别，而无需在 O（1） 时间内进行任何遍历。因此，如果你正在执行多个查询，你可以执行 O（N） BFT 并在 O（1） 时间内回答每个查询。
该级别的公式为：
level = floor(log(index + 1))
日志到基数 2 的位置
在这棵树上试试：
0
/
/
1 2
/ /
/ /
3 4 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只选择好的子树。
似乎直接在树上行走应该足够有效。
在算法的每一步，请记住您所在节点的子树上的索引范围。范围的第一个值是根节点，之后的前半部分是左侧子树的范围，后半部分应该是右侧子树的范围。然后，您可以递归向下移动，直到找到您的节点。
例如，让我们在包含 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是树中的节点总数。
编辑：尝试编号 1... 仅适用于 BFS。
如果完美二叉树是指具有堆状结构的二叉树，那么您可以使用以下公式计算节点的父索引：
parentIndex = (index-1)/2
所以你可以重复这个公式，直到你得到<=0，每次循环时，你基本上都会在树中上升一个级别。
编辑：尝试编号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（left = root + 1），因为在 DFS 中，左子项总是首先访问。第二个节点的左节点索引按左子树的大小增加（右=左+左大小）。如果我们知道树的深度，我们可以计算它的大小（大小 = 2^depth - 1）。只要左子树的深度等于父级的深度减少一，其大小 = 2^（父级深度 - 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);
}