鄙人乃一介初学者，文中及代码中难免出错，恳请同志们批评指正！

或许你曾看到过这样的图片，这张图中的树，在每一个分叉点都分为两个枝桠，这就是一棵非常形象的“二叉树”。

?二叉树的定义

如果我们把上一篇文章中的树改造成以下的结构：每一个内部结点的度最大为2，且规定左右两个子结点是有序的，那么这就是二叉树。如图1中所示。

那么我们来给二叉树下一个定义：
二叉树( Binary Tree)是n(n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

⭐1.二叉树的特点

1. 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
2. 左子树和右子树是有顺序的，次序不能任意颠倒。
3. 即使树中某结点只有一棵子树， 也要区分它是左子树还是右子树.如下图2中，树1和树2是同一棵树，但它们却是不同的二叉树。

那么根据二叉树特殊的限制，一个二叉树应该有五种基本形态：

1. 空二叉树；
2. 只有一个根节点；
3. 根结点只有左子树；
4. 根结点只有右子树；
5. 根结点既有左子树又有右子树。

⭐2.特殊的二叉树

?（1）斜树

顾名思义，斜树一定是斜的。我们说：所有结点只有左子树的二叉树为左斜树，所有节点只有右子树的二叉树为右斜树。二者统称为斜树。
如下图3中的树1就是左斜树，树2就是右斜树。

?（2）满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
如图4中的二叉树，就是一棵满二叉树：

可以看到，这棵二叉树中，除了叶子结点，其他每一个结点都有左右子树，并且所有的叶子结点都在同一层。满二叉树满足：
(1)叶子只能出现在最下一面层。出现在其他层就不可能达成平衡。
(2)非叶子结点的度一定是2，即非叶子结点一定都有左右子树。
(3)在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

?（3）完全二叉树

上面我们说了满二叉树，那么什么是完全二叉树呢？
我们说：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。
还有一个比较拗口的定义：对一棵具有n个结点的二叉树按层序编号，如果编号为i (1≤i≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树，如图5所示。

这里我们说和满二叉树对比，首先我们应该区分“满”和“完全”。根据定义，我们发现，满二叉树一定是完全二叉树，但是，完全二叉树不一定是满二叉树。

观察图5我们发现，完全二叉树其实就是相当于把满二叉树的最后一层的几个结点去掉了。而且去掉的时候是从最后一个结点依次向前去掉的，中间并没有隔着去掉。也就是说，如果满二叉树和完全二叉树深度相同，那么按照图5中的这种按层次编号的编号顺序，完全二叉树的某个结点和满二叉树的同样编号的结点是处于同一个位置的。例如我们把图5想象成一个满二叉树，那么只要是完全二叉树有的序号，那么一定对应在满二叉树的相同位置。比如10号结点，满二叉树中10在5的左子树，完全二叉树中10也一定是5的左子树！

从这里我也可以得出一-些完全二叉树的特点:
(1)叶子结点只能出现在最下两层。
(2)最下层的叶子结点一定集中在左部连续位置。
(3)倒数二层，若有叶子结点，一定都在右部连续位置。
(4)如果结点度为1，则该结点只有左子树，即整个完全二叉树中不存在某一个结点只有右子树的情况。
(5)同样结点数的二叉树，完全二叉树的深度最小。

⭐3.二叉树的一些性质

?性质1：

在二叉树的第i层上至多有2^i-1个结点(i≥1)。
我们知道一个二叉树某一层结点最多的时候是满二叉树的情况，所以参考图4中的满二叉树，我们可以发现：
第一层是根结点，只有一个结点，所以2^1-1=2⁰=1。
第二层有两个，2^2-1=2¹ =2。
第三层有四个，2^3-1=2²=4。
第四层有八个，2^4-1=2³=8。
通过数据归纳法的论证，可以很容易得出在二叉树的第i层上至多有2^i-1 (i≥1)个结点。

?性质2：

深度为k的二叉树至多有2^k -1个结点(k≥1)。

注意这里一定要看清楚，是2^k减去1。深度为k意思就是有k层的二叉树。
如果有一层，至多1 = 21-1个结点。
如果有二层，至多1+2 = 3 = 2²-1个结点。
如果有三层，至多1+2+4 = 7 = 2³-1个结点。
如果有四层，至多1+2+4+8 = 15 = 2⁴-1个结点。
通过数据归纳法的论证，可以得出，如果有k层，此二叉树至多有2^k-1个结点。

?性质3：

对任何一棵二叉树T，如果其叶子结点数为n₀，度为2的结点数为n₂，则有n₀=n₂+1

一棵二叉树，除了叶子结点外，剩下的就是度为1或2的结点，我们设n₁为度是1的结点数。则树T结点总数
n=n₀+n₁+n₂。

?性质4：

具有n个结点的完全二叉树的深度为[ log₂n ] +1

注意，log₂n需要取整。

?性质5：

如果对一棵有n个结点的完全二叉树(其深度为[log₂n]+1)的结点按层序编号(从第1层到第[log₂n]+1 层，每层从左到右)，对任一结点i (1<i≤n)有：

1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2]（取整）。
2. 如果2i>n, 则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i。
3. 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

我们以图5来验证理解性质5：

1. 如果i=1，则1是根结点，没有双亲。如果i = 5，则5/2 = 2，可以发现2是其双亲结点。
2. 比如i = 2，则2i = 4 <10 = n，而2号结点的左孩子就是4；比如i = 6，2i = 12 > n，而6号结点没有左孩子。
3. 比如i = 3，则2i + 1 = 7 < n = 10，而3号结点的右孩子就是7；比如i = 5，2i + 1 = 11 > 10，而5号结点没有右孩子。

二叉树是树结构中最常用的树，在实际编程中，二叉树也是使用最频繁的树形结构。那么下一篇文章，我们将了解二叉树的存储结构和二叉树的遍历，并且编程实现二叉树的基本操作！