如何确定完全二叉树中给定子树中叶子的索引？

Question

我有一个完整的二叉树，索引从 0 开始：

                             0
                 _________ /   \ __________
               /                            \
             1                                2
           /   \                           /     \
         /       \                       /         \
       3           4                   5             6
     /   \       /   \               /   \         /   \
    7     8     9     10           11     12     13     14

叶节点的索引为

7

、

8

、

9

、...、

14

。

给定一个节点索引

i

，我们如何找到属于根节点为

i

的子树的叶节点索引？

例如，

• 当

  i == 0

  时，答案是

  7

  ，

  8

  ，...，

  14

  。

• 当

  i == 1

  时，答案是

  7

  、

  8

  、

  9

  和

  10

  。

• 当

  i == 4

  时，答案是

  9

  和

  10

  。

---

_{（↓编者注：以下信息与问题本身完全无关。但是，我不会删除它，因为这些信息是从已接受的答案中引用的。）}

顺便说一句，我们假设节点具有这些值（广度优先）：

[15, 10, 5, 3, 7, 5, 0, 1, 2, 3, 4, 5, 0, 0, 0]
 ↑                                           ↑
root note                            rightmost leaf node

Answer 1

由于数组表示完美二叉树，即所有内部节点都有 2 个子节点，并且所有叶子都位于相同深度，因此数组长度将始终为 2 减 1 的幂。在示例中为 2 ⁴-1。这个力量就是树的层数……比树的高度多一层。我们将高度称为 ℎ，则输入数组的大小为 2^ℎ+1-1。

我们可以使用position数字的二进制表示。对于位置，我的意思是 index 加 1。因此根的位置为 1，其子节点的位置为 2 和 3。使用 ℎ+1 个二进制数字以二进制表示形式表示每个位置。因此，对于示例输入，您将使用 4 位数字。要了解给定位置以下叶子的位置范围，请查看位置编号中有多少个前导零。

例如，取位置 3（示例树的值为 5），即 4 位二进制的 0011。它有 2 个前导零。

现在删除那些前导零。对于这个例子，我们得到二进制 11。

现在将右侧的这些数字与任意数字一起补全，再次得到 4 位数字。这代表叶子的位置范围。在示例中：1100 到 1111。然后您可以将其转回十进制并减去 1 以获得索引：11,12,13,14。

这是一个对示例中的所有内部节点进行此计算的表：

索引	价值	位置	位置（二进制）	移动	范围	十进制	指数
0	15	1	0001	1***	1000-1111	8-15	7-14
1	10	2	0010	10**	1000-1011	8-11	7-10
2	5	3	0011	11**	1100-1111	12-15	11-14
3	3	4	0100	100*	1000-1001	8,9	7,8
4	7	5	0101	101*	1010-1011	10,11	9,10
5	5	6	0110	110*	1100-1101	12,13	11,12
6	0	7	0111	111*	1110-1111	14,15	13,14