【数据结构与算法】深入详解完全二叉树和满二叉树：概念、特性、堆、实际应用

艾莉丝努力练剑

发布于 2025-11-13 10:39:36

5660

文章被收录于专栏：C / C++C / C++

🔥个人主页：艾莉丝努力练剑 ❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题、C/C++干货分享&学习过程记录 🍉学习方向：C/C++方向 ⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

C++的两个参考文档：

老朋友（非官方文档）：cplusplus 官方文档（同步更新）：cppreference

1 基本概念对比

【数据结构与算法】数据结构初阶：详解二叉树（一）

1.1 满二叉树的概念

定义：满二叉树是指每一层的节点都达到最大数量的二叉树。

满二叉树具有以下特征： 1、所有非叶子节点都有且只有两个子节点； 2、第k层的节点数为2的(k-1)次方个； 3、深度为h的满二叉树总节点数为2的h次方减1； 4、所有叶子节点都位于树的最底层。

1.2 完全二叉树的概念

定义：完全二叉树指的是除了最后一层外，其他各层节点都达到最大数量，且最后一层节点依次从左向右连续排列的二叉树。

完全二叉树具有以下特征： 1、高度为h的完全二叉树，节点数范围在[2的(h-1)次方，2的h次方减1]之间； 2、可以高效使用数组存储（与堆结构存储方式相同）； 3、插入/删除操作能保持完全二叉树的结构特性。

2 特性对比

2.1 两者的结构特性

2.1.1 满二叉树的结构特性

（1）每一层都必须完全填满；（2）不存在只有单个子节点的父节点；（3）所有叶子节点都在同一深度。

2.1.2 完全二叉树的结构特性

（1）允许最后一层不完全填满；（2）最后一层节点必须从左向右连续排列；（3）可以存在只有左子节点的父节点。

2.2 存储特性

2.2.1 满二叉树的存储特性

（1）可以使用数组存储；（2）但可能存在较多空间浪费（当实际节点数不足时）。

2.2.2 完全二叉树的存储特性

（1）特别适合数组存储；（2）存储空间利用率高；（3）无空间浪费（与堆结构存储方式一致）。

2.3 数量关系

2.3.1 节点数量关系

（1）满二叉树：严格等于2的h次方减1（h为树高）；（2）完全二叉树：介于2的(h-1)次方到2的h次方减1之间。

2.3.2 高度计算

（1）满二叉树高度：h = log (n + 1)；（2）完全二叉树高度：⌈ log (n + 1) ⌉。

2.4 满二叉树和完全二叉树的对比

特性	满二叉树	完全二叉树
节点分布	每层都为满	最后一层可以不满，但必须从左向右依次填充
叶子节点位置	叶子节点全在最底层	叶子节点集中在最后两层
节点数量关系	严格地按2 ^h - 1	范围在[ 2 ^ ( h - 1 ), 2 ^ h - 1 ]
存储方式	可以使用数组，但可能会造成空间上的浪费	数组存储不存在浪费

3 二叉树与堆结构

【数据结构与算法】数据结构初阶：详解二叉树（二）——堆

3.1 堆的本质特性

1、堆是一种特殊的完全二叉树。

2、堆满足的堆序性质：

（1）大顶堆（大堆）：每个父节点的值 >= 其子节点的值；（2）小顶堆（小堆）：每个父节点的值 <= 其子节点的值。

3.2 数组表示法

完全二叉树紧凑的特性使得我们可以使用堆数组来高效表示——

完全二叉树的紧凑特性使得我们可以使用数组高效表示堆。

以节点 i（数组下标从0开始）为例：

（1）父节点位置：( i - 1 ) / 2；（2）左子节点：2 i + 1；（3）右子节点：2 i + 2；

下面是一个大顶堆（大堆）的示例——

int heap[] = {50, 30, 20, 15, 10, 8, 16};

4 代码实现

4.1 完全二叉树实现

代码演示如下：

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} CompleteBinaryTree;

// 初始化函数
void initTree(CompleteBinaryTree* tree) {
    tree->size = 0;
}

