完全二叉树的数组表示,为什么节点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了


补充:

其实想一下结果也很简单,参考前面的计算,节点的下标就是节点前面的所有节点数。

节点数分为

  1. 前n-1层的节点数
  2. 本层前方的节点数。

对于子节点来说。

  1. 第一部分是前n层的节点数,恰好是父节点前n-1层节点数*2 + 1
  2. 第二部分子节点同层节点数,肯定是父节点同层前方节点数*2,因为是完全二叉树。
原文地址:https://www.cnblogs.com/mosakashaka/p/14247323.html