三、用数组实现完全二叉树

用顺序方法存储二叉树，就是要把所有结点按照一定的次序顺序存储到一片连续的存储单元中。适当安排这个结点的线性序列，可以使结点在序列中的相互位置反映出二叉树结构的部分信息，但一般说来这样的信息是不足以刻画整个结构的，还要在结点中附加一些其他的必要信息，以完全地反映整个结构。
    完全二叉树中除最下面一层外，各层都被结点充满了，每一层结点的个数恰是上一层结点个数的两倍。因此，从一个结点的编号就可以推知它的父母，左、右子女，兄弟等结点的编号。
    当2i+1≤n时，结点i的左子女是结点2i+1，否则结点i没有左子女。
    当2i+2≤n时，结点i的右子女是结点2i+2，否则结点i没有右子女。
    当0<i<n时，结点的父母是结点 。
    当i为偶数且0<i<n时，结点i的左兄弟是结点i-1，否则结点i没有左兄弟。
    当i为奇数且i+1<n时，结点i的右兄弟是结点i+1，否则结点i没有右兄弟。
    对于完全二叉树这一特殊情况，结点的层次序列就足以反映整个二叉树的结构。因此完全二叉树可以使用数组方式进行顺序存储。