二叉树的存储结构

二叉树常见的存储方式有两种：顺序存储和链式存储。

一、顺序存储

顺序存储是用一段连续的内存空间，例如数组，来保存二叉树的结点。

通常按照二叉树的层序依次存入数组：

        A
       / \
      B    C
     / \  / \
    D   E 0  F

若数组下标从 0 开始：

下标：0  1  2  3  4  5  6
数据：A  B  C  D  E  0  F

结点位置关系

设某个结点的数组下标为 i：

若数组下标从 0 开始，则：

• 左孩子下标：2i + 1
• 右孩子下标：2i + 2
• 父结点下标：(i - 1) / 2，结果向下取整

若数组下标从 1 开始，则：

• 左孩子：2i
• 右孩子：2i + 1
• 父结点：i / 2

特点

优点：

• 存储结构简单；
• 能快速计算父结点和孩子结点的位置；
• 特别适合存储完全二叉树；
• 堆通常使用顺序存储。

缺点：

• 对于普通二叉树或斜树，数组中可能出现大量空位置；
• 插入、删除结点不够灵活；
• 需要提前考虑数组容量。

例如斜树：

A
 \
  B
   \
    C

顺序存储可能是：

下标：0  1   2  3 4 5   6
数据：A  空  B  空 空 空  C

会造成空间浪费。

---

二、链式存储

链式存储使用结点和指针来表示二叉树。每个结点通常包含三个部分：

左孩子指针 | 数据 | 右孩子指针

C语言中的定义示例：

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

结构关系可以表示为：

        A
       / \
      B   C

其中：

• A.left 指向 B
• A.right 指向 C
• 没有孩子时，对应指针为 NULL
• n个节点的二叉链表中，有n + 1个空链域

特点

优点：

• 不需要连续的内存空间；
• 不会因为空结点造成大量存储空间浪费；
• 插入、删除结点比较灵活；
• 适合存储各种形态的二叉树。

缺点：

• 每个结点需要额外保存两个指针；
• 不能直接通过下标访问结点；
• 查找某个结点通常需要从根结点开始遍历。

---

三、两种存储方式对比

对比项	顺序存储	链式存储
存储结构	数组	结点和指针
内存是否连续	是	不一定
访问孩子结点	通过下标计算	通过指针访问
空间利用率	普通二叉树可能较低	通常较高
插入和删除	不够灵活	较灵活
适合场景	完全二叉树、堆	一般二叉树
是否需要额外指针	不需要	需要左右指针

这个章节倒是没啥内容，都挺简单的。主要时间去做选择题去了，但我懒得把题目也搬上来，明天或后天做到代码题在去总结吧。

可爱的贵贵呢😊