一、二叉树的概念
1.1二叉树
一棵二叉树是结点的一个有限集合，该集合:
1. 可以为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
从上图可以看出：
1. 二叉树不存在度大于2的结点；
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
任意二叉树都应该是以下几种情况复合而成：
现实中也是存在这种树的：
1.2 二叉树的分类
二叉树分为两类：满二叉树和完全二叉树。
1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是2^K-1，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
1.3二叉树的性质
1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1个。
3. 对任何一棵二叉树，如果度为0，其叶结点个数为N0， 度为2的分支结点个数为N2，则有
N0=N2+1.
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1);(ps：是log以2为底，n+1为对数).
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点。
2. 若2i+1<n,则有左孩子，若2i+1>=n，则无左孩子。
3. 若2i+2<n,则有右孩子，若2i+2>=n，则无右孩子。
总结一下，我觉得比较重要的有这几点：
1、第K层的节点个数为2^(K-1).
2、一个满二叉树的节点个数为2^K-1。
3、双亲结点找左孩子：leftchild=parent*2+1； rightchild=parent*2+2.(leftchild，rightchild，parent均为下标)。
4、孩子找双亲结点：parent=(child-1)/2
5、度为0的叶节点个数为N0，度为2的分支节点个数为N2，则有N0=N2+1。因为一个二叉树无非由三种节点组成，度为0的叶节点，度为1和度为2的分支节点组成。所以总的节点个数就是N=N0+N1+N2；掌握叶节点和度为2的分支节点的关系有助于解题。
6、完全二叉树的节点个数区间为：(设层数为K)：[ 2^(k-1)，2^k-1 ].
1.4二叉树的存储结构
1. 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
2. 链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，链式结构仅作简单介绍，并不会详细讲解。
二、堆
2.1堆的概念及结构
1、堆的概念
如果有一个集合，它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并且满足双亲结点小于孩子，或者双亲结点大于孩子，则成为大堆(或小堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
这里我们可以看出堆的性质：
1、堆中某个节点的值总是不大于或不小于其双亲节点的值。
2、堆总是一棵完全二叉树。
