如何证明堆数据结构中的子数据位于: 2*n和2*n+1？

Question

这不是家庭作业问题，我今天学习了堆数据结构，我不知道如何证明这种关系是正确的。谢谢。

Answer 1

归纳证明：

1. 根的子(1) -> child1= 2*1=2，child2= 2*1 +1=3 true
2. 假设kth元素的子元素是-> child1= 2k，child2=2k+1
3. 证明(k+1)th元素的子元素是child1= 2*(k+1)，child2=2(k+1) +1(证明这一点)

证明3:由于kth元素的子元素位于2k和2k+1 (基于假设)，那么后面的两个元素是2k+2和2k+3。

2k+2 = 2( k+1 ) (证明了k+1的第一个子)(A)

2k+3 = 2k +2+1= 2( k+1 ) +1(证明了k+1的第二个孩子)(B)

从(a) & (b) ->因此，3是有效的，因此元素n的子元素2n和2n+1

Answer 2

这里有一个没有归纳的证明，从我的角度看，这是更直观和有洞察力的。这里有四个心理步骤来证明这种关系对我。

把树夷为平地。

让我们以以下方式枚举树的所有顶点：

​

以下是这些版本在数组中的外观：

​

​

在数组中隔离兄弟姐妹。

我们可以注意到，每两个连续节点(第一个除外)都是一些公共顶点的子节点：

1 [ 2 3 ] [ 4 5 ] [E 2116 7E 112]e 213E 114[E 2158 9E 116]E 217

以不同的方式构建这个数组。

现在让我们以相反的顺序思考。如果我们有一个对的数组：(2，3)，(4，5)，(6，7)，(8，9)，并且我们想把它们聚集在一个数组中呢？

假设我们已经放置了前3对：

[ 2 3 ] [ 4 5 ] [E 2276 7E 128]E 229

最后一个数组中的数字8的索引是什么？我们知道我们已经放置了3对，它们在开始的时候占据了3*2=6位，所以我们将获得第7位。

如果我们编码成对的位置，它将如下所示：

pair<int, int> pairs[4] = { {2, 3}, {4, 5}, {6, 7}, {8, 9} };
int aggregate[2 * 4];
for (int i = 0; i < 4; i++)
{
    aggregate[2 * i] = pairs[i].first;
    aggregate[2 * i + 1] = pairs[i].second;
}

关键部分是数组聚合索引2* i。在这段代码中，显而易见的是我们为什么要乘2 -我们要这样做，因为我们必须跳过之前的i-1对。

树的平化与对的聚合相结合

现在，我们需要看到构建对的聚合数组与二叉树的扁平之间的对应关系。每对兄弟姐妹都有父母。如果两个兄弟姐妹(2，3)和(4，5)在阵列上相邻，那么它们的父母也是相邻的。兄弟姐妹(2，3 )有父级1，兄弟姐妹(4，5)有父级2，兄弟姐妹(6，7)有父级3。因此，父级就像这组对( pairs[4] = { (2, 3), (4, 5), (6, 7), (8, 9) } )中的索引，当我们使用2 * i访问它的左子时，我们可以考虑跳过由以前的顶点生成的i-1对。