如果节点 X 存储在数组中下标为 i 的位置, 下标为 2 * i 的位置存储的就是左子节点, 下标为 2 * i + 1 的位置存储的就是右子节点.
反过来, 下标为 i/2 的位置存储就是它的父节点. 通过这种方式, 我们只要知道根节点存储的位置(一般情况下, 为了方便计算子节点, 根节点会存储在下标为 1 的位置), 这样就可以通过下标计算, 把整棵树都串起来.
所以, 如果某棵二叉树是一棵完全二叉树, 那用数组存储无疑是最节省内存的一种方式. 因为数组的存储方式并不需要像链式存储法那样, 要存储额外的左右子节点的指针.
对于完全二叉树来说, 下标从 n/2+1 到 n 都是叶子节点, 反证法.