1、二叉树的性质
*******、二叉树是m叉树的一种情况
*******、重要计算靠点
对任何一棵二叉树T，若其终端结点树为 N0，度为2的结点数是N2，则N0 = N2 + 1，证明如下：
（1）、设N1为二叉树T中度为1的结点数，因为二叉树中所有结点的度均小于还活着等于2，所以其结点总数是 N = N0 + N1 + N2
（2）、二叉树中的分支数（总度数）设为B，则 N = B+1（可以自己画个树随便验证一般性结论），又由于这些分支是由度为1或者是度为2的结点射出，所以总的分支数或者是总度数是 B = N1 + 2N2，所以必有 N = N1 + 2N2 + 1
（3）、由上面的式子联立，即 N0 = N2 + 1 成立！
*******、二叉树的左右子树不能颠倒，也即二叉树是有序树
*******、满二叉树
一棵高度为h，总共有2^h-1个结点的二叉树！
特点：
（1）、只有最后一层有叶子结点
（2）、不存在度为1的结点
（3）、按照层序遍历的顺序编号，结点为 i 的左孩子为 2i，右孩子为 2I+1。其父节点是[i/2]（向下取整）
*******、完全二叉树
完全二叉树是满二叉树的特例，就是在满二叉树的基础上将编号更大结点去掉，此时剩下的结点构成为二叉树就是完全二叉树！
特点：
（1）、只有可能在最后两层出现叶子结点
（2）、最多只有一个度为1的结点，并且是根节点的左孩子结点，不可能是根节点的右孩子，如果是根节点的右孩子就不可能是完全二叉树
（3）、按照层序遍历的顺序编号，结点为 i 的左孩子为 2i，右孩子为 2I+1。其父节点是[i/2]（向下取整）
*******、完全二叉树的两个重要特性
（1）、具有N个结点的完全二叉树的深度为[log2N]+1（向下取整），或者是[log2（N+1）]（向上取整）
（2）、如果对一棵有n个结点的完全二叉树（其深度是**[log2N]+1（向下取整）**）的结点按照层序遍历（从第一层到[log2N]+1（向下取整）层，每层从左到右），则对任何一个结点都有i（1<= i <=n）
*如果 i = 1，则结点 i 是二叉树的根节点，无双亲；如果 i > 1，则其双亲是 [i/2]（向下取整）
*如果 2i > n，则i没有左孩子，因为左孩子是 2i
*如果 2i + 1 > n，则结点没有右孩子；因为右孩子的编号是 2i + 1;
2、二叉树的存储结构
*******、顺序存储结构
//-------------------------顺序存储结构------------------------
typedef struct{
ElemType *elem; //储存空间的基地址
int length; //结点个数
}SqBiTree;
（1）、顺序存储结构使用一组地址连续的存储单元来存储数据，为了能够在存储结构中反映出结点之间的逻辑关系，必须将二叉树中的结点按照已定的规律安排在这组单元中。
（2）、对于完全二叉树，只要从根开始按照层序遍历存储即可，依次自上而下、自左到右存储结点元素，即将完全二叉树上编号为 i 的结点元素存储在顺序表中！
（3）、对于非完全二叉树，顺序地将每个结点与完全二叉树中上的结点相对应，存储在一维数组的相应分量中，对于没有结点的使用0代替即可！
（4）、由上面分析可得，这种顺序存储结构仅适用于完全二叉树，因为非完全二叉树按照完全二叉树的方式存储会造成空间的极大浪费！所以对于一般的二叉树使用链式存储更加合适！
（5）、在顺序表中存储完全二叉树有个特性，所有序号大于 [N/2] （向下取整）的结点都是叶子结点，小于 [N/2] （向下取整）的结点都是非叶子结点，这个特性会在第八章中的的堆排序中将一个无序序列建设成一个大根堆或者小根堆的时候使用到！
*******、链式存储结构
//-------------------------链式存储结构------------------------
//二叉链表
typedef struct BiNode{ //结点
ElemType data; //数据域
struct BiNode *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;
使用链式存储结构容易证得，在含有n个结点的二叉链表中有 n + 1个空链域，利用这 n + 1个空链域可以得到另一种存储结构-----------------------------------线索链表！
相对应的还有三叉链表，三叉链表中定义了找到父节点的指针，所以相比于二叉链表的好处是可以找到其父节点！
//-------------------------链式存储结构------------------------
//三叉链表
typedef struct BiNode{ //结点
ElemType data; //数据域
struct BiNode * parent,*lchild,*rchild; //指向父节点的指针，以及左右孩子指针
}BiNode,*BiTree;