数据结构：满二叉树 (Full Binary Tree) 和 完全二叉树 (Complete Binary Tree)
目录
重要的术语澄清
完美二叉树 (Perfect Binary Tree)
完全二叉树 (Complete Binary Tree)
大比拼 (Comparison)
相互关系的第一性推导
我们来深入探讨两种在算法中非常重要的、具有特定“形状”的二叉树：满二叉树 (Full Binary Tree) 和 完全二叉树 (Complete Binary Tree)。
最关键的是，我们会将它们与之前学过的严格二叉树 (Strict Binary Tree) 进行详细的比较。
数据结构：严格二叉树 (Strict Binary Tree)-CSDN博客
这三者之间的区别和联系是常考点，也是一个非常容易混淆的地方，所以这次的第一性推导会特别注重辨析。
重要的术语澄清
在开始之前，我必须先解决一个长期困扰学习者的问题：术语混乱。
-
Strict Binary Tree (严格二叉树): 我们已经学过，定义非常清晰——每个节点要么有0个孩子，要么有2个孩子。
-
Full Binary Tree: 这是最混乱的术语。
-
在很多国际经典教材（如《算法导论》）和学术界中，"Full Binary Tree" 就是我们学的 "Strict Binary Tree"。
-
但是，在中国国内的很多教材中，“满二叉树” 指的是一种结构最完美的树，即所有叶子都在同一层。为了避免这种语义混淆，我们把这种最完美的树称为 完美二叉树 (Perfect Binary Tree)。
-
-
Complete Binary Tree (完全二叉树): 这个术语的定义是统一的，没有争议。
为了本次学习的清晰性，我们将采用以下定义:
-
严格二叉树 (Strict Binary Tree): 度为0或2。
-
完美二叉树 (Perfect Binary Tree): 国内教材中的“满二叉树”，是一种极致形态。
-
完全二叉树 (Complete Binary Tree): 为数组表示法而生的结构。
完美二叉树 (Perfect Binary Tree)
让我们从一个问题开始——一棵二叉树最“完美”、最“饱满”、最“对称”的形态应该是什么样的？
推导1 ——饱满：要想“饱满”，内部就不应该有任何浪费的空间。
任何一个非叶子节点，如果只挂了一个孩子，那它的另一个孩子位就空着，这不“饱满”。
所以，所有非叶子节点都必须有两个孩子。（这恰好是严格二叉树的定义）。
推导2 ——对称： 要想“对称”，树的末端应该是整齐划一的。
如果有些叶子在第3层，有些在第4层，那这棵树看起来就像参差不齐的灌木，不够“完美”。
所以，所有的叶子节点必须在同一层。
h = 2 (高度 2)●/ \● ●/ \ / \● ● ● ●
将这两个推论合二为一，就得到了完美二叉树 (Perfect Binary Tree) 的定义：
一棵深度为 k 且有 2^(k + 1) − 1 个节点的二叉树。用更直观的语言描述就是：
-
它是一棵严格二叉树。
-
并且，它所有的叶子节点都在最下面一层。
这棵树的形状像一个完美的等腰三角形，没有任何空缺。
性质:
-
节点数与高度的关系是固定的：对于高度为
h的完美二叉树，其节点数n永远是它能达到的最大值，不多不少，即 n = 2^(h + 1) − 1。 -
它是严格二叉树的一种非常特殊的特例。
完全二叉树 (Complete Binary Tree)
完美二叉树的要求太苛刻了。如果我有6个节点，就无法构成一棵完美二叉树（高度为1的完美树有3个节点，高度为2的有7个）。
那么，在节点数不“完美”的情况下，如何让树的形态尽可能地紧凑、不浪费空间呢？
推导1 ——填充顺序： 要想紧凑，我们应该从上到下，一层一层地去填充节点。不能第2层还没满，就去放第3层的节点。
所以，树的所有层，除了最后一层，都必须是满的（即构成一个完美二叉树）。
推导2 ——最后一层的排列： 对于最后一层，节点可能没有填满。那这些节点应该怎么放？是随便放，还是靠右放，还是靠左放？
为了“紧凑”，最自然的方式就是从左到右依次排列，中间不能有空隙。
满二叉树 (高度 2):●/ \● ●/ \ / \● ● ● ●完全二叉树（去掉最右叶子）:●/ \● ●/ \ / ● ● ●
将这两个推论合二为一，就得到了完全二叉树 (Complete Binary Tree) 的定义：
一棵二叉树，如果它除了最底层之外的其他各层都被完全填满，并且最底层的所有节点都连续地集中在左边，那么它就是一棵完全二叉树。
这个“从上到下，从左到右，连续排列”的特性，使其与数组表示法完美契合！
数据结构：二叉树的表示方式（Representation of Binary Trees）-CSDN博客
当你按层序遍历一个完全二叉树时，得到的节点序列可以不多不少、不留一个空位地（没有-1作为占位符）存入一个数组中。
完全二叉树这个概念，可以说就是为了高效的数组表示法而生的。 这是理解它的关键。
大比拼 (Comparison)
现在我们把三个概念放在一起，从不同维度进行比较。
| 对比维度 | 严格二叉树 (Strict) | 完美二叉树 (Perfect) | 完全二叉树 (Complete) |
|---|---|---|---|
| 一句话定义 | 节点度数要么是0，要么是2 | 节点全满，叶子在同一层 | 节点按层序连续排列 |
| 允许的节点度 | 只有 0 和 2 | 只有 0 和 2 | 可以是 0, 1, 2<br>(最多只允许有一个度为1的节点) |
| 形状要求 | 无特定形状要求，可高可矮 | 必须是完美的金字塔形 | 必须是“左对齐”的紧凑形状 |
| 和别人的关系 | 是一个比较宽泛的分类 | 是严格二叉树的特例<br>是完全二叉树的特例 | 不一定是严格二叉树<br>(当节点总数为偶数时，必有1个度为1的节点) |
| 数组表示法 | 如果很“瘦”，会浪费巨大空间 | 空间利用率100%，没有浪费 | 空间利用率100%，完美适配 |
相互关系的第一性推导
我们可以把这些树的集合想象成几个圈：
1. 完美二叉树是标准最严苛的。它既要求所有内部节点度为2（满足严格定义），又要求节点是连续的（满足完全定义）。
所以，完美二叉树的圈是最小的，它同时位于严格树和完全树两个圈的交集之内。
-
完美 => 严格(成立) -
完美 => 完全(成立)
完美二叉树： ●/ \● ●/ \ / \● ● ● ●/ \ / \ / \ / \● ● ● ● ● ● ● ●
2. 严格二叉树只对节点的“度”有要求。它不关心节点是不是“左对齐”。你可以构造一棵严格二叉树，它中间有空位，因此它不是完全二叉树。
-
严格 => 完全(不成立)
严格二叉树：●/ \● ●/ \● ●/ \ / \● ● ● ●
3. 完全二叉树只对节点的“位置”有要求。它不关心节点的“度”。当节点总数是偶数时，必然会产生一个只有一个左孩子的节点，它的度是1，这就不满足严格二叉树的定义。
-
完全 => 严格(不成立)
完全二叉树：●/ \● ●/ \ / \● ● ● ●/ \ / ● ● ●
结论:
-
完美二叉树 是最特殊、最规整的，它同时是一棵严格二叉树和一棵完全二叉树。
-
严格二叉树 和 完全二叉树 是从两个不同维度（“度” vs “位置”）对树进行的约束，它们有交集（交集就是完美二叉树），但谁也不是谁的子集。
理解了这些从基本原则出发的定义和它们之间的逻辑关系，你就再也不会把这几个概念搞混了。