概念
一棵二叉树是结点的一个有限集合，该集合:
1.或者为空
2.由一个根节点加上两棵别称为左子树和右子树的二叉树组成
从上图可以看出：
①二叉树不存在度大于2的节点
②二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种复合而成
特殊的二叉树
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2 k − 1 2^k-1 2k−1，则它就是满二叉树。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。(完全二叉树的高度-1的各层均是满的，最后一层从左往右按顺序连续排列，但最后一层不一定满)
二叉树的性质
1.若规定根节点的层数为1，则一颗非空二叉树的第i层最多有 2 i − 1 2^{i-1} 2i−1个结点。
证明：根结点有一个结点，每个结点最多可以分出2个分支，因而深度每增加1，层结点数就会×2。故可以得到规律：第i层最多有 2 i − 1 2^{i-1} 2i−1个结点。
2.若规定根结点的层数为1，则深度为h的二叉树的最大结点数是 2 h − 1 2^h-1 2h−1。
证明：由上一个性质可以知道：第i层最多有 2 i − 1 2^{i-1} 2i−1个结点。也就是说，二叉树的总结点是首项为1，公比为2的等比数列，由等比数列可知 ( a 1 ( 1 − q n ) ) / ( 1 − q ) (a_{1}(1-q^n))/(1-q) (a1(1−qn))/(1−q)= ( 1 × ( 1 − 2 h ) ) / ( 1 − 2 ) (1×(1-2^{h}))/(1-2) (1×(1−2h))/(1−2)= 2 h − 1 2^{h}-1 2h−1。
3.对任何一颗二叉树，如果度为0的叶结点个数为 n 0 n_{0} n0，度为2的分支结点个数为 n 2 n_{2} n2，则有 n 0 = n 2 + 1 n_{0}=n_{2}+1 n0=n2+1。
4.若规定根结点的层数为1，具有n个结点的满二叉树的深度为 l o g 2 ( n + 1 ) log_{2}(n+1) log2(n+1)。
证明：由上面的结论可知深度为h的二叉树的最大结点数是 2 h − 1 2^h-1 2h−1，可以得到 n = 2 h − 1 n=2^h-1 n=2h−1，两边取对数得 h = l o g 2 ( n + 1 ) h=log_{2}(n+1) h=log2(n+1)
5.对于具有n个基点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：
①若i>0，i位置结点的双亲结点序号为
(
i
−
1
)
/
2
(i-1)/2
(i−1)/2；i=0，i为根节点编号，无双亲结点
②若2i+1<n，有孩子序号为2i+1，2i+1>=n则没有左孩子
③若2i+2<n，有孩子序号为2i+2，2i+2>=n则没有右孩子
二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
1.顺序存数
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆会在下一篇文章专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
可以通过2i+1找到结点的左孩子，2i+2找到结点的有孩子。下图中，右侧不是完全二叉树，但为了B和C能找到自己的孩子，3和5下标位置必须空出来。如果是一个全部结点只有右子树的树，则会有大量的空间浪费。
2.链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链。
typedef int TreeDataType;
struct Node2
{
struct Node2* leftChild; //保存左孩子
struct Node2* rightChild; //保存右孩子
TreeDataType val; //值域
}
struct Node3
{
struct Node3* parent; //指向父节点
struct Node3* leftChild; //指向左孩子结点
struct Node4* rightChild; //指向右孩子结点
TreeDataType val; //值域
}