存储方式

二叉树的存储方式有多种，常见的有以下两种主要方式：

1. 顺序存储（数组存储）

适合于存储完全二叉树和满二叉树，因为这些树的节点位置有规律，可以用数组按层次存储节点数据。

特点：

树的节点按层次编号，根节点位于数组的第 1 个位置（数组下标为 0 或 1），然后是左子树和右子树的节点依次填充。
下标关系：
- 父节点的下标为 (i)，则：
  - 左子节点的下标为 (2i + 1) （0-based），或 (2i)（1-based）。
  - 右子节点的下标为 (2i + 2) （0-based），或 (2i + 1)（1-based）。
- 子节点的下标为 (i)，则父节点的下标为 (\frac{i-1}{2}) （0-based）或 (\frac{i}{2})（1-based）。

优点：

简单，适合完全二叉树或满二叉树，便于计算节点的关系。

缺点：

如果是一般二叉树，可能会有大量的空位置浪费空间，特别是对于稀疏的二叉树。

示例：对于如下二叉树：

它的数组表示为 [1, 2, 3, 4, 5]。

2. 链式存储（链表存储）

这是最常见的一种二叉树存储方式，特别是对于普通二叉树或不规则树，使用链表来存储更为高效。

特点：

每个节点包含三部分：
- 数据域（存储节点的值）。
- 左指针域（指向左子节点）。
- 右指针域（指向右子节点）。
如果没有左或右子节点，则对应的指针为 null（空指针）。

节点结构（C语言或类似语言表示）：

struct TreeNode {
    int value;          // 节点值
    TreeNode* left;     // 左子节点指针
    TreeNode* right;    // 右子节点指针
};

优点：

适合一般二叉树，能够灵活处理各种树形结构。
不浪费内存，因为只为实际存在的节点分配空间。

缺点：

对于完全二叉树或满二叉树，链式存储可能占用更多的空间（每个节点额外存储两个指针）。

示例：对于如下二叉树：

使用链式存储的结构如下：

TreeNode {
    value = 1,
    left = TreeNode { value = 2, left = TreeNode { value = 4 }, right = TreeNode { value = 5 } },
    right = TreeNode { value = 3 }
}

比较：

存储方式

适用场景

优点

缺点

顺序存储

完全二叉树、满二叉树

节点关系可以通过下标直接计算，简单

空间浪费，适合规则树

链式存储

普通二叉树（不规则结构的树）

灵活，节省空间，不存在空节点浪费

需要指针，空间开销更大，复杂度增加

3. 特殊存储方式

在一些特殊应用场景中，也有针对特定需求的存储方法。例如：

父子表示法：每个节点除了存储子节点的指针，还存储父节点的指针，用于快速找到父节点。
三叉链表：用于三叉树或有特殊指向需求的树。

具体的存储方式取决于实际应用场景和二叉树的类型。

PreviousAVL树和红黑树的关系与区别比较 Next遍历

Last updated 9 months ago