未命名文件 (6).jpg

二叉树的每一层节点数量是一个公比为2的等比数列，如第一层也就是根节点的数量是2^(1-0) =1，第二层2^(2-1) =2，第三层2^(3-1)=4，第k层为2^(k-1)

等比数列的通项公式和求和公式如下

image.png

假设根节点下标从0开始，第k层最后一个节点的下标为带入到求和公式 Sn = 1(1-2^k)/(1-2) = 2^k -1，因为下标从0开始，因此再减去1为 2^k -1 -1 = 2^k - 2。

而第k层第一个节点下标为上一层（k-1）层最后一个节点加1可以得到为2^(k-1)-1。

假设父节点为第k层的第n个节点，则其下标为F=2^(k-1) -1 + (n-1) = 2^(k-1) + n -2

根据二叉树的结构，其子节点得走完第层剩下的2^k -2 - F = 2^k -2 - (2^(k-1) + n -2)= 2^(k-1) - n 个节点，到下一层后，还得走完左边个父节点对应的子节点，再加上本身的1一个值，即其左子节点的下标为

2^(k-1) - n + 2(n-1)+1 + F
= 2^(k-1) - n + 2n - 2 + 1 + 2^(k-1) + n - 2
= 2 * 2^(k-1) + 2n - 4 + 1
= 2 * (2^(k-1) + n - 2) +1
= 2F +1

结论
二叉树中父节点的下标为F，则其左子节点下标为2F+1，右子节点下标为2F+2