Question

关于完全二叉树的子节点序号

完全二叉树中编号为i的结点，其左子节点编号为2i，这个结论怎么证明或推导啊？实际验证倒是完全通过，但是如果有个具体证明就更清楚了，谢谢。

Answer 1

可以这样证明吧：

约定根节点所在的层数为1,根节点编号为1。

下面先证明
（1）完全二叉树中任何一层最左的节点编号n,则其左子树为2n,右子树为2n+1.
显然，每个节点的编号N = 按层遍历位于该节点前面的节点数目+1.
对于第L层的最左节点，在它之前的节点即为第1层到第L-1层的所有节点，共
2^0+2^1+...+2^(L-2) = 2^(L-1)-1个（注意第i层共有2^(i-1)个节点）。
则第L层最左节点编号为2^(L-1)，其左子树为第L+1层的最左节点，故编号为2^L。这样，（1）被证明了。

下面证明
（2）完全二叉树中任一节点编号n,则其左子树为2n,右子树为2n+1.
任取一节点N，其编号为n。设N所在的这一层L的最左节点为M，编号为m。
显然，L层中位于N左边的节点数为n-m个。N的左子树NL位于第L+1层，由于是完全二叉树，第L+1层中位于NL之前的节点数为2(n-m).由(1)可知第L+1层的最左节点编号为2m，那么NL的编号为2m+2(n-m)=2n.