数据结构——二叉树存储结构

顺序存储

用一组连续的存储单元依次自上而下、自左向右存储完全二叉树上的结点元素。

完全二叉树：依次编号，结点$i$，左孩子$2i$，右孩子$2i+1$。

非完全二叉树：无法进行存储，可将其补成完全二叉树，空结点为$0$

**缺点**：占用内存空间较多，适用于完全二叉树

---

链式存储

用链表来存放二叉树，二叉树中每个结点用链表一个链结点来存储。

typedef struct BiTNode{
    ElemType data;     // 保存数据
    struct BiTNode *lchild,*rchild;    // 保存孩子结点
}BiTNode,*BiTree;