顺序存储结构
该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。
1．完全二叉树结点编号
（1） 编号办法
在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。
【例】如下图所示。
（2） 编号特点
完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是ki(1≤i≤n)，则有：
①若i>1，则ki的双亲编号为
②若2i≤n，则Ki的左孩子的编号是2i；否则，Ki无左孩子，即Ki必定是叶子。因此完全二叉树中编号
③若2i+1≤n，则Ki的右孩子的编号是2i+1；否则，Ki无右孩子。
④若i为奇数且不为1，则Ki的左兄弟的编号是i-1；否则，Ki无左兄弟。
⑤若i为偶数且小于n，则Ki的右兄弟的编号是i+1；否则，Ki无右兄弟。
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．二叉树的顺序存储结构类型定义
【参见参考书】
链式存储结构
1．结点的结构
二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构为：
2．结点的类型说明
typedef char DataType； //用户可根据具体应用定义DataType的实际类型
typedef struct node{
DataType data；
Struct node *lchild，*rchild； //左右孩子指针
}BinTNode； //结点类型
typedef BinTNode *BinTree；//BinTree为指向BinTNode类型结点的指针类型
3．二叉链表（二叉树的常用链式存储结构）
在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root，就构成了二叉树的链式存储结构，并将其称为二叉链表。
【例】下面左图所示二叉树的二叉链表如下面中图所示。
注意：
① 一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。
② 具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。
4．带双亲指针的二叉链表
经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。
【例】上面右图是上面左图所示的二叉树的带双亲指针的二叉链表。
注意：
二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。
转载自：http://student.zjzk.cn/course_ware/data_structure/web/shu/shu6.2.3.2.htm