设一棵完全二叉树中有 21 个结点，如果按照从上到下、从左到右的顺序从 0 开始顺序编号，则编号为 8 的双亲结点的编号是___________，编号为 8 的左孩子结点的编号是_____________。

在完全二叉树中，每个节点的编号与其位置有直接的关系。对于第 `i` 个节点，如果它是从上往下数的第 `j` 行（行数从 0 开始），并且从左往右数的第 `k` 个节点（列数也从 0 开始），那么它的编号就是 `2^(j-1) * k + i - 1`。

对于编号为 8 的节点：
1. 因为它是第 8 号节点，我们可以先计算出它所在的行和列。由于它是从0开始编号，所以需要找出 `(8 - 1)` 是哪两个 `2^n` 的差值之和，也就是 `(8 - 1)` 等于第几层的 `2^(n-1)` 和第几列的 `k` 乘积。这可以逐位检查：

   8 = 2^3 (因为4*2=8)
   所以，8是一个深度为3的节点，即它在第4行，第0列（因为是从0开始计数的）。

其双亲节点将位于上一行的最右边，也就是第 3 行的最后一个节点，其列号将是 2^(3-1) - 1，即 `2 * 1 - 1 = 1`。所以双亲节点的编号是 `2^(3-1) * 1 + 3 - 1 = 2 * 1 + 2 = 4`。

2. 对于编号为 8 的左孩子结点，它将在同一行的下一个位置，即第 4 行第 1 列，因此左孩子的编号是 `2^(3-1) * 2 + 8 - 1 = 2 * 2 + 7 = 11`。

总结起来，编号为 8 的双亲节点的编号是 4，左孩子节点的编号是 11。

相关问题

写出下面的答案3.已知完全二叉树的第6层有10个结点，则该完成二叉树共有 个结点。 4.已知一颗完全二叉树，结点编号从0开始按层次遍历，结点i （i>0）的双亲结点编号是 。 5.已知一颗完全二叉树，结点编号从1开始按层次遍历，结点i 的右孩子结点编号是 ,左孩子结点编号是 。 6.已知Huffman树有n个叶子结点，则它的结点总数为 。 7.如果二叉树的深度为5，则其结点数目最少为 , 最多为 。 8.如果一颗二叉树的先序遍历和中序遍历顺序相同，则该二叉树 ；如果其先序遍历和后序遍历顺序相同， 则该二叉树 。

3. 该完全二叉树共有 2^6 - 1 + 10 = 75 个节点。
4. 结点 i 的双亲结点编号为 (i-1)/2。
5. 结点 i 的右孩子结点编号为 2i，左孩子结点编号为 2i+1。
6. Huffman 树共有 2n-1 个结点。
7. 结点数目最少为 2^5 - 1 = 31，最多为 2^6 - 1 = 63。
8. 如果一颗二叉树的先序遍历和中序遍历顺序相同，则该二叉树是一颗斜树；如果其先序遍历和后序遍历顺序相同，则该二叉树为一颗满二叉树。

给定一棵包含n个结点的完全二叉树，树上每个结点都有一个权值，按从上到下、从左到右的顺序依次是 w1,w2,…,wn。请你计算一下哪个深度的结点权值之和最大？已知深度从1开始逐层增1。

### 回答1：
可以发现，深度相同的结点权值之和是相等的，因此我们只需要计算每一层的权值之和，然后比较大小即可。

对于一棵完全二叉树，第k层有2^(k-1)个结点，因此第k层的权值之和为2^(k-1) * wk。

我们可以遍历每一层，计算出每一层的权值之和，然后比较大小，找出最大值所在的深度即可。

具体实现可以使用一个变量max_sum记录当前最大的权值之和，以及一个变量max_depth记录当前最大权值之和所在的深度。遍历每一层时，计算该层的权值之和sum，如果sum大于max_sum，则更新max_sum和max_depth。

时间复杂度为O(logn)，因为完全二叉树的深度为logn。

### 回答2：
首先，我们需要了解什么是完全二叉树。完全二叉树是一种特殊的二叉树，除了最后一层外，每一层都被填满，最后一层从左至右填入结点，不允许出现空缺。根据这个定义，我们可以算出这棵树的深度为log2(n)+1。

接下来考虑如何求深度为d的结点权值之和。我们首先需要考虑完全二叉树的性质，即对于任意一个结点i，其左儿子结点编号为2i，右儿子结点编号为2i+1。根据这个性质，我们可以得出深度为d的结点的编号范围为[2^(d-1), 2^d-1]。

有了编号范围，我们可以直接计算深度为d的结点权值之和。具体地，我们将处于该编号范围内的结点权值求和即可。这个过程可以用一个简单的循环实现，时间复杂度为O(n/logn)，n为树的结点数。

最后，我们需要遍历所有深度，找到权值之和最大的深度。这个过程可以在遍历深度时同时计算出每个深度的权值之和，并不断更新最大值。遍历深度的时间复杂度为O(logn)，因此整个算法的时间复杂度为O(n/logn)。

总结起来，给定一棵完全二叉树，计算其中哪个深度的结点权值之和最大，可以按照以下步骤进行：

1. 计算树的深度为log2(n)+1。
2. 遍历每个深度，计算对应深度的结点权值之和。
3. 按照深度权值之和的大小排序，找到最大的深度。

### 回答3：
首先，要知道什么是完全二叉树。完全二叉树是一棵二叉树，除了最底层，其他层的结点个数都是满的，最后一层的结点都靠左排列。根据这个性质，我们可以很容易地计算出每一层的结点数量。

然后，我们考虑哪个深度的结点权值之和最大。可以发现，对于一棵完全二叉树，深度越大的结点权值之和一定越大，因为深度越大的结点数量越少，但是它们的权值都比较大。

设最大的深度为d，那么我们需要计算每一层的权值之和，并比较它们的大小。具体地，对于第k层，我们把该层的结点权值之和乘上2^(d-k)，即可得到深度为d的总权值之和。最后，再比较每一层的权值之和，找出最大值所在的深度即可。

代码实现如下：

int n; // 结点数
vector<int> w; // 存储每个结点的权值

// 计算深度为d的结点权值之和
int getSum(int d) {
int cnt = (1 << (d - 1)); // 第d层的结点数
int sum = 0;
for (int i = cnt; i < min(n+1, cnt*2); i++) { // 第d层的结点编号从2^(d-1)到2^d-1
sum += w[i];
}
return sum * (1 << (n-d)); // 计算深度为d的总权值
}

// 查找最大权值所在的深度
int findMaxDepth() {
int maxSum = 0, maxDepth = -1;
for (int d = 1; d <= n; d++) {
int sum = getSum(d);
if (sum > maxSum) {
maxSum = sum;
maxDepth = d;
}
}
return maxDepth;
}

时间复杂度为O(nlogn)，因为要计算深度为d的结点权值之和，需要遍历第d层的所有结点，但是每个结点只会被遍历一次。总共有logn层，所以时间复杂度为O(nlogn)。