如何确定完全二叉树中给定子树中叶子的索引？
How to determine the indexes of the leaves in a given subtree in a complete binary tree?
我有一个完整的数组表示法二叉树（广度优先）：
[15, 10, 5, 3, 7, 5, 0, 1, 2, 3, 4, 5, 0, 0, 0]
所以所有叶子的索引是：7,8,9,10,11,12,13,14
对于每个内部节点，我需要 return 它们子树中叶子的索引：
- 节点 15:7、8、9、10、11、12、13、14
- 节点 10: 7, 8, 9, 10
- 节点 5: 11, 12, 13, 14
- 节点 3:7、8
- 节点 7:9、10
- 节点 5:11、12
- 节点 0:13, 14.
是否存在任何公式？
由于数组代表一棵完美的二叉树，即所有内部节点都有 2 个子节点，并且所有叶子都位于同一深度，因此数组长度将始终为 2 减 1 的幂。在例如它是 24-1。那个幂就是树的层数……比树的高度多一层。我们称高度为ℎ，则输入数组的大小为2ℎ+1-1.
我们可以使用 position 数字的二进制表示。对于位置，我的意思是 index 加 1。因此根节点的位置为 1，其子节点的位置为 2 和 3。使用 ℎ+1 二进制数字以二进制表示形式表示每个位置。因此对于示例输入，您将使用 4 位数字。要知道给定位置下方的叶子的位置范围，请查看位置编号中有多少个前导零。
例如，取位置3（示例树的值为5），二进制为0011，有4位。它有 2 个前导零。
现在删除那些前导零。例如，我们得到二进制 11.
现在完成这些数字 在右边 与任何数字再次有 4 位数字。这表示叶子的位置范围。在示例中：1100 到 1111。然后您可以将其转回十进制并减去 1 以获得索引：11,12,13,14。
这是一个 table，它对您的示例中的所有内部节点执行此计算：
Index
Value
Position
Position (binary)
Shift
Range
In decimal
Indices
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
我有一个完整的数组表示法二叉树（广度优先）：
[15, 10, 5, 3, 7, 5, 0, 1, 2, 3, 4, 5, 0, 0, 0]
所以所有叶子的索引是：7,8,9,10,11,12,13,14
对于每个内部节点，我需要 return 它们子树中叶子的索引：
- 节点 15:7、8、9、10、11、12、13、14
- 节点 10: 7, 8, 9, 10
- 节点 5: 11, 12, 13, 14
- 节点 3:7、8
- 节点 7:9、10
- 节点 5:11、12
- 节点 0:13, 14.
是否存在任何公式？
由于数组代表一棵完美的二叉树，即所有内部节点都有 2 个子节点，并且所有叶子都位于同一深度，因此数组长度将始终为 2 减 1 的幂。在例如它是 24-1。那个幂就是树的层数……比树的高度多一层。我们称高度为ℎ，则输入数组的大小为2ℎ+1-1.
我们可以使用 position 数字的二进制表示。对于位置，我的意思是 index 加 1。因此根节点的位置为 1，其子节点的位置为 2 和 3。使用 ℎ+1 二进制数字以二进制表示形式表示每个位置。因此对于示例输入，您将使用 4 位数字。要知道给定位置下方的叶子的位置范围，请查看位置编号中有多少个前导零。
例如，取位置3（示例树的值为5），二进制为0011，有4位。它有 2 个前导零。
现在删除那些前导零。例如，我们得到二进制 11.
现在完成这些数字 在右边 与任何数字再次有 4 位数字。这表示叶子的位置范围。在示例中：1100 到 1111。然后您可以将其转回十进制并减去 1 以获得索引：11,12,13,14。
这是一个 table，它对您的示例中的所有内部节点执行此计算：
| Index | Value | Position | Position (binary) | Shift | Range | In decimal | Indices |
|---|---|---|---|---|---|---|---|
| 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 |