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

顺序存储

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

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

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

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

---

链式存储

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

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