C / C++ / 系统课时

完全二叉树为何适合数组保存

完全二叉树为何适合数组保存

完全二叉树的关键优势是节点按层从左到右连续出现,不会在中间留下大量空位。因此它可以直接映射到连续数组,并用简单下标公式定位父节点和两个子节点,省去指针字段,也让堆这类结构的实现更紧凑。

学习目标

  • 理解完全二叉树为什么能紧凑映射到数组
  • 掌握从数组下标计算父节点、左子节点和右子节点的方法
  • 能判断给定下标对应的亲子关系是否越界

连续排列为什么适合数组

普通二叉树可能在任意位置缺少左、右孩子,如果强行按层编号保存,数组里容易出现许多空槽。完全二叉树不同:除最后一层外,每层都填满;最后一层也从左向右连续填充,所以按层序放入数组时,节点天然占据一段连续下标。

完全二叉树到数组的下标映射

这种紧凑性带来两个直接收益:一是无需为左右孩子额外保存指针;二是父子关系可以通过算术计算得到。对堆来说,这意味着插入、删除和调整都可以直接在数组内交换元素。

下标关系怎么计算

采用 C 数组常见的 0 起始下标 时,设当前节点下标为 i,数组元素个数为 n:

  • 左子节点:2 * i + 1
  • 右子节点:2 * i + 2
  • 父节点:(i - 1) / 2,仅在 i > 0 时使用

这些公式成立的原因是层序排列把每个父节点的两个孩子依次放在后续位置。根节点下标为 0,没有父节点,因此不能直接套用父节点公式。

下面用一个完整 C 程序验证下标关系:

c
#include <stdio.h>

int main(void) {
    int heap[] = {90, 70, 80, 20, 40, 60, 50};
    int n = (int)(sizeof(heap) / sizeof(heap[0]));
    int i = 1;

    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int parent = (i - 1) / 2;

    printf("node[%d]=%d\n", i, heap[i]);
    printf("parent[%d]=%d\n", parent, heap[parent]);

    if (left < n) {
        printf("left[%d]=%d\n", left, heap[left]);
    }
    if (right < n) {
        printf("right[%d]=%d\n", right, heap[right]);
    }

    return 0;
}

预期输出

text
node[1]=70
parent[0]=90
left[3]=20
right[4]=40

越界判断不能省

下标公式只告诉你“理论位置”,不保证那个位置真的有节点。最后一层可能没有填满,因此访问孩子前必须检查计算出的下标是否小于 n。父节点也有边界:当 i == 0 时,当前节点就是根,没有父节点。

什么时候这种表示最合适

数组表示特别适合形状接近完全二叉树、并且经常通过父子下标调整的结构,例如最大堆和最小堆。相反,若树的形状非常稀疏、频繁在任意位置插入节点,数组会浪费空间,此时链式节点通常更合适。

理解“完全二叉树的结构约束换来了连续存储和 O(1) 下标定位”后,就能看懂为什么堆通常不是用指针树实现,而是直接放在数组里。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

完全二叉树为何适合数组保存

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通