Complete Binary Tree

一颗二叉树中，除了最后一层外其余层节点都是满的，并且最后一层要么是满的，要么在右边连续缺少若干叶子节点的二叉树称为 完全二叉树（Complete Binary Tree）。

完全二叉树有个重要的特点是可以通过数组来顺序存储，对于索引为 $i$ 节点，它的左子节点为 $2(i+1)-1\to 2i+1$ ， 右子节点为 $2(i+1)+1-1\to 2i+2$ ，父节点为 $\lfloor \frac{i+1}{2}\rfloor -1$ 。

这种存储结构常被用于实现 Binary Heap (完全二叉树的一种), 并用于实现堆排序。