5.6 二叉树的存储结构

5.6  二叉树的存储结构

虽然二叉树与树很相似，但它却不是树的特殊情形。在许多情况下，使用二叉树具有结构简单、操作方便的优点。另外，在树的左孩子右兄弟表示法中，实际上已将一棵一般的树转化为一棵二叉树。事实上，在更一般的情形，还可以将树或森林转化为一棵等价的二叉树。

与线性表一样，二叉树也有顺序存储结构和链式存储结构两种。

5.6.1  顺序存储结构

顺序存储一棵二叉树时，首先对该树的节点进行编号，然后以各节点的编号为下标，把各节点的值对应存储到一维数组中。二叉树中各节点的编号与等深度的完全二叉树中位置上节点的编号相同。其编号过程为：首先，将树根节点的编号定为1，然后按照层次从上到下、每层从左到右的顺序对每一节点进行编号。当一个节点的双亲节点的编号为i时，若它为左孩子，则编号为2i，若它为右孩子，则编号为2i+1。

如图5-19（a）所示的二叉树（各节点上方的数字就是该节点的编号）对应的顺序存储结构为图5-19（b）。

（a）带编号的二叉树

（b）对应的顺序存储结构

图5-19  二叉树及其顺序存储结构

二叉树顺序存储结构的类型定义如下：

typedef ElemType SqBinTree[MaxSize];

其中，ElemType为二叉树中节点的数据值类型；MaxSize为顺序表的最大长度。为了方便运算，通常不用下标为0的位置。

在用顺序方法存储的完全二叉树中，找节点的孩子、双亲都很方便。设某节点存储在sqtree[i]中。若i=1，则sqtree[i]是根节点，否则sqtree[i]的双亲是sqtree[i/2]；若2i<n，则sqtree[i]的左孩子是sqtree[2i]，否则sqtree[i]没有左孩子；若2i+l<n，则sqtree[i]的右孩子是sqtree[2i+l]，否则sqtree[i]没有右孩子。

对于一般的二叉树，也可以用这种方法存储。首先，在二叉树中补上若干虚拟节点使其成为完全二叉树，然后，按上述方法对节点进行编号，并将它们存入数组sqtree[l..m]中，其中m等于实际节点个数加上虚拟节点个数。由于虚拟节点在顺序表中占据空单元，在确定节点之间关系时需要进行判断，所以用顺序方法存储一般的二叉树时，存储空间的利用率有时是非常低的。例如，为了存储一棵节点个数和高度都等于10的二叉树，至少需要占用2⁹个元素的空间。

5.6.2  链式存储结构

对于一般的二叉树，通常采用二叉链表表示。链表中的每个节点包含两个指针，分别指向对应节点的左孩子和右孩子（注意在树的孩子兄弟链表存储结构中，每个节点的两个指针分别指向对应节点的第一个孩子和下一个兄弟）。在二叉树的链式存储中，节点的类型定义如下：

typedef struct tnode

{  

   ElemType data;

   struct tnode *lchild,*rchild;

}  BTNode; 

其中，data表示数据域，用于存储放入节点的数据值；lchild和rchild分别表示左指针域和右指针域，分别存储左孩子和右孩子节点（即左右子树的根节点）的存储地址。

例如，图5-19（a）中二叉树的二叉链存储结构如图5-20所示。

图5-20  二叉链存储结构

这种存储结构的优点是：访问节点的孩子很方便。有时为了方便访问节点的双亲可在每个节点中再增加一个指向双亲的指针域parent，就构成了二叉树的三叉链表。其节点结构如图5-21所示。

图5-21  二叉树的三叉链表节点结构