何为二叉树
二叉树，英文名Binary Tree，顾名思义，二叉树就是每个节点最多有2个子节点的树，这个说法好理解，但是不够严谨。具体的说：
- 二叉树节点是有限个，无限对于计算机来说处理不了。
- 二叉树可以由0个节点，这种属于空二叉树。
- 二叉树如果有超过0个节点，则必有根节点，而且根节点最多有两个子节点，且子节点为根节点的子树也为二叉树。
注意二叉树的左右子树，是有顺序的，不能互相调换，下图为经典的二叉树。
特殊二叉树
二叉树是数据结构中非常重要的一种，可以说是鼎鼎大名，而且延伸出了许多特殊的二叉树，此处先了解下他们的情况。
斜树
顾名思义来，所有节点都往一边倾斜的二叉树叫做斜树，都往左倾斜即为左斜树，都往右倾斜即为右斜树，如下图。
满二叉树
什么叫满啊，英文是full，充满、满溢、不缺少的意思，也就是说所有分支节点都有左右子树，且所有叶子都在同一层，称为满二叉树。
在同样深度的二叉树中，满二叉树的节点个数最多，叶子数也最多，所以称之为满绝对不是浪得虚名。如下图为满二叉树：
完全二叉树
刚刚说完了有个满二叉树，好像这次的新概念完全二叉树，应该差不多啊。完全二叉树更多的是数学上的一种完全，表示从小到大一个不缺，叫做“完全”。
具体到二叉树上，完全二叉树是指按层序编号，如果是从第一个节点到最后一个节点都是依次排下来的，那么这颗二叉树即为完全二叉树，如下图，第三张没有按照应有顺序依次排下来，所以不是完全二叉树。
二叉树的性质
性质是从概念观察、思考得来，我们此处总结归纳一些有用的性质：
性质1：二叉树的第n层，最多有2^(n-1)个节点
n=1，第一层，最多1个节点，2^(1-1)=1
n=2，第二层，最多2个节点，2^(2-1)=2
n=3，第三次，最多4个节点，2^(3-1)=4
性质2：深度为n的二叉树，最多有2^n-1个节点
第一层最多有：2^0
第二层最多有：2^1
第三层最多有：2^2
所以深度为n的二叉树，最多有：2^0 + 2^1 + 2^2+...+2^(n-1)个节点，根据等比数列的求和公式，即为2^n-1个。
性质3：如果二叉树叶子节点数为a，度为2的节点数为c，则a=c+1
二叉树中，叶子节点度为0，除了叶子节点还有度为1的节点和度为2的节点，设总节点数为n，度为1的节点数为b，则
式子1
n=a+b+c
观察二叉树能发现，除了根节点的上头没有一个连接线，其他节点都有，如下图，所以连接线的数量为n-1。
从另一个角度出发，连接线的数量为度数，即为b+2c，所以有：
式子2：
n-1=b+2c
将式子1带入式子2，得出：a=c+1，简单的数学题嘛。
还有一些性质，论证起来比较复杂，此处暂且不表了。