CC++ & Algorithm

完全二叉树：像排队一样整齐的树

困难15
语言版本：C++Python
概述：完全二叉树是一种特殊的二叉树，除了最后一层外，其他层都是满的，最后一层的节点都靠左排列。

完全二叉树：像排队一样整齐的树

同学们，你们在学校里排过队吗？体育老师常常说：“第一排站满，第二排站满，第三排从左边开始站，不能有空位！”这种从左边开始、整整齐齐的排队方式，和计算机里一种叫“完全二叉树”的结构特别像。完全二叉树就像一支训练有素的队伍：前面的几排（层）都站得满满当当，最后一排（层）的人也是紧紧靠左排列，中间绝不空缺。

完全二叉树有什么用呢？它最大优点是可以很方便地用数组来存放，不需要像普通二叉树那样用很多指针，既节省内存又提高访问速度。今天我们就来认识一下这位“排队标兵”。

一、什么是完全二叉树？

完全二叉树是这样一棵树：

  1. 除了最下面一层，其他层的节点个数都达到最大值（也就是每一层都排满了）。
  2. 最下面一层的节点必须从左到右连续排列，中间不能有缺口。

举个例子：一棵有3层的完全二叉树，第一层1个节点，第二层2个，第三层应该最多有4个节点。如果第三层刚好有4个节点（全满），那它叫满二叉树，当然也是完全二叉树。如果第三层只有3个节点，且这3个节点是左边的连续三个（比如第1、2、3位），那也满足完全二叉树的条件。但如果第三层只有最右边一个节点（左边空着），或者中间缺了一个（比如左边两个，右边一个，中间空一个），那就不是完全二叉树了。

生活小例子：
假设你们班要站成3排照相，第一排能站4人，第二排能站4人，第三排能站4人。如果前两排都站满了（各4人），第三排只来了3个人，那他们就只能从左边开始站（位置1、2、3），空着最右边的位置。这样整支队伍从前面看是满的，最后一排只有左边有人——这就是完全二叉树。如果第三排的人非要站最右边两个，中间空一个，那队伍就不好看，也不算完全二叉树。

用节点编号来理解：
完全二叉树中，节点从上到下、从左到右依次编号（从0开始），你会发现所有非空节点的编号是连续的，中间不会有空缺。例如下面这棵树：

        1 (0)
       / \
      2   3 (1,2)
     / \   \
    4   5   6 (3,4,5)

最后一层只有3个节点（4,5,6），但它们都是从左到右连续的，所以是完全二叉树。

二、为什么完全二叉树这么有用？

完全二叉树最吸引人的地方是：可以用数组来存储，而且找父子节点非常快。

用数组存储时，我们把节点按层序遍历的顺序依次放进数组里。假设根节点在数组下标0的位置，那么：

  • 左孩子的下标 = 2 * i + 1
  • 右孩子的下标 = 2 * i + 2
  • 父节点的下标 = (i - 1) / 2（向下取整）

比如上图的二叉树，用数组存为：[1, 2, 3, 4, 5, 6]。

  • 节点2的下标是1，它的左孩子4的下标是 2*1+1=3，右孩子5的下标是 2*1+2=4，都对得上。
  • 节点3的下标是2，它的左孩子6的下标是 2*2+1=5，右孩子呢？右孩子下标是 2*2+2=6，但数组下标6不存在，说明节点3没有右孩子。

好处： 不需要像普通二叉树那样用 left 和 right 指针，只用数组就能表示整棵树，节省了大量内存（每个指针在64位系统上要占8字节）。另外，从数组里找父节点或孩子节点只需要简单计算，速度非常快。

这种存储方式在“堆”（一种特殊的完全二叉树）中特别常用，比如我们后面要学的优先队列（priority_queue）就用堆实现。

三、如何判断一棵树是不是完全二叉树？

面试或考试中，经常要你判断一棵二叉树是否是完全二叉树。最常用的方法是层序遍历（也叫广度优先搜索）。思路是：

  1. 用队列从根节点开始一层层遍历。
  2. 设置一个布尔变量 mustBeEmpty（必须为空），初始为 false。
  3. 遍历每个节点时：
    • 如果当前节点是 nullptr（空节点），就把 mustBeEmpty 设为 true。
    • 如果当前节点不是空节点，那么：
      • 如果 mustBeEmpty 已经是 true（说明之前已经遇到过空节点），那就不符合完全二叉树（因为空节点后面不应该再出现非空节点），直接返回 false。
      • 否则，把当前节点的左孩子和右孩子（即使它们是空）都加入队列。
  4. 遍历完所有节点都没有返回 false，就说明是完全二叉树。

注意： 为什么要同时把左右孩子（即使是空）加入队列？因为我们要模拟层序遍历的顺序，不跳过任何位置。空节点也要入队，这样队列里才算完整记录了每一层的所有位置（包括空缺），然后通过 mustBeEmpty 来判断后续是否还有非空节点。

四、新手容易犯的错误

  1. 忘记把空孩子加入队列
    有人只把非空孩子加入队列，这样队列里就不会出现空节点，导致 mustBeEmpty 永远为 false，结果误判所有树都是完全二叉树。正确做法是：不管孩子是不是空，都把它加入队列。

  2. 混淆满二叉树和完全二叉树
    满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。满二叉树是每一层都满了（比如三层树有1+2+4=7个节点）。有些同学以为最后一层没满就不是完全二叉树，其实只要最后一层的节点靠左连续，就是完全二叉树。

  3. 下标计算错误
    如果要用数组实现完全二叉树，记住孩子下标公式是 2*i+1 和 2*i+2，而不是 2*i 和 2*i+1（那是根节点下标从1开始的写法）。下标从0开始更常见，也更符合C++数组习惯。

  4. 忘记考虑空树
    空树（根节点是 nullptr）也算完全二叉树吗？是的，因为定义允许空树。判断时应该先处理 if (!root) return true;。

