层序遍历与完全二叉树的数组存储

💡 打个比方

消防队检查一栋楼，不会"顺着楼梯一口气冲顶"，而是一层查完再查下一层，每层从东到西挨个房间。把这套"一层一层"的规则用在树上，就是层序遍历。

而"完全二叉树"像一座座位号排得满满当当的阶梯影院：第 1 排 1 个座、第 2 排 2 个、第 3 排 4 个……座位号从左到右连号发。既然座位号这么规整，直接用数组下当代号就能管理整棵树——不用一根指针一根指针地连！

🖼️ 大图看明白

💻 完整代码

两段代码：第一段用队列做指针树的层序遍历；第二段把完全二叉树存进数组，用三公式秒查父亲和孩子。

// 代码 1：指针树的层序遍历（队列版）
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *l, *r;
    Node(int v) : val(v), l(nullptr), r(nullptr) {}
};

void bfs(Node *root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);              // 根先排队
    while (!q.empty()) {
        Node *p = q.front();   // 队头出列
        q.pop();
        cout << p->val << " ";  // 访问（打印）
        if (p->l) q.push(p->l); // 孩子按左→右排到队尾
        if (p->r) q.push(p->r);
    }
}

int main() {
    //      1
    //     / \
    //    2   3
    //   / \
    //  4   5
    Node *root = new Node(1);
    root->l = new Node(2);  root->r = new Node(3);
    root->l->l = new Node(4); root->l->r = new Node(5);
    bfs(root);   // 输出：1 2 3 4 5
    return 0;
}

// 代码 2：完全二叉树的数组存储（下标从 1 开始）
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int a[MAXN];
int n;

int main() {
    int vals[] = {0, 8, 3, 10, 1, 6, 14, 4, 7, 2, 13};
    n = 10;
    for (int i = 1; i <= n; i++) a[i] = vals[i];

    // 完全二叉树的层序遍历 = 按序打印数组
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << endl;
    // 输出：8 3 10 1 6 14 4 7 2 13

    int i = 6;   // 查询下标 6 的节点
    if (i > 1) cout << "父亲 = " << a[i/2] << endl;
    // 输出：父亲 = 10
    if (2*i <= n) cout << "左孩子 = " << a[2*i] << endl;
    // 输出：左孩子 = 7
    if (2*i+1 <= n) cout << "右孩子 = " << a[2*i+1] << endl;
    // 输出：右孩子 = 2
    return 0;
}

✋ 你来试试