如何在深度优先顺序的隐式二叉树中快速确定左右节点索引？

问题背景 #

我们知道，完美二叉树按**Eytzinger顺序（层序/广度优先遍历）**存储时，1-based索引下内部节点i的左右子节点索引为2i和2i+1，规则非常直观。

但如果按前序深度优先遍历顺序存储节点，节点i的左右子节点索引计算依赖于该节点子树的高度hᵢ：

• 左子节点索引：i+1
• 右子节点索引：i + 2^(hᵢ-1) - 1（其中2^(hᵢ-1)-1是左子树的节点总数）

如果每次传递高度信息可行，但我们希望直接从i和整树高度H优雅高效地推导hᵢ，替代时间复杂度O(H)的循环解法。

最优解法：O(1)直接推导 #

公式推导 #

对于完美二叉树的前序DFS存储，子树高度hᵢ可以通过以下公式直接计算：

hᵢ = H - floor(log₂(i))

其中floor(log₂(i))是i的二进制表示中最高位对应的指数（即最大的整数k满足2ᵏ ≤ i）。

验证示例 #

以整树高度H=3为例（总节点数7，前序DFS顺序为：1→2→4→5→3→6→7）：

• i=1（根节点）：floor(log₂(1))=0 → hᵢ=3-0=3，正确
• i=2（左子根）：floor(log₂(2))=1 → hᵢ=3-1=2，正确
• i=3（右子根）：floor(log₂(3))=1 → hᵢ=3-1=2，正确
• i=4（左左叶节点）：floor(log₂(4))=2 → hᵢ=3-2=1，正确

位运算高效实现 #

为了避免浮点运算的精度问题，可以用位操作快速获取最高位的指数k：

• 在Python中，利用int.bit_length()方法：k = i.bit_length() - 1（比如i=3的二进制是11，bit_length=2，k=1）
• 在C++中，使用内置函数：k = 31 - __builtin_clz(i);（针对32位无符号整数）

对应的hᵢ计算代码示例（Python）：

def get_subtree_height(i, H):
    k = i.bit_length() - 1
    return H - k

原算法的不足 #

你当前的循环算法需要遍历从根到目标节点的路径，时间复杂度为O(H)，当H较大（比如H=30，对应百万级节点）时，性能会明显低于O(1)的位运算解法。

内容的提问来源于stack exchange，提问作者Alec Jacobson