二叉树算法 - 二叉树存储

数据结构与算法系列（二十九）

前面我们聊到树和二叉树的定义和特性，树这种结构不能简单通过线性表的前后关系来存储，在线性表中，一个节点只有至多一个前驱节点和至多一个后驱节点，树则不然，一个节点可能有多个后驱节点，这个时候，我们需要通过更加复杂的结构才能存储树。二叉树是一种特殊的树，比多叉树要简单，因为特定节点至多只有两个节点，这就极大简化了相应的数据结构，使得通过线性表就可以实现二叉树的存储。我们后面基本只讨论二叉树，下面我们通过数组和链表来演示如何存储二叉树。

通过数组存储二叉树

对于特定的二叉树而言，比如满二叉树、完全二叉树，它们的节点之间是有一定关联关系的，以下面这棵完全二叉树为例：

我们按照从上到下，从左到右对所有节点编号，可以看到，下一层的左右子节点和对应父节点序号存在某种数学关系，如果父节点的序号是 i，其对应左子节点位于 2i 的位置上，对应右子节点位于 2i + 1 的位置上，我们可以参照这个规则将上述完全二叉树存储到数组中：

注意我们的下标从1开始（根节点），索引为0的下标舍弃，浪费这个空间，以方便计算。这样，我们就可以从根节点开始，依次将所有节点元素存放到数组中，并且可以根据节点间的数学关系很方便地遍历整棵树。此外，由于完全二叉树的特殊性，除了第一个元素之外，该数组不存在任何空间的浪费。由于满二叉树是完全二叉树的子集，所以也可以通过这种方式来存储。

那么其它二叉树呢？当然也可以按照这种思路来做，我们把不存在的节点补全，比如假设上述序号为 4、6、8、9 的元素不存在：

可以看到，我们将不存在的元素补上，只是对应位置值为 null，缺失的节点越多，数组的「空洞」也就越多，如果是极端情况，比如二叉树只包含 1、3、7 三个元素，那么数组中将会存在大量的「空洞」，浪费大量的空间，而且也会影响性能。

综上，数组适合满二叉树、完全二叉树这些特殊二叉树的存储，一些比较稠密的二叉树也可以用数组，如果二叉树比较稀疏就不适合用数组了，我们可以通过链表来存储它们。

通过链表存储二叉树

理论上来说，链表适用于所有的二叉树存储，只不过这里我们需要对线性表中的链表进行扩展，因为二叉树特定节点最多有两个子节点，所有我们在链表结点上设置两个指针域，分别指向左右子节点，所以这种链表结构又被称作二叉链表。我们可以通过一个类表示二叉链表的结点：

class Node
{
    public $data;
    public $left = null;
    public $right = null;

    public function __construct($data)
    {
        $this->data = $data;
    }
}

如果要用二叉链表表示上面的完全二叉树，对应的图示如下：

不管是什么样结构的二叉树，用链表来存储都不会存在空间的浪费。关于二叉树的创建、查找和删除，需要等到介绍完二叉树的遍历才能开始，下一篇我们就来探讨如何遍历二叉树。