数据结构与算法 －二叉树的存储结构

二叉树的存储结构主要分为顺序存储结构和链式存储结构。

顺序存储结构

它是用一组连续的存储单元存储二叉树的数据元素，因此，必须把二叉树的所有结点安排成为一个恰当的序列。

为了在这个序列中的能反映出结点相互位置之间的逻辑关系，可用编号的方法，即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中编号 为i的结点存储在数组中下标为i的分量中，该方法称为“以编号为地址”策略，该策略会从树根起，自上层至下层，每层自左至右的给所有结点编号。

该策略的缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树却需要2^h -1个结点存储空间，而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好。

对于完全二叉树来说，采用以编号作为数组的下标的方法将结点存入一位数组中，也就是将编号为i的结点存入一维数组的以i为下标的数组元素中，这种情况下，不仅节省内存，结点的位置确定也很方便。

对于非完全二叉树，则用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点，这种情况下对存储空间浪费极大。

链式存储结构

二叉链表中结点不仅包含数据域，还包含两个指针域，一个是左孩指针，指向其左孩结点，另一个是右孩指针，指向其右孩结点。

在含n个结点的二叉链表中有2n个指针域，其中 n-1个用来指向结点的左右孩子，其余n+1个空链域。

三叉链表的结点中会多一个指向父结点的指针。

以下是三叉链表的结构表现形式。