还分不清楚一些二叉树种类和概念？

前言

刚接触二叉树的学习的时候，相信很多人可能会被二叉树各种各样的叫法和概念给绕晕了，今天就来科普一下关于二叉树我们需要知道的一些树的种类，以及它的特点。

比较常见的一些树名称的种类如下，你能够分清他们的区别吗？

（1）完全二叉树

（2）均衡二叉树

（3）有序二叉树

（4）满二叉树

（5）完美二叉树

如果还分不清楚，也不要紧，下面我们就来学习一下。

二叉树（Binary Tree）

二叉树是树类应用最广泛的一种数据结构，顾名思义，二叉树的每个节点最多只能包含两个孩子节点，一个节点可以包含0个，1个，2个孩子，如果是两个孩子，也就是通常我们说的左孩子和右孩子，图示如下：

有的朋友可能会思考，是否有三叉树，四叉树，N叉树呢？答案是肯定的，但树的分叉越多，内部结构就越复杂，理解起来就比较困难，这也是为什么二叉树如此流行的原因。

满二叉树（Full Binary tree）

满二叉树是二叉树里面一种分类，它的特点是每个节点的孩子节点要么没有，要么就是两个，不允许出现单个孩子的情况，图示如下：

完全二叉树（Complete Binary Tree）

完全二叉树是二叉树里面另外一个分类，它的特点是每个节点的孩子节点的数量可以是0， 1， 2 个，除此之外它要求每层节点添加，必须是从左到右，不允许跳着添加，图示如下：

上面的4个图示都是完全二叉树，下面我们在看几个反例：

注意上面这5张图都是完全二叉树，图1里面0节点还没有孩子，记住完全二叉树每层的添加节点必须是从左到右的，左边的节点还没有孩子，就添加右边的就违背了其定义，图2里面一样问题，3,7,10的插入都不是正确的顺序，图3,4,5的问题都是一样的，最下面的一层必须是从左到右的顺序添加。

二叉搜索树 （Ordered Binary Tree ）

也称二叉排序树，这个是我们接触的最多的一种结构，它要求节点的左子树小于该节点本身，右子树大于该节点，每个节点都符合这样的规则，对二叉搜索树进行中序遍历就得得到一个有序的序列，如下图：

二叉排序树的问题在于，如果树本身不是均衡的会导致树退化成链表，这个时候所有操作的效率都是O（N），效率大大降低，如下：

再看下满二叉树，完全二叉树，和普通二叉树的图示：

均衡二叉树 （Balanced Binary Tree:）

严格均衡二叉树指的是一个节点的左右子树的高度差值不能大于1，均衡二叉树一般都是在二叉搜索树的基础之上添加自动维持平衡的性质，这种树的插入，搜索，删除的综合效率比较高为O（logN），比如前面介绍的AVL树(严格平衡的二叉树)和红黑树（非严格平衡的二叉树）。

均衡和倾斜的二叉树如下图示：

完美二叉树 （Perfect binary Tree）

完美二叉树是理想中的一种二叉树，这种树的特点就是非常完美，每个节点都有两个孩子节点，并且都层都被完全填空，完美二叉树的叶子节点的高度都是一样，如下图示：

总结

本文主要介绍了二叉树相关的各种种类和特点，在这里我们还需要记住几个重要的知识，首先满二叉树不是均衡树，而完全二叉树则是均衡树，但均衡树却又不一定是完全二叉树，这一点从其性质上就能够得到。此外满二叉树和完全二叉树没有直接的关系，没有谁是谁这一说法。完全二叉树是一种非常高效和紧凑的树结构，堆这种数据结构就是基于完全二叉树实现的，堆的逻辑结构就是完全二叉树，其物理结构常用数组存储，常见的场景就是海量数据求Top N的问题，此外Java里面的优先级队列也是基于堆这种结构实现的，感兴趣的朋友可以自己去了解下。最后我们应该知道均衡的树的性能要比不均衡的树的性能要高很多，为了保持均衡性一般会有特定的规则来约束树，而解决均衡的手段通常是旋转和变色。除了二叉树，还有多叉均衡树，比如2-3树，B树，B+树等，多叉树的实现更加复杂，但是其树的高度比较低，所以拥有较高的查找性能，常用在数据库索引和文件系统。