// 插入节点函数
bool insertNode(CompleteBinaryTree* tree, int value) 
{
    if (tree->size >= MAX_SIZE) return false;
    tree->data[tree->size++] = value;
    return true;
}

// 计算树的高度
int calculateHeight(int nodeCount) 
{
    return (int)ceil(log2(nodeCount + 1));
}

// 判断是否为满二叉树
bool isFullBinaryTree(const CompleteBinaryTree* tree) 
{
    int h = calculateHeight(tree->size);
    return tree->size == (1 << h) - 1; // 2^h - 1
}

// 打印树结构
void printTree(const CompleteBinaryTree* tree) 
{
    for (int i = 0; i < tree->size; i++) 
    {
        printf("Node %d: %d", i, tree->data[i]);
        
        int left = 2*i + 1;
        int right = 2*i + 2;
        
        if (left < tree->size) 
            printf(" -> Left: %d", tree->data[left]);
        if (right < tree->size) 
            printf(", Right: %d", tree->data[right]);
        
        printf("\n");
    }
}

int main() 
{
    CompleteBinaryTree tree;
    initTree(&tree);
    
    // 构建完全二叉树
    for (int i = 1; i <= 7; i++) 
    {
        insertNode(&tree, i*10);
    }
    
    printTree(&tree);
    printf("Is full binary tree? %s\n", 
           isFullBinaryTree(&tree) ? "Yes" : "No");
    
    return 0;
}

4.2 分析

4.2.1 节点插入

（1）始终保持完全二叉树的结构特性；（2）新节点总是添加到当前最后一个位置。

4.2.2 判断满二叉树

（1）通过计算实际节点数是否等于2^h-1来判断；（2）使用位运算提高计算效率。

4.3 其他代码实现

4.3.1 完全二叉树的数组表示

代码演示如下：

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct 
{
    int data[MAX_SIZE];
    int size;
} CompleteBinaryTree;

// 初始化完全二叉树
void initTree(CompleteBinaryTree *tree) 
{
    tree->size = 0;
}

// 插入节点（保持完全二叉树性质）
bool insertNode(CompleteBinaryTree *tree, int value) 
{
    if (tree->size >= MAX_SIZE) return false;
    tree->data[tree->size++] = value;
    return true;
}

// 获取父节点索引
int parentIndex(int childIdx) 
{
    return (childIdx - 1) / 2;
}

// 获取左子节点索引
int leftChildIndex(int parentIdx) 
{
    return 2 * parentIdx + 1;
}

// 获取右子节点索引
int rightChildIndex(int parentIdx) 
{
    return 2 * parentIdx + 2;
}

// 打印树结构
void printTree(const CompleteBinaryTree *tree) 
{
    for (int i = 0; i < tree->size; i++) {
        printf("Node %d: %d", i, tree->data[i]);
        
        int left = leftChildIndex(i);
        int right = rightChildIndex(i);
        
        if (left < tree->size) 
            printf(" -> Left: %d", tree->data[left]);
        if (right < tree->size) 
            printf(", Right: %d", tree->data[right]);
        
        printf("\n");
    }
}

int main() 
{
    CompleteBinaryTree tree;
    initTree(&tree);
    
    // 构建一个完全二叉树
    insertNode(&tree, 10);
    insertNode(&tree, 20);
    insertNode(&tree, 30);
    insertNode(&tree, 40);
    insertNode(&tree, 50);
    insertNode(&tree, 60);
    insertNode(&tree, 70);
    
    printTree(&tree);
    
    return 0;
}

4.3.2 满二叉树判断函数

代码演示如下：

// 判断是否为满二叉树
bool isFullBinaryTree(const CompleteBinaryTree *tree) 
{
    if (tree->size == 0) return true;
    
    int h = 0;
    int nodes = tree->size;
    
    // 计算树的高度
    while ((1 << h) - 1 < nodes) 
    {
        h++;
    }
    
    // 检查节点数是否等于2^h - 1
    return nodes == (1 << h) - 1;
}