作者：解学武

树是一种非线性存储结构，一棵树由多个逻辑关系为“一对多”的结点构成，这些结点之间的关系可以用父子、兄弟、表兄弟等称谓描述。

如果你还不了解什么是树存储结构，请猛击《数据结构的树存储结构》了解。

理论上，一棵树上的各个结点可以有任意个孩子。但是，如果一棵树具备以下两个特征：

1. 本身是一棵有序树，即各个结点的孩子位置不能改变；
2. 树中各个结点的度（子树个数）不能超过 2，即只能是 0、1 或者 2。

同时具备这 2 个特征的树就称为「二叉树」。

例如下图画了两棵有序树，图 1a) 是二叉树，而图 1b) 不是，因为它的根结点的度为 3，不具备第 2 个特征。


如果一棵树是二叉树，那么它具有以下几个性质：

1. 树中第 i 层最多可以有 2^i-1 个结点。以图 1a) 为例，第 1 层最多只能有 1 个结点（2^1-1），也就是根结点；第 2 层最多有 2 个结点（2^2-1）；第 2 层最多有 4 个结点（2^3-1），以此类推。
2. 若二叉树的深度（高度）为 K，那么树中最多可以包含 2^K-1 个结点。图 1a) 这棵二叉树的深度为 3，所以它最多可以包含 2³-1 = 7 个结点。
3. 若二叉树中叶子结点的个数用 n₀ 表示，度为 2 的结点的个数用 n₂ 表示，那么有 n₀=n₂+1 等式成立。

这里重点解释一下第 3 条性质，等式 n₀=n₂+1 的推导过程是：

1) 二叉树中除了度为 0 的叶子结点和度为 2 的结点，剩下的全是度为 1 的结点，数量用 n₁表示，那么树中所有结点的个数 n = n₀+n₁+n₂。

2) 二叉树中结点的个数 n 还可以用所有结点的度来表示：
①：若树中所有结点度的和用 B 表示，那么有等式 n=B+1 成立。以图 1a) 为例，树中所有结点度的和为 B=2+2+1=5，因此树中包含的结点数量为 B+1=6。
②：一棵树所有结点度的和 B 可以用 n1 和 n2 表示，等式为 B=n₁+2*n₂。
将两个等式结合，可以得到等式 n =n₁+2*n₂+1。

3) 最终，将两种表示 n 的式子组成一个方程组，就可以轻松得出 n₀=n₂+1。

特殊的二叉树

二叉树还可以继续分类，衍生出满二叉树和完全二叉树。

1、满二叉树

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
如图 2 所示就是一棵满二叉树。

对于任意一棵满二叉树，除了满足普通二叉树的全部性质，还具备一些特有的性质，包括：

1. 满二叉树中第 i 层的节点数为 2^i-1 个；
2. 深度为 k 的满二叉树必有 2^k-1 个节点 ，叶子结点的个数也为 2^k-1；
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层；
4. 具有 n 个节点的满二叉树的深度为 log₂(n+1)。

2、完全二叉树

如果二叉树最后一层的叶子结点依次从左向右分布，且去除最后一层叶子结点后变成一棵满二叉树，这样的二叉树被称为完全二叉树。


如图 3a) 所示是一棵完全二叉树，图 3b) 由于最后一层的叶子节点没有依次从左向右分布，因此只是一棵普通的二叉树。

对于任意一棵完全二叉树，除了满足普通二叉树的全部性质，还具备一些特有的性质，比如包含 n 个结点的完全二叉树的深度为 ⌊log₂n⌋+1。

⌊log₂n⌋ 表示取小于 log₂n 的最大整数。例如，⌊log₂4⌋ = 2，而 ⌊log₂5⌋ 结果也是 2。

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，有以下几条结论成立：

1. 当 i>1 时，父亲结点为结点 ⌊i/2⌋ 。（i=1 表示的是根结点，无父亲结点）；
2. 如果 2*i>n（总结点的个数） ，则结点 i 肯定没有左孩子，并且该结点为叶子结点；反之，如果 2*i<n，那么结点 i 的左孩子是结点 2*i ；
3. 如果 2*i+1>n ，则结点 i 肯定没有右孩子；否则结点 i 的右孩子是结点 2*i+1 。

总结

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

本节主要介绍了什么是二叉树、满二叉树和完全二叉树，以及它们各自具有的性质。实际开发中，合理利用二叉树的性质可以快速操作二叉树中的结点，提高程序的执行效率。