二叉树的存储结构

一 概述

二叉树的存储结构可以分为顺序存储和链式存储两种存储结构。

二 顺序存储结构

二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下，自左至右存储完全完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一个一维数组下标为i-1的分量中。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储结构比较合适，树中结点的序号可以唯一的反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

但是对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏的情况下，一个高度为h且只有h个结点的单支树却需要占据近2^h-1个存储单元。

采用顺序存储结构的时候，建议从数组下标为1开始存储树种的结点，若从数组下标0开始存储，不满足以下情况，即当结点A存储在下标为i=0的位置时，无法根据确定其左孩子为2i和其右孩子为(2i+1)。

三 链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉树表至少包含3个域：数据域data，左指针域lchild，右指针域。

二叉树的链式存储结构代码

typedef struct BiTNode{
    ElemType data;    //数据域
    struct BiTNode, *lchild,*rchild; //左，右孩子指针
}BiTNode,*BiTree;

使用不同的存储结构时，实现二叉树操作的算法也是不同的，我们应该能够根据二叉树的实际形态和需要进行的运算来选择合适的存储结构。