（一）基础补充

满二叉树是每一层节点都放满的二叉树。

完全二叉树是只有最后一层节点右边不放满的二叉树。

满二叉树（Perfect Binary Tree）

        如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。另一种说法：一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树，别称完美二叉树。

  

完全二叉树

        如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。完全二叉树的特点是，除了最后一层之外的其他层都是完全填满的，并且最下面一层的节点集中在该层的最左侧。性质：

• 叶节点的填充必须从最左侧开始。
• 最后一个叶节点必须具有正确的同级节点不是强制性的。