完全二叉树的数组表示,为什么节点i子节点坐标为2i+1,2i+2

看堆排序的时候看到堆这个结构,对这个结论有点好奇。
于是算了一下,其实结果还挺简单的。

假设一个节点,他在数组下标是i
在二叉树的第n层
且该节点在该层位于第x+1个(既在该层前方有x个节点)。

那么由于完全二叉树前n层的总节点数是2^n - 1,在第n层的节点,前n-1层有2^(n-1) - 1个节点,加上他本层前面的x个节点,则:
i = 2^(n-1) - 1 + x

下面考虑子节点,i的子节点在第n+1层。
对于左子节点,令他在数组中下标为j。
左子节点在n+1层中,前面应该有2x个节点,(因为i在第n层前面有x个,每一个节点在下一层都会有2个节点)。
所以可以得到
j = (2^n - 1) + 2x = 2(2^(n-1) + x -1) + 1
= 2i + 1

这样左节点下标j = 2i+1,右节点也就是2i+2了

上一篇:luogu P2609 [ZJOI2012]数列


下一篇:[atAGC051D]C4