0
/ \
1 4
/ \ / \
2 3 5 6
我知道树的大小（节点数/最大层数），但只知道特定节点的索引，我需要计算它的层数（即到根节点的距离）。如何以最有效的方式完成这项工作？
这是另一个能够让解决此问题更为简单的建议：
如果您按照广度优先的顺序为节点标记索引，您可以在O(1)时间内计算出其所处的层数，而无需进行遍历。因此，如果您需要进行多个查询，您可以进行一次O(N)的广度优先遍历，并在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只选择正确的子树。
(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是树中节点的总数。
(count + 1) / 2 - 1 看起来有点奇怪，为什么不用 (count - 1) / 2 呢？ - Thomash如果你只有索引，你无法找到深度。
假设你有这样一棵树：
1
/ \
2 5
/ \
3 4
索引为3的节点深度为2。
假设您有这样一棵树：
1
/ \
2 3
/ \
4 5
索引为3的节点深度为1。
仅凭索引无法区分这两棵树。仅凭索引无法找到距离根节点的距离。
编辑：如果您指的是完美二叉树，即所有叶子节点深度相同，每个父节点都有两个子节点，则仍然无法找到深度。
比较这两棵树：
1
/ \
2 3
1
/ \
2 5
/ \ / \
3 4 6 7
第三个节点的深度取决于树的高度。
编辑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)
所以，我们有一个四层的树结构：
0 - 0th level
/ \
1 8 - 1th level
/ \ / \
2 5 9 12 - 2th level
/ \ /\ / \ / \
3 4 6 7 10 11 13 14 - 3th level
如您所见，每个左子节点的根索引都加了一(root+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);
}
编辑：第一次尝试...仅适用于BFS。
如果您所说的完美二叉树是指具有堆结构的二叉树，则可以使用以下公式计算节点的父索引：
parentIndex = (index-1)/2
所以你可以重复使用该公式，直到达到<=0，每次循环实际上都会向树中的上一级移动。
编辑：尝试第二次...
我能想到的最好方法需要O（索引+ log n），即O（n）的时间复杂度。进行深度优先搜索，直到达到所需的索引，然后使用父指针继续沿着树向上走，直到达到根节点，并跟踪你向上走的次数。这假定每个节点都有一个父指针。