完全二叉树、近完全二叉树和完美二叉树的区别是什么？

首先明确：三者的定义都基于“除最底层外的上层节点全部填满”的前提，差异仅集中在最底层节点的填充规则、约束严格程度上。

1. 完美二叉树（Perfect Binary Tree） #

• 是三类树中约束最严格的类型，所有层级的节点都被完全填满，不存在任何空缺
• 高度为h的完美二叉树，总节点数固定为2^(h+1) - 1，所有叶子节点都处于同一最深层
• 天然满足另外两类二叉树的所有判定条件，属于另外两类的特例

2. 完全二叉树（Complete Binary Tree，国际通用定义） #

• 仅允许最底层存在节点空缺，其余所有层的节点都被完全填满
• 最底层的节点必须严格按照从左到右的顺序填充，空缺只能出现在最底层的最右侧，不允许出现“左侧位置空缺、右侧位置有节点”的情况
• 高度为h的完全二叉树，总节点数范围是2^h ~ 2^(h+1) - 1
• 常用的堆数据结构，就是基于完全二叉树的规则实现的

3. 近完全二叉树（Almost Complete Binary Tree） #

• 仅要求除最底层外的上层节点全部填满，对最底层节点的排列顺序没有强制靠左的要求，只要节点的父节点存在即可
• 与完全二叉树的核心差异：完全二叉树不允许最底层节点中间有空隙，近完全二叉树允许
• 网络上概念混淆的核心原因：部分中文资料会直接将近完全二叉树翻译为“完全二叉树”，和国际通用的完全二叉树定义冲突

• 约束严格程度排序：完美二叉树 > 完全二叉树 > 近完全二叉树
• 完美二叉树是完全二叉树的特例，完全二叉树是近完全二叉树的特例
• 三类树中仅近完全二叉树允许最底层节点不按靠左顺序排列
• 仅完美二叉树的总节点数是固定值，另外两类的总节点数都有浮动范围

内容的提问来源于stack exchange，提问作者Ruhan Saini