二叉树（Binary Tree）
简单地理解，满足以下两个条件的树就是二叉树：
- 本身是有序树；
- 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；
二叉树的性质
经过前人的总结，二叉树具有以下几个性质：
- 性质1：二叉树中，第 i 层最多有$2^{i-1}$ 个结点。
- 性质2：如果二叉树的深度为 K，那么此二叉树最多有 $2^K-1$ 个结点（k>=1）。
- 性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
- 性质4：在任意一棵二叉树中，若叶子结点的个数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$。
二叉树还可以继续分类，衍生出满二叉树和完全二叉树。
性质1：二叉树第i层上的结点数目最多为 $2^{i-1}$ (i≥1)
证明：下面用"数学归纳法"进行证明。
(01) 当i=1时，第i层的节点数目为 $2^{i-1}=2^{0}=1$。因为第1层上只有一个根结点，所以命题成立。
(02) 假设当i>1，第i层的节点数目为 $2^{i-1}$。这个是根据(01)推断出来的！
下面根据这个假设，推断出"第(i+1)层的节点数目为 $2^{i}$ “即可。
由于二叉树的每个结点至多有两个孩子，故"第(i+1)层上的结点数目” 最多是 “第i层的结点数目的2倍”。即，第(i+1)层上的结点数目最大值 $=2×2^{i-1}=2^{i}$。
故假设成立，原命题得证！
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)
证明：在具有相同深度的二叉树中，当每一层都含有最大结点个数时，其二叉树中结点数最多。利用"性质1"可知，深度为k的二叉树的结点数至多为：
$2^0+2^1+…+2^{k-1}=2^{k}-1$
故原命题得证！
性质3：包含n个结点的二叉树的高度至少为 $log_2 (n+1)$
证明：根据"性质2"可知，高度为h的二叉树最多有 $2^{h}–1$ 个结点。反之，对于包含n个节点的二叉树的高度至少为 $log_2(n+1)$。
性质4：在任意一棵二叉树中，若叶子结点的个数为 $n_0$，度为2的结点数为 $n_2$，则$n_0=n_2+1$
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)=“0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)"。由此，得到等式一。
(等式一) $n=n_0+n_1+n_2$
另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：$n_1+2n_2$。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) $n=n_1+2n_2+1$
由(等式一)和(等式二)计算得到：$n_0=n_2+1$。原命题得证！
满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
如上图所示就是一棵满二叉树。
满二叉树除了满足普通二叉树的性质，还具有以下性质：
- 满二叉树中第 i 层的节点数为 2n-1 个。
- 深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
- 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
- 具有 n 个节点的满二叉树的深度为 $log_2(n+1)$。
完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
如上图所示是一棵完全二叉树，图 b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊$log_2n$⌋+1。
⌊$log_2n$⌋ 表示取小于 $log_2n$ 的最大整数。例如，⌊$log_24$⌋ = 2，而 ⌊$log_25$⌋ 结果也是 2。
对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如上图），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
- 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
- 如果 2*i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2*i 。
- 如果 $2i+1>n$ ，则结点 i 肯定没有右孩子；否则右孩子是结点 $2i+1$ 。
完全二叉树的编号问题
以上是将根结点编号为0的规律，比较符合数组下标以0开始的访问方式。有另外的一些以1开始的规律，虽然不是错的，但是不太适合写代码：
若结点的高度为h，则该结点的左儿子是2*h，右儿子是左儿子加1，即2*h+1。反过来，如果儿子的编号为y，则父结点的编号是(int)x/2。高度h的规律，其实是上面的树的编号从1开始，而不是从0开始。
所以问题也来了，树的编号从0开始，从1开始，从n开始呢，表达式是怎样呢。直观上可以知道，结点和儿子的关系是不变的，变的只是编号，所以应该可以利用其中一个规律推导出编号改变后的表达式。
首先，把完全二叉树用数组的形式表示： 0 开始：0 1 2 3 4 5 6 7… 1 开始：1 2 3 4 5 6 7… 2 开始：2 3 4 5 6 7…
可以看出，总体编号是往左移的。以编号0开始为例，左儿子为x，右儿子为y，当前结点为k，那么规律是x = 2*k + 1和y = 2*k + 2，其中x、y、k都是数组里面的元素。
当以编号1开始时，总体编号相当于往左移动了1位。其中，相当于x往左移动了1位，相当于y向左移动了1位，k也往左移动了1位，因为它们都是数组里面的元素。
设新的关系，左儿子为x1，右儿子为y1，当前结点为k1，那么得到关系x1 - 1 = x、y1 - 1 = y和k1 - 1 = k，代入编号为0的表达式：
x = 2*k + 1 => x1 - 1 = 2*(k1 - 1) + 1 推导出 x1 = 2*k1
y = 2*k + 2 => y1 - 1 = 2*(k1 - 1) + 2 推导出 y1 = 2*k1 + 1。也可以直接使用右儿子 = 左儿子 + 1直接得出。
所以，也即是说，当编号从1开始，结点与儿子结点的关系是x = 2k和y = 2k+1，这和高度h那里得到的表达式一致。
当编号从n开始，就相当于数组往左移动了n位，思路参考上面，和高中数学里移动x、y坐标轴一样（没想到是高中数学）。
二叉树的存储结构
二叉树的存储结构有两种，分别为顺序存储和链式存储。
二叉树的顺序存储结构
二叉树的顺序存储，指的是使用**顺序表（数组）**存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。
有读者会说，满二叉树也可以使用顺序存储。要知道，满二叉树也是完全二叉树，因为它满足完全二叉树的所有特征。
普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可。如下图所示：
上图中，左侧是普通二叉树，右侧是转化后的完全（满）二叉树。
完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。
例如，存储上图所示的完全二叉树，其存储状态如下图所示：
同样，存储由普通二叉树转化来的完全二叉树也是如此。例如，上图中普通二叉树的数组存储状态如下图所示：
由此，我们就实现了完全二叉树的顺序存储。
不仅如此，从顺序表中还原完全二叉树也很简单。我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,…），若节点 i 有左右孩子，则其左孩子节点为 2*i，右孩子节点为 2*i+1。此性质可用于还原数组中存储的完全二叉树。
二叉树的链式存储结构
其实二叉树并不适合用数组存储，因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或多会存在空间浪费的现象。
如上图所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，上图对应的链式存储结构如下图所示：
由上图可知，采用链式存储二叉树时，其节点结构由 3 部分构成（如下图所示）：
- 指向左孩子节点的指针（Lchild）；
- 节点存储的数据（data）；
- 指向右孩子节点的指针（Rchild）；
三叉链表
其实，二叉树的链式存储结构远不止上图所示的这一种。例如，在某些实际场景中，可能会做 “查找某节点的父节点” 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点，如下图所示：
这样的链表结构，通常称为三叉链表。
Reference
- 数据结构概述 - http://data.biancheng.net/intro/