二叉树_顺序存储

满二叉树 (Full Binary Tree)
所有分支结点都有存在左子树和右子树，并且所有叶子结点都在同一层上。
完全二叉树 (Complete Binary Tree)
如果一棵具有n个结点的二叉树与满二叉树的前n个结点的结构相同，则称这棵二叉树为完全二叉树。

完全二叉树

---

顺序存储：

重要性质：
对于一棵有n个结点的完全二叉树的结点按照从上至下和从左至右的顺序对所有结点从零开始到 n-1 进行顺序编号，则对于序号为i的结点(0≤i≤n),有：
(1)如果 i=0，则结点i是二叉树的根；如果i>0，则其双亲是结点(i-1)/2（整除）。
(2)如果2i+1≥n，则结点i无左孩子；否则，其左孩子是结点 2i+1。
(3)如果2i＋2≥n，则结点i无右孩子；否则，其右孩子是结点 2i＋2。

对于非完全二叉树的存储一律转为完全二叉树处理，空缺的地方内容为空。

根据上面两点，得到二叉树顺序存储的实现：

定义：

#define MaxSize 100
typedef char ElemType;
typedef struct SeqBinaryTree
{
    ElemType data[MaxSize];
    int node_num;   //完全二叉树状态下的节点数 
}SeqBTree;

获取双亲节点下标：

int Parent_seq(SeqBTree *t, int p)
{
    if(p < 0||p>=t->node_num) return -1;
    return (p-1)/2;
}

左子节点下标：

int LeftChild_seq(SeqBTree *t, int p)
{
    if(p < 0 || (2*p+1) >= t->node_num) return -1;
    return 2*p + 1;
}

右子节点下标：

int RightChild_seq(SeqBTree *t, int p)
{
    if(p<0 || (2*p+2)>=t->node_num) return -1;
    return 2*p + 2;
}

主函数测试：

#include<stdio.h> 
void main()
{
    SeqBTree t;
    int i,x;
    for(i=0; i<10; i++)
    {
        t.data[i] = 'A' + i;
        t.node_num++;
    }
    x = Parent_seq(&t,5);
    printf("%c\n", t.data[x]);  
}

总结：
1、对于完全二叉树或接近于完全的二叉树，用顺序存储可以省空间简化操作；否则，都不适宜用顺序存储。
2、顺序存储结构通病：必须预先给出数组的存储空间大小MaxSize。