23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储？-数据结构与算法之美

当前位置:　首页>> 技术小册>> 数据结构与算法之美

### 23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储？

在数据结构与算法的广阔天地中，二叉树以其独特的结构特性和广泛的应用场景占据了举足轻重的地位。它不仅是理解复杂数据结构如红黑树、AVL树等的基础，也是实现许多高效算法（如快速排序、堆排序等）的关键组件。然而，在二叉树的存储方式上，我们常面临两种选择：使用指针（或引用）的链式存储和使用数组的顺序存储。本章节将深入探讨什么样的二叉树适合用数组来存储，以及这种存储方式的优势与局限性。

#### 一、二叉树的基本概念

在正式讨论之前，我们先简要回顾二叉树的基本概念。二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。根据节点的子节点数量，二叉树的节点可以分为三类：叶子节点（无子节点）、只有一个子节点的节点（左子节点或右子节点）、以及有两个子节点的节点（完全节点）。

#### 二、二叉树的存储方式

##### 1. 链式存储

链式存储是二叉树最直观的存储方式，通过节点间的指针（或引用）连接构成树的结构。每个节点通常包含三个部分：存储数据的元素域、指向左子节点的指针（或引用）、以及指向右子节点的指针（或引用）。链式存储的优点是灵活，可以方便地表示各种形态的二叉树，包括不平衡的树；缺点是空间利用率不高，因为每个节点都需要额外的空间来存储指针（或引用）。

##### 2. 顺序存储

顺序存储则是将二叉树中的节点按照某种规则存储在数组中。这种存储方式要求二叉树具有特定的性质，以便能够高效地在数组与树结构之间进行转换。顺序存储的优点是空间利用率高，访问节点速度快（通过数组索引直接访问）；缺点是适用范围有限，仅适用于满足特定条件的二叉树。

#### 三、什么样的二叉树适合用数组来存储？

并非所有类型的二叉树都适合用数组来存储。适合用数组存储的二叉树通常需要满足以下一个或多个条件：

##### 1. 完全二叉树

完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。对于完全二叉树，我们可以按照层序遍历的顺序将其节点存储在数组中。具体来说，若节点在树中的位置为第i层、第j个（从左至右计数，根节点位于第1层、第1个），则其在数组中的索引为`index = (i-1) * 2^(L-i) + j-1`，其中L为树的层数（根节点层数为1）。然而，由于计算索引的复杂性，更常用的方法是直接按照层序遍历的顺序，从数组的第一个位置开始依次存储节点。

完全二叉树的数组存储方式使得我们可以通过简单的计算快速定位任意节点的父节点、左子节点和右子节点的位置。例如，对于数组中索引为`i`的节点，其父节点的索引为`(i-1)/2`（向下取整），左子节点的索引为`2*i+1`，右子节点的索引为`2*i+2`（假设数组索引从0开始）。

##### 2. 满二叉树

满二叉树是另一种特殊的完全二叉树，其中每一层都被完全填满，没有任何空缺。由于满二叉树是完全二叉树的一个子集，因此它也适合用数组来存储，并且存储方式与完全二叉树相同。

##### 3. 特定形态的二叉树

除了完全二叉树和满二叉树外，某些具有特定形态的二叉树也可能适合用数组来存储，但这通常取决于具体的应用场景和存储需求。例如，在某些特定算法中，可能需要构建一个形状固定的二叉树（如二叉搜索树的某种特殊形态），此时如果能够通过某种规则将树的结构映射到数组上，那么使用数组存储可能会带来便利。然而，这种情况相对少见，且需要具体问题具体分析。

#### 四、数组存储的优势与局限性

##### 优势：

1. **空间利用率高**：对于完全二叉树和满二叉树等特定形态的二叉树，数组存储可以充分利用数组的空间连续性，减少空间浪费。
2. **访问速度快**：通过数组索引直接访问节点，无需遍历指针链，提高了访问效率。
3. **便于实现某些操作**：如快速定位父节点、子节点等，对于某些算法实现具有优势。

##### 局限性：

1. **适用范围有限**：仅适用于满足特定条件的二叉树，如完全二叉树和满二叉树。对于一般形态的二叉树，数组存储方式可能不适用或效率低下。
2. **灵活性差**：数组存储方式在插入和删除节点时可能不够灵活，尤其是当树的结构发生变化时，可能需要重新调整数组中的元素位置。
3. **空间浪费**：对于非完全二叉树，使用数组存储可能会导致部分空间未被有效利用。

#### 五、总结

在选择二叉树的存储方式时，我们需要根据二叉树的形态、应用场景以及存储需求等多方面因素进行综合考虑。对于完全二叉树和满二叉树等特定形态的二叉树，数组存储方式具有空间利用率高、访问速度快等优势；然而，对于一般形态的二叉树或需要频繁进行插入和删除操作的场景，链式存储方式可能更为合适。在实际应用中，我们应灵活选择存储方式，以最大化算法的性能和效率。

该分类下的相关小册推荐：

算法面试通关 50 讲

数据结构与算法(下)

数据结构与算法(中)

数据结构与算法(上)

编程之道-算法面试(下)

编程之道-算法面试(上)

业务开发实用算法精讲