五、完整代码示例

下面给出一个完整的C++程序，包含判断完全二叉树的函数，并测试多种情况。

#include <iostream>
#include <queue>
using namespace std;

// 二叉树节点结构
struct Node {
    int data;            // 节点的值
    Node* left;          // 左孩子指针
    Node* right;         // 右孩子指针
    // 构造函数：初始化节点值，左右孩子置为空
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 判断一棵树是否是完全二叉树
// 用层序遍历，遇到空节点后不能再有非空节点
bool isComplete(Node* root) {
    if (root == nullptr) return true;          // 空树是完全二叉树
    queue<Node*> q;                            // 队列用于层序遍历
    q.push(root);                              // 根节点入队
    bool mustBeEmpty = false;                  // 标记是否已经遇到过空节点
    while (!q.empty()) {
        Node* cur = q.front();                 // 取队首节点
        q.pop();                               // 出队
        if (cur == nullptr) {
            mustBeEmpty = true;                // 遇到空节点，开启“必须为空”模式
        } else {
            if (mustBeEmpty) return false;     // 空节点后面还有非空节点 → 不是完全二叉树
            // 把左右孩子（无论是否为空）都入队
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    return true;                               // 遍历完都符合条件
}

int main() {
    // 测试1：构造一棵完全二叉树（最后一层靠左）
    cout << "测试1：构造完全二叉树" << endl;
    Node* root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);
    root1->right->left = new Node(6);          // 最后一层只有3个节点，靠左连续
    cout << (isComplete(root1) ? "是完全二叉树" : "不是完全二叉树") << endl;

    // 测试2：构造一棵非完全二叉树（最后一层中间空缺）
    cout << "测试2：构造非完全二叉树（右孩子存在，左孩子为空）" << endl;
    Node* root2 = new Node(1);
    root2->left = new Node(2);
    root2->right = new Node(3);
    root2->left->right = new Node(4);          // 节点2只有右孩子，没有左孩子 → 中间有空缺
    cout << (isComplete(root2) ? "是完全二叉树" : "不是完全二叉树") << endl;

    // 测试3：空树
    cout << "测试3：空树" << endl;
    Node* root3 = nullptr;
    cout << (isComplete(root3) ? "是完全二叉树" : "不是完全二叉树") << endl;

    // 测试4：满二叉树（也是完全二叉树）
    cout << "测试4：满二叉树" << endl;
    Node* root4 = new Node(1);
    root4->left = new Node(2);
    root4->right = new Node(3);
    root4->left->left = new Node(4);
    root4->left->right = new Node(5);
    root4->right->left = new Node(6);
    root4->right->right = new Node(7);         // 所有节点都满了
    cout << (isComplete(root4) ? "是完全二叉树" : "不是完全二叉树") << endl;

    return 0;
}

运行结果：

测试1：构造完全二叉树
是完全二叉树
测试2：构造非完全二叉树（右孩子存在，左孩子为空）
不是完全二叉树
测试3：空树
是完全二叉树
测试4：满二叉树
是完全二叉树

小朋友可以自己动手修改 main 函数中的树结构，看看哪些树会被判断为完全二叉树，哪些不是。

六、相关知识点指引

学完完全二叉树，你可能会对下面几个内容感兴趣：

  • 满二叉树：每一层节点都达到最大值，是完全二叉树的特例。
  • 二叉堆：一种基于完全二叉树的数据结构，常用于实现优先队列（C++中的 priority_queue）。堆有很多有趣的应用，比如“堆排序”。
  • 层序遍历：也叫广度优先遍历，是二叉树遍历的一种重要方法，常用于判断完全二叉树、求树的宽度等。
  • 数组存储树：当你知道树是完全二叉树时，可以用数组非常高效地存储和访问，没有指针开销。

下一次，不妨拿一支笔在纸上画出几棵二叉树，然后用今天的方法判断它们是不是“排队标兵”吧！

例题精讲

1单选题

一棵深度为h的完全二叉树，最少有多少个节点？（深度从1开始，根节点深度为1）

A2^h - 1
B2^(h-1)
C2^(h-1) + 1
D2^(h-1) - 1
2单选题

关于完全二叉树，下列说法错误的是？

A完全二叉树中，若某个节点没有左孩子，则它一定没有右孩子。
B完全二叉树中，度为1的节点数最多为1。
C完全二叉树采用顺序存储时，下标为i的节点的左孩子下标为2i（下标从1开始）。
D完全二叉树中所有叶子节点都在同一层。
3判断题

在完全二叉树中，如果节点A有左孩子但没有右孩子，则节点A一定是完全二叉树中最后一个非叶子节点。

4填空题
以下函数用于在采用顺序存储（下标从1开始）的完全二叉树中获取节点i的父节点下标（若i为根节点则返回0）。请补全代码。

int getParent(int i) {
    if (i == 1) return 0;
    return ___;
}
5填空题
以下函数用于判断一棵完全二叉树（节点个数为n）是否为满二叉树。请补全循环条件。

bool isFullCompleteBinaryTree(int n) {
    if (n <= 0) return false;
    int m = n + 1;
    while (___) {
        m /= 2;
    }
    return m == 1;
}