史上最全的二叉树：

前言

刚开始接触二叉树的研究时，相信很多人可能会对二叉树的各种名称和概念感到困惑。 今天我们就来科普一下二叉树我们需要了解的一些树的类型，以及它们的特点。

一些更常见的树名称类型如下。 你能说出它们之间的区别吗？

(1)完全二叉树

(2)平衡二叉树

(3)有序二叉树

(4)满二叉树

(5)完美二叉树

如果你还是分不清，没关系，下面我们就来了解一下。

二叉树

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

有的朋友可能会想，有三叉树、四叉树、N叉树吗？ 答案是肯定的，但是树的分支越多，内部结构就越复杂，也就越难理解，这也是二叉树如此流行的原因。

满二叉树

满二叉树是二叉树的一种分类。 其特点是每个节点要么没有子节点，要么有两个子节点。 不允许有独生子女。 示意图如下：

完全二叉树

完全二叉树是二叉树的另一类。 它的特点是每个节点的子节点数量可以是0、1、2。另外，它要求每一级添加节点，必须是从左到右，是不允许的。 跳转添加，如下图：

上面四张图都是完全二叉树。 下面我们看几个反例：

注意，上面五张图都是完全二叉树。 在图 1 中，节点 0 没有子节点。 请记住，在完全二叉树的每一层添加节点必须从左到右。 左边的节点还没有子节点，所以添加右边的节点是违反规则的。 定义与图2相同。3、7、10的插入顺序不正确。 图3、图4、图5中的问题都是相同的。 底层必须按照从左到右的顺序添加。 。

有序二叉树

也称为二叉排序树，这是我们接触最多的结构。 它要求节点的左子树小于节点本身，右子树大于节点。 每个节点都遵守这样的规则。 对于二分查找按顺序遍历树时，必须得到一个有序序列，如下图：

二叉排序树的问题在于，如果树本身不平衡，就会导致树退化为链表。 此时所有操作的效率都是O(N)，效率大大降低，如下：

我们看一下满二叉树、完全二叉树、普通二叉树的图：

平衡二叉树：

严格平衡二叉树是指一个节点的左右子树的高度差不能大于1。平衡二叉树一般在二叉搜索树的基础上增加了自动保持平衡的性质。 这棵树的插入、查找、删除整体效率都比较高，在O(logN)，比如前面介绍的AVL树（严格平衡二叉树）和红黑树（非严格平衡二叉树）。

平衡二叉树和倾斜二叉树如下所示：

完美二叉树

完美二叉树是理想二叉树。 这棵树的特点就是非常完美。 每个节点有两个子节点，并且所有级别都被完全填充。完美二叉树的叶子节点的高度都是相同的，如下所示。 展示：

总结

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