顺序存储结构

    　该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。

1．完全二叉树结点编号
（1） 编号办法
    　在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。
　　【例】如下图所示。
   

（2） 编号特点
   　 完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是k_i(1≤i≤n)，则有：
　　①若i>1，则k_i的双亲编号为 ；若i=1，则K_i是根结点，无双亲。
　　②若2i≤n，则K_i的左孩子的编号是2i；否则，K_i无左孩子，即K_i必定是叶子。因此完全二叉树中编号 的结点必定是叶结点。

　　③若2i+1≤n，则K_i的右孩子的编号是2i+1；否则，K_i无右孩子。
　　④若i为奇数且不为1，则K_i的左兄弟的编号是i-1；否则，K_i无左兄弟。
　　⑤若i为偶数且小于n，则K_i的右兄弟的编号是i+1；否则，K_i无右兄弟。

2．完全二叉树的顺序存储
    　将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[0..n]中。
  其中：
    bt[1．．n]用来存储结点
    bt[0]不用或用来存储结点数目。
　【例】表6.1是图6.8所示的完全二叉树的顺序存储结构，bt[0]为结点数目，b[7]的双亲、左右孩子分别是bt[3]、bt[l4]和bt[15]。
 

3．一般二叉树的顺序存储
（1） 具体方法
　　① 将一般二叉树添上一些 "虚结点"，成为"完全二叉树"
　　② 为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号
　　③ 将结点按编号存入向量对应分量，其中"虚结点"用"∮"表示

　【例】图6-9中单支树的顺序存储结构如下图
       

（2） 优点和缺点
　　① 对完全二叉树而言，顺序存储结构既简单又节省存储空间。
　　② 一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。
  　　【例】最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间。
　　③在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。

4．二叉树的顺序存储结构类型定义
   【参见参考书】

下一页