完全二叉树与数组表示：像排队一样高效存储

你有没有遇到过这样的场景：老师让全班同学按顺序坐成一个“三角形”座位，第一排1个座位，第二排2个，第三排4个……但是今天只有很少的同学来，座位从左到右连续坐满，空位都集中在右边。这种“左边满、右边可能空”的树，就是完全二叉树。

计算机里经常要处理这种树，比如堆排序、优先队列（就是操作系统里任务调度的那个“优先队列”）。如果用指针建树，每个节点都要存左右孩子地址，很占内存。但是完全二叉树有一个超棒的规律：用数组就能存，通过下标快速找到父子关系。这篇笔记就来仔细讲讲这个技巧。

1. 什么是完全二叉树？——从“满二叉树”说起

先复习一下满二叉树：每一层的节点数都达到最大值。比如高度为3的满二叉树，第1层1个，第2层2个，第3层4个，总共7个节点。

完全二叉树就是：从满二叉树里，从右边开始去掉一些节点，但去掉的顺序必须是从右往左连续地去掉。换句话说，最后一层的节点都集中在左边，右边可以空着。

举个例子：有5个节点的完全二叉树，长这样：

第1层1个，第2层2个，第3层本来是4个，但这里只有左边2个（4和5），右边两个位置空着。如果第3层节点是4,6（左边是4，右边是6），中间空了5，那就不是完全二叉树——因为没有连续从左到右。

生活中的类比：班级座位编号。老师要求所有同学按学号从左到右、从前到后坐。第1排1号，第2排2、3号，第3排4、5、6、7号……如果某排最后几个座位没人，但只要前面的座位都坐满了（没有跳号），这就是完全二叉树。你按学号找座位，知道排数和位置，非常方便。

2. 数组表示法：利用下标关系“指路”

如果我们把完全二叉树的节点按层序遍历（先第一层，再第二层，逐层从左到右）编号，从1开始，那么会得到一个神奇的规律：

根节点下标是 1
下标为 i 的节点，它的左孩子下标是 2*i
下标为 i 的节点，它的右孩子下标是 2*i + 1
下标为 i 的节点，它的父节点下标是 i / 2（整数除法，向下取整）

为什么这么巧？因为层序遍历的编号顺序，正好让左孩子排在 2i 的位置（把当前层所有节点放完两倍，恰好跳到下一层左边第一个）。我们可以用数学归纳法简单理解：根为1，左孩子2，右孩子3；然后节点2的左孩子4，右孩子5……确实每个节点都能用这个公式找到。

用数组存储的好处

不需要存指针（left、right），省内存
通过下标计算直接访问亲戚节点，速度超快
堆排序、优先队列底层都用这种数组实现

注意：下标从0还是从1？

如果数组下标从 0 开始，公式会变成：左孩子 2*i+1，右孩子 2*i+2，父节点 (i-1)/2。
但为了直观，许多教材和竞赛代码（特别是CSP-J）习惯从下标1开始（浪费tree[0]不用）。我们下面都采用从1开始。

3. 生活中的例子：电影院找座位

假设电影院有3排，第1排1个座位（1号），第2排2个（2、3号），第3排4个（4、5、6、7号）。如果只坐了前5个观众（1~5号），那么第3排的6、7号空着。这时候，座位编号就构成了一个完全二叉树。

你是3号观众，你左边是2号（兄弟），右边？没有，因为树里3号没有右兄弟（完全二叉树最后一层右边可能缺）。
你想找4号观众（你的左孩子的左孩子）：根据公式，3号的左孩子是2*3=6？不对，6号是空座位！所以这里要小心：如果你要访问的孩子下标超过了节点总数n，那么它不存在。

这个小例子提醒我们：用数组存二叉树时，一定要检查下标是否越界。

#include <iostream>
using namespace std;

// 打印层序遍历（其实就是数组按顺序输出）
void printLevelOrder(int tree[], int n) {
    cout << "层序遍历（学号顺序）: ";
    for (int i = 1; i <= n; i++) {
        cout << tree[i] << " ";
    }
    cout << endl;
}

