6.7　二叉树的存储结构

6.7.1　二叉树顺序存储结构

前面我们已经谈到了树的存储结构，并且谈到顺序存储对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

先来看看完全二叉树的顺序存储，一棵完全二叉树如图6-7-1所示。

6.7　二叉树的存储结构 - 图1

图6-7-1

将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如图6-7-2所示。

6.7　二叉树的存储结构 - 图2

图6-7-2

这下看出完全二叉树的优越性来了吧。由于它定义的严格，所以用顺序结构也可以表现出二叉树的结构来。

当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把不存在的结点设置为“∧”而已。如图6-7-3，注意浅色结点表示不存在。

6.7　二叉树的存储结构 - 图3

图6-7-3

考虑一种极端的情况，一棵深度为k的右斜树，它只有k个结点，却需要分配2

k-1个存储单元空间，这显然是对存储空间的浪费，例如图6-7-4所示。所以，顺序存储结构一般只用于完全二叉树。

6.7　二叉树的存储结构 - 图4

图6-7-4

6.7.2　二叉链表

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。结点结构图如表6-7-1所示。

表6-7-1
lchild data rchild

其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

以下是我们的二叉链表的结点结构定义代码。

  1. /* 二叉树的二叉链表结点结构定义 */
  2. /* 结点结构 */
  3. typedef struct BiTNode                  
  4. {
  5.     /* 结点数据 */
  6.     TElemType data;                     
  7.     /* 左右孩子指针 */
  8.     struct BiTNode *lchild, *rchild;    
  9. } BiTNode, *BiTree;

结构示意图如图6-7-5所示。

6.7　二叉树的存储结构 - 图5

图6-7-5

就如同树的存储结构中讨论的一样，如果有需要，还可以再增加一个指向其双亲的指针域，那样就称之为三叉链表。由于与树的存储结构类似，这里就不详述了。