什么是近似完全二叉树？

Question

我曾经在网上阅读了很多“堆”的定义，并且也看过CLRS中的定义。大部分在线定义似乎都说堆是完全二叉树;然而，CLRS用以下句子开始堆章节:

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

我不确定为什么，但是CLRS称堆为“几乎完整的”，而我读过的几乎所有其他“堆”的定义都称堆为“完整的”。

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

- oompa

---

看起来他们在这里定义了一个“完全二叉树”，这通常被定义为“满二叉树”。 - Willem Van Onsem

这正是我所想的，但我只是想确认一下。谢谢！@WillemVanOnsem - oompa

当“完整”指的是左子树必须在右子树之前完成时，是的，堆是完全二叉树。 - User_67128

Answer 1

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

完全二叉树：除了最后一层之外，所有层都完全占满，而最后一层的叶节点出现在该层的左侧。

完美二叉树：一棵完全二叉树，同时最后一层也完全占满。

满二叉树：一棵二叉树中没有任何节点只有一个子节点。有时候这个术语也用来表示完美二叉树，增加了混淆。

完美二叉树既是完全二叉树又是满二叉树，但完全二叉树可以是满二叉树，也可以不是满二叉树。

但是二叉树的维基百科文章发出警告：

有些作者使用术语“完全”来指代一个“完美”的二叉树[...] 在这种情况下，他们将具有可能未填满最后一层的这种树称为“几乎完全的二叉树”。

所以显然你所提到的文字的作者属于这个类别。

- trincot

Answer 2

“complete”是什么意思？人们有不同的看法。在堆的上下文中，“complete”二叉树应该意味着树的最后一层具有最大数量的节点。

任何没有其最后一层拥有最大叶子节点的堆都不是“complete”，或者是“nearly complete”。

例如，一个具有7个元素的堆将是“complete”二叉树。但是，具有4、5或6个元素的堆将无法完全填充其最后一层，即为“nearly complete”。

深度为三的“nearly complete”二叉树的堆（假设根节点的深度为1）如下所示：

- Shridhar R Kulkarni

---

一棵完全二叉树的定义并不是这样的。正如维基百科所述：“在一棵完全二叉树中，除了最后一层可能不完全填充外，每一层都完全填充，并且最后一层中的所有节点尽可能地靠左。”因此，最后一层本身并没有最大数量的叶子节点。参考资料：https://en.wikipedia.org/wiki/Binary_tree - Willem Van Onsem

是的，同意。在“完成”方面进行了更详细的阐述后进行了编辑。 - Shridhar R Kulkarni

它不符合维基百科的定义。 - trincot