二叉树
二叉树是n(n>=0)个结点的有限集合
1、n=0时，二叉树为空
2、n>0时，由根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树叶分别是一棵二叉树。
二叉树和度为2的有序树
1、二叉树可以为空，而度为2的有序树至少有三个结点
2、二叉树的孩子结点始终有左右之分，而度为2有序树的孩子结点次序是相对的
满二叉树
一颗高度为h，且有-1个结点的二叉树为满二叉树
对于编号为i的结点，若存在，其双亲的编号为[i/2]，左孩子为2i，右孩子为2i+1
完全二叉树
设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树
完全二叉树性质：
1、若i<=n/2，则结点i为分支结点，否则为叶子结点
2、叶子结点只可能在层次最大的两层上出现。对于最大层次的叶子结点，都依次排在最左边的位置上。
3、度为1的结点若存在，则可能有一个，且是编号最大的分支结点，并孩子结点一定是左结点。
二叉排序树
一颗二叉树，若数非空，则具有如下性质：
对任意结点若存在左子或右子树。则其左子树上所有结点的关键字均小于该结点，右子树上所有结点的关键字均大于该结点。
平衡二叉树
树上任意结点和左子树和右子树的深度之差不超过1
二叉树的性质
1、非空二叉树上的叶子结点数等于度为2的结点数加1，即=
+1
2、非空二叉树上的第k层至多有2^k-1个结点(k>=1)
3、高度为h的二叉树至多有-1个结点(k>=1)
4、结点i所在层次为+1
5、对完全二叉树从上到下，从左到右的顺序依次编号1,2,3,……,n，则有以下关系：
5.1 当i>1时，结点i的双亲结点标号为i/2，即i为偶数时，其双亲结点编号为i/2，他是数亲结点的左孩子；当i为奇数时，其双亲结点的编号为(i-1)/2，他是双亲结点的右孩子
5.2 当2i<=n时，结点i的左孩子编号为2i，否则无左孩子
5.3 当2i+1<=n时，结点i的右孩子编号为2i+1，否则无右孩子
6、具有n个(n>0)结点的完全二叉树的高度为[]+1或
二叉树的顺序存储：用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素
在完全二叉树中依次编号，对于结点i：若存在左孩子，则编号为2i；若存在右孩子，则编号为2i+1
顺序存储最坏情况会非常浪费存储空间，比较适合完全二叉树。
二叉树的链式存储：用链表来存放一颗二叉树，二叉树中每个结点用链表的一个结点来存储。
typedef struct BiTNode{
Element data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
含有n个结点的二叉链表中，有n+1个空链域。
