5.3.3 二叉树的存储结构

既然二叉树是一种数据结构，就得始终明白其任务——存储数据。在使用二叉树的存储数据时，一定要体现二叉树中各个节点之间的逻辑关系，即双亲和孩子之间的关系，只有这样才能向外人展示其独有功能。在应用中，会要求能从任何一个节点直接访问到其孩子，或直接访问到其双亲，或同时访问其双亲和孩子。

1．顺序存储结构

二叉树的顺序存储结构是指用一维数组存储二叉树中的节点，并且节点的存储位置（下标）应该能体现节点之间的逻辑关系，即父子关系。因为二叉树本身不具有顺序关系，所以二叉树的顺序存储结构需要利用数组下标来反映节点之间的父子关系。由5.3.2节中介绍的二叉树的性质（5）可知，使用完全二叉树中节点的层序编号可以反映出节点之间的逻辑关系，并且这种反映是唯一的。对于一般的二叉树来说，可以增添一些并不存在的空节点，使之成为一棵完全二叉树，然后用一维数组顺序存储。

顺序存储的具体步骤如下。

（1）将二叉树按完全二叉树编号。根节点的编号为1，如果某节点i有左孩子，则左孩子的编号为2i；如果某节点i有右孩子，则右孩子的编号为2i+1。

（2）以编号为下标，将二叉树中的节点存储到一维数组中。

例如，图5-7展示了将一棵二叉树改造为完全二叉树及其顺序存储。

图5-7 二叉树及其顺序存储示意图

因为二叉树的顺序存储结构一般仅适合于存储完全二叉树，所以如果使用上述存储方法，会有一个缺点——造成存储空间的浪费或形成右斜树。例如在图5-8中，一棵深度为k的右斜树，只有k个节点，却需要分配2k−1个存储单元。

图5-8 右斜树及其顺序存储示意图

使用Python定义二叉树顺序存储结构数据的格式如下所示。

class BinaryTreeNode(object):
     def __init__(self, data=None, left=None, right=None):
          self.data = data
          self.left = left
          self.right = right
class BinaryTree(object):
     def __init__(self, root=None):
          self.root = root

2．链式存储结构

链式存储结构有两种，分别是二叉链存储结构和三叉链存储结构。二叉树的链式存储结构又称二叉链表，是指用一个链表来存储一棵二叉树。在二叉树中，每一个节点用链表中的一个链节点来存储。二叉树中标准存储方式的节点结构如图5-9所示。

图5-9 链式存储结构

· data：表示值域，目的是存储对应的数据元素。

· LSon和RSon：分别表示左指针域和右指针域，用于存储左子节点和右子节点（即左、右子树的根节点）的存储位置（即指针）。

例如，图5-10所示的二叉树对应的二叉链表如图5-11所示。

图5-10 二叉树

图5-11 二叉链表

图5-12中展示了二叉树和对应的三叉列表。

图5-12 二叉树及对应的三叉列表