真完全二叉树和完全二叉树的区别

### 真完全二叉树与完全二叉树的区别

#### 定义差异

真完全二叉树通常指的是满二叉树，即除了叶节点外每一个节点都具有两个子节点，并且所有的叶子节点都在最后一层[^1]。对于满二叉树而言，每一层上的所有结点都有两个孩子结点，在最后一层上不存在任何非叶子结点。

完全二叉树定义为除最后一层外其他各层的结点数都达到最大值，而且最后一层的结点全部集中在该层最左边的位置。即使最后一层未填满也只会在右边缺少部分元素[^2]。

#### 结构特性比较

- **层次填充**
- 满二叉树（真完全二叉树）要求每层都被完全填充，直到最后一层为止；而完全二叉树允许最后一层只有左侧连续的部分被占用。

- **节点数量关系**
- 对于高度为h的满二叉树来说，其总共有\(2^{h}-1\)个节点；
- 而同样高度下的完全二叉树则至少拥有\(\lceil(2^{h})/2\rceil+(2^{h}-1)\)个节点，最多不超过\(2^{h}-1\)个节点[^3]。

def is_full_binary_tree(tree):
    """检查给定的二叉树是否为满二叉树"""
    if not tree or (not tree.left and not tree.right): 
        return True
    elif bool(tree.left) != bool(tree.right): 
        return False
    else: 
        return is_full_binary_tree(tree.left) and \
               is_full_binary_tree(tree.right)

def is_complete_binary_tree(tree, index=0, node_count=None):
    """验证一棵二叉树是不是完全二叉树"""
    if node_count is None:
        count = lambda t: 1 + count(t.left) + count(t.right) if t else 0
        node_count = count(tree)
    
    if not tree:
        return True
    
    if index >= node_count:
        return False
    
    return all([
        is_complete_binary_tree(child, i*2+idx+1, node_count) 
        for idx, child in enumerate((tree.left, tree.right))])