什么是近完全二叉树？

Question

我在网上读过很多“堆”的定义，也读过CLRS中的定义。网上大部分的定义似乎都说堆是完全二叉树；但是，CLRS 使用以下句子开始堆章节：

（二叉）堆数据结构是一个数组对象，我们可以将其视为几乎完整的二叉树......

我不知道为什么，但 CLRS 称堆“几乎完整”，而我读过的几乎所有其他“堆”定义都称堆“完整”，这确实让我感到困扰。

这引出了以下问题：是否有可能有一个不是完整二叉树的堆？

Answer 1

您对“几乎完成”这个表达感到困扰是完全正确的。根据最常见的术语，堆是一个完全二叉树：

• 完全二叉树：除了最后一层之外的所有层都被完全占据，最后一层的叶子出现在该层的左侧。

• 完美二叉树：完全二叉树，其中最后一层也被完全占据。

• 完整二叉树：一种二叉树，其中没有一个节点只有一个子节点。有时该术语用于表示完美二叉树，从而增加了混乱。

完美二叉树也是完全二叉树，但完全二叉树可能是也可能不是满二叉树。

但维基百科关于二叉树的文章警告说：

一些作者使用术语“完整”来代替完美二叉树[...]，在这种情况下，他们将这种类型的树（最后一层可能未填充）称为几乎完全二叉树或几乎完全二叉树。

显然，您所引用的文本的作者就属于这一类。