完全二叉树必为满二叉树

在C++中，完全二叉树是一种特殊的二叉树，它的定义是：除了最后一层外，其他层的节点数都达到最大值，并且最后一层的节点都集中在左侧。而满二叉树是一种特殊的完全二叉树，它的定义是：除了叶子节点外，每个节点都有两个子节点。

可以证明，一个完全二叉树必然是满二叉树。证明的思路如下：

假设完全二叉树的高度为h，那么它的节点数n满足以下关系：
n = 2^h - 1

假设满二叉树的高度为h，那么它的节点数m满足以下关系：
m = 2^h - 1

我们可以通过数学归纳法来证明完全二叉树必然是满二叉树。

当h=1时，全二叉树和满二叉树都只有一个节点，满足条件。

假设当h=k时，完全二叉树必然是满二叉树，即n = 2^k - 1 = m。

当h=k+1时，完全二叉树的节点数为n' = 2^(k+1) - 1，满二叉树的节点数为m' = 2^(k+1) - 1。

我们可以观察到，完全二叉树的最后一层节点数最多为2^k，而满二叉树的最后一层节点数为2^(k+1) - 1。

因此，完全二叉树的节点数n'小于等于满二叉树的节点数m'，即 n' <= m'。

又因为完全二叉树的节点数n' = 2^k - 1 = m，所以 n' = m。

综上所述，完全二叉树必然是满二叉树。

相关问题

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

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

#### 定义差异

真完全二叉树通常指的是满二叉树，即除了叶节点外每一个节点都具有两个子节点，并且所有的叶子节点都在最后一层[^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))])

. 编写函数实现判断二叉树是否为完全二叉树。（空二叉树是完全 二叉树）

判断一个给定的二叉树是否为完全二叉树，可以通过遍历节点并检查每个层级的节点数是否满足完全二叉树的要求来实现。在完全二叉树中，除了最后一层外，每一层的节点都是满的，且最右边的节点都尽可能靠左。

以下是一个简单的C语言函数，用于判断一个二叉树是否为完全二叉树：

#include <stdbool.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 判断是否为完全二叉树辅助函数
bool isCompleteBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return true; // 空树视为完全二叉树
    }
    
    queue<TreeNode*> q; // 使用队列存储节点
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left != NULL && node->right != NULL) { // 如果当前节点有两个子节点
                q.push(node->left);
                q.push(node->right);
            } else {
                // 检查是否有节点未填满当前层级的剩余位置
                bool hasIncompleteLevel = false;
                if (levelSize > 1 && node->left != NULL) {
                    hasIncompleteLevel = true;
                } else if (levelSize > 0 && node->right != NULL) {
                    hasIncompleteLevel = true;
                }

                if (hasIncompleteLevel) {
                    return false; // 找到不完整层级，直接返回false
                }
            }
        }
    }

    return true; // 遍历完所有节点都没找到不完整层级，说明是完全二叉树
}

这个函数首先创建一个队列并将根节点放入。然后在每一轮循环中，处理当前层级的所有节点，如果遇到节点有右孩子但没有左孩子（或相反），则说明当前层级不满，立即返回`false`。只有当所有层级都被正确填充时，才返回`true`表示完全二叉树。