一、二叉树
二叉树(逻辑结构)：
二叉树是n(n>=0)个结点的有限集合
1、n=0时，二叉树为空
2、n>0时，由根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树也分别是一颗二叉树
注意：
二叉树是有左右之分的
二叉树的五种基本形态
1、满二叉树
满二叉树定义：
一棵高度为h，并且有(2^h)−1个结点的二叉树为满二叉树。
特点：
所有的叶子结点都在最后一层
性质：
对于编号为 i 的结点，若存在，其双亲的编号为向下取整(i/2)，左孩子为2i，右孩子为2i+1
2、完全二叉树
完全二叉树的定义：
设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树
完全二叉树的性质：
1、若i<=向下取整(n/2)，则结点i为分支结点，否则为叶子结点
2、叶子结点只可能在层次最大的两层上出现。对于最大层次的叶子结点，都依次排在最左边的位置上
3、度为1的结点若存在，则可能有一个，且是编号最大的分支节点，并孩子结点一定是左结点
3、二叉排序树
二叉排序树又称二叉查找树
一颗二叉树，若树非空则具有如下
性质：
对任意结点若存在左子树或右子树，则其左子树上所有结点的关键字均小于该结点，右子树上所有结点的关键字均大于该结点
特点：
可为空树，左子树所有节点<根节点<右子树，不存在值相等的节点
二叉排序树也是一种以递归的形式来定义
4、平衡二叉树
定义：
树上
任意结点
的左子树和右子树的深度只差不超过1
特点：
是一种结构平衡的二叉搜索树，即叶子节点深度差不超过1，能够在O(logn)内完成插入、查找和删除操作,结构如图所示，常见的平衡二叉树有AVl树、红黑树等
AVL树
又被称为高度平衡树，是最先发明的自平衡二叉查找树，任何节点的两个儿子子树的高度最大差别为1，增加和删除可能需要通过一次或多次树旋转来重新平衡这个树
5、红黑树
特点：
红黑树是一种自平衡二叉查找树，又称为“对称二叉B树”，除了满足所有二叉查找树的要求之外还需要满足以下要求：
（1）节点是红色或者是黑色的
（2）跟节点是黑色的
（3）每个叶子节点都是黑色的（叶子是NIL节点）
（4）每个红色节点必须有两个黑色节点（从叶子到根节点的所有简单路径上不可能有两个连续的红色节点）
（5）从任一节点到其每个叶子的所有简单路径都饱和相同数目的节点
注:
NIL节点就是空节点，二叉树中庸NIL节点代替NULL
简单路径：指顶点序列中顶点不重复出现的路径
二、二叉树的性质
1、非空二叉树上的叶子结点数等于度为2的结点数加1，即
n
0
=
n
2
+
1
（
n
0
指叶子结点，
n
2
指度为2的结点）
解释：
n
0
=
n
2
+
1
，是由
n
=
n
0+
n
1
+
n
2
，
n
=
n
1
+
2
n
2
+
1
这两个式子相削得来的。n代表总结点数，式子1由来是，度为0和度为1、度为2的结点相加就是总结点数；式子2由来是，度为1的结点乘以1（因为度为1的结点有一个子结点，所以乘以1），加上度为2的结点乘以2（因为度为2的结点有两个结点，所以乘以2），最后加1，是因为还有一个根结点没包含进来
2、非空二叉树上第K层上至多有2^(k-1)个结点(k>=1)
解释：用数学归纳法可以得出
3、高度为h的二叉树至多有2^h-1个结点（h>=1）
解释：由第2个性质可以得到第3个性质，把每层的结点数相加可得
4、对完全二叉树按从上到下、从左到右的顺序依次编号1，2，…，n，则有一下关系：
1) 当i>1时，结点i的双亲结点标号为向下取整(i/2)，即当i为偶数时，其双亲结点的编号为i/2，他是双亲结点的左孩子；当i为奇数时，其双亲结点的编号为(i-1)/2，他是双亲结点的右孩子。
2)当2i<=n时，结点i的左孩子编号为2i，否则无左孩子
3) 当2i+1<=n时，结点i的右孩子编号为2i+1，否则无右孩子
4) 结点i所在层次为向下取整(log
2
i
)+1
5) 具有n个(n>0)结点的完全二叉树的高度为向下取整(log
2
n
)+1或向上取整log
2
(n+1)
本文章参考于《王道考研》
欢迎大家阅读，本人见识有限，写的博客难免有错误或者疏忽的地方，还望各位大佬指点，在此表示感谢。