algorithm - 什么是近完全二叉树？

Question

我在网上看过很多关于“堆”的定义，也看过CLRS中的定义。网上的大部分定义好像都说堆是完全二叉树；然而，CLRS 以下列句子开始堆章节:

The (binary) heap data structure is an array object that we can view as a nearly complete binary tree...

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

这使我想到了以下问题:是否可能有一个不是完整二叉树的堆？

Answer 1

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

• 完全二叉树:除最后一层外都被占满，最后一层的叶子级别出现在该级别的左侧。

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

• 完全二叉树:没有一个节点只有一个 child 的二叉树。有时这个术语被用来表示完美的二叉树，增加了困惑。

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

但是关于 Binary tree 的维基百科文章警告:

Some authors use the term complete to refer instead to a perfect binary tree [...] in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.

显然你所指的文字的作者属于这一类。