// 查找节点下标 i 的左孩子（如果存在），返回下标，否则返回 -1
int leftChild(int i, int n) {
    int lc = 2 * i;
    if (lc <= n) return lc;
    else return -1;  // 不存在
}

// 查找节点下标 i 的右孩子（如果存在）
int rightChild(int i, int n) {
    int rc = 2 * i + 1;
    if (rc <= n) return rc;
    else return -1;
}

// 查找节点下标 i 的父节点（根节点没有父亲）
int parent(int i) {
    if (i == 1) return -1;   // 根节点没有父节点
    return i / 2;            // 整数除法，自动向下取整
}

int main() {
    int n = 6;  // 节点数量（班级有6个学生）
    // tree[1]~tree[6] 存储学号（也可以存储值）
    // 为了演示，直接用学号作为节点值
    int seats[7] = {0, 101, 102, 103, 104, 105, 106}; // seats[0] 不用

    // 树结构（完全二叉树）：
    //       101
    //      /   \
    //   102    103
    //   / \    /
    // 104 105 106
    // 注意：103只有左孩子106，没有右孩子

    printLevelOrder(seats, n);

    // 演示：访问节点 102（下标2）的亲戚
    int idx = 2;
    cout << "节点 " << seats[idx] << " 的左孩子: ";
    int lc = leftChild(idx, n);
    if (lc != -1) cout << seats[lc] << " (下标" << lc << ")" << endl;
    else cout << "不存在" << endl;

    cout << "节点 " << seats[idx] << " 的右孩子: ";
    int rc = rightChild(idx, n);
    if (rc != -1) cout << seats[rc] << " (下标" << rc << ")" << endl;
    else cout << "不存在" << endl;

    int p = parent(idx);
    cout << "节点 " << seats[idx] << " 的父节点: ";
    if (p != -1) cout << seats[p] << " (下标" << p << ")" << endl;
    else cout << "根节点，无父节点" << endl;

    // 演示：访问节点 103（下标3），它没有右孩子
    idx = 3;
    cout << "\n节点 " << seats[idx] << " 的右孩子: ";
    rc = rightChild(idx, n);
    if (rc != -1) cout << seats[rc] << " (下标" << rc << ")" << endl;
    else cout << "不存在（因为下标 " << 2*idx+1 << " > n=" << n << "）" << endl;

    // 演示：访问根节点的父节点
    cout << "根节点 " << seats[1] << " 的父节点: " << (parent(1) == -1 ? "没有" : "有") << endl;

    return 0;
}

运行结果：

层序遍历（学号顺序）: 101 102 103 104 105 106 
节点 102 的左孩子: 104 (下标4)
节点 102 的右孩子: 105 (下标5)
节点 102 的父节点: 101 (下标1)

节点 103 的右孩子: 不存在（因为下标 7 > n=6）
根节点 101 的父节点: 没有

6. 小总结

完全二叉树：最后一层从左到右连续，右边可缺。数组存储时下标规律超简单：左孩子=2i，右孩子=2i+1，父节点=i/2。
数组大小要开够，访问孩子时记得判断下标是否越界。
从下标1开始写代码更直观，但注意 tree[0] 不用。
这个技巧在堆（最大堆、最小堆）、优先队列、线段树等数据结构中经常用到，是CSP-J必会的“基本功”。

学会了这个，你就可以自己去实现一个堆排序或者优先队列了！下一篇可以学习“堆的插入与删除”，或者“用数组存储完全二叉树的其他应用（比如线段树）”。加油！

完全二叉树与数组表示

完全二叉树与数组表示：像排队一样高效存储

1. 什么是完全二叉树？——从“满二叉树”说起

2. 数组表示法：利用下标关系“指路”

用数组存储的好处

注意：下标从0还是从1？

3. 生活中的例子：电影院找座位

4. 新手容易踩的坑

错误1：数组开得不够大

错误2：忘记判断孩子是否存在

错误3：混淆下标0和下标1

5. 完整代码示例：模拟班级座位查找

6. 小总结

例题精讲