完全二叉树（Complete Binary Tree）是一种特殊的二叉树，具有以下性质：

1. 定义

完全二叉树是指一棵二叉树中，除了最后一层外，其余层都是满的，并且最后一层的节点都集中在左侧。

2. 性质

（1）节点编号与层次关系

  • 如果将完全二叉树的节点从上到下、从左到右依次编号（从 1 开始），则对于任意节点 i：
    • 其左子节点的编号为 2i。
    • 其右子节点的编号为 2i + 1。
    • 其父节点的编号为 ⌊i / 2⌋（向下取整）。

（2）高度与节点数的关系

  • 设完全二叉树的高度为 h，节点数为 n，则：
    • 高度 h = ⌊log₂n⌋ + 1。
    • 节点数的范围是：2^(h-1) ≤ n ≤ 2^h - 1。

（3）结构特点

  • 完全二叉树的最后一层节点从左到右依次排列，不会出现中间空缺的情况。
  • 如果最后一层不满，则所有节点都集中在左侧。

（4）与满二叉树的关系

  • 满二叉树是完全二叉树的特例，即所有层都满的完全二叉树。
  • 完全二叉树不一定是满二叉树，但满二叉树一定是完全二叉树。

（5）数组存储

  • 完全二叉树可以用数组高效存储，因为节点编号与数组下标有直接的对应关系。
    • 节点 i 的左子节点存储在 2i。
    • 节点 i 的右子节点存储在 2i + 1。
    • 节点 i 的父节点存储在 ⌊i / 2⌋。

（6）插入与删除

  • 插入新节点时，总是添加到最后一层的第一个空位（从左到右）。
  • 删除节点时，通常删除最后一个节点（即编号最大的节点）。

（7）堆的实现

  • 完全二叉树是堆（Heap）的基础结构。
    • 大顶堆：每个节点的值大于或等于其子节点的值。
    • 小顶堆：每个节点的值小于或等于其子节点的值。

3. 示例

以下是一个完全二叉树的示例：

1
2
3
4
5
    1
   / \
  2   3
 / \ /
4  5 6
  • 节点编号：1, 2, 3, 4, 5, 6。
  • 最后一层（第 3 层）节点集中在左侧。

4. 完全二叉树与满二叉树的区别

特性 完全二叉树 满二叉树
定义 除了最后一层，其余层都是满的，最后一层节点集中在左侧 所有层都满
节点数范围 2^(h-1) ≤ n ≤ 2^h - 1 n = 2^h - 1
结构灵活性 最后一层可以不满 必须所有层都满
数组存储 可以用数组高效存储 可以用数组高效存储

5. 完全二叉树的应用

（1）堆（Heap）

  • 堆是一种基于完全二叉树的数据结构，常用于实现优先队列。
  • 堆分为大顶堆和小顶堆，分别用于快速获取最大值或最小值。

（2）优先队列

  • 优先队列通常用堆实现，支持高效插入和删除操作。

（3）哈夫曼树

  • 哈夫曼树是一种用于数据压缩的完全二叉树。

（4）二叉搜索树

  • 某些二叉搜索树（如 AVL 树、红黑树）在平衡时会保持完全二叉树的性质。

6. 判断完全二叉树的方法

可以通过以下方法判断一棵二叉树是否为完全二叉树：

  1. 层序遍历法：

    • 对二叉树进行层序遍历。
    • 如果遇到空节点后还有非空节点，则不是完全二叉树。

  2. 节点编号法：

    • 为每个节点编号（从 1 开始）。
    • 如果最大编号等于节点数，则是完全二叉树。

7. 代码实现：判断完全二叉树

以下是使用层序遍历法判断完全二叉树的 C++ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isCompleteTree(TreeNode* root) {
    if (!root) return true; // 空树是完全二叉树
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false; // 是否遇到过空节点
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (!node) {
            hasNull = true; // 遇到空节点
        } else {
            if (hasNull) return false; // 如果之前有空节点，则不是完全二叉树
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}

int main() {
    // 构建一个完全二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    if (isCompleteTree(root)) {
        cout << "It is a complete binary tree." << endl;
    } else {
        cout << "It is not a complete binary tree." << endl;
    }
    return 0;
}

输出：

1
It is a complete binary tree.

总结

完全二叉树是一种结构规整的二叉树，具有高效的存储和操作特性。它在堆、优先队列等数据结构中广泛应用，是算法设计与实现中的重要工具。