什么是近乎完整的二叉树？ [英] What are nearly complete binary trees?

问题描述

我已经在线阅读了许多有关堆的定义，并且还阅读了CLRS中的定义。在线上的大多数定义似乎都说堆是完整的二叉树。但是，CLRS使用以下语句开始堆章节：

I have read many definitions of a "heap" online, and I have also read the definition in CLRS. Most of the definitions online seem to say that heaps are complete binary trees; however, CLRS starts the heap chapter with the following sentence:

（二进制）堆数据结构是一个数组对象，我们可以查看
是几乎完整的二叉树...

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

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

I'm not sure why, but it really bothers me that CLRS calls heaps "nearly complete," whereas almost every other definition of "heap" I've read calls heaps "complete."

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

This leads me to the following question: Is it possible to have a heap that isn't a complete binary tree?

推荐答案

您绝对对表达式几乎完成感到困扰。根据最常用的术语，堆是完整的二叉树：

You are absolutely right to be bothered by the expression "nearly complete". A heap is a complete binary tree, according to the most common terminology:

• 完整的二叉树：除最后一个级别外的所有其他对象都已被全部占用，最后一个
  级别中的叶子出现在该级别的左侧。

• complete binary tree: all except the last level are fully occupied, and the leaves in the last level appear at the left side of that level.

完美的二叉树：完整的二叉树，其中最后一层也被完全占用。

perfect binary tree: a complete binary tree where also the last level is completely occupied.

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

full binary tree: a binary tree where none of the nodes has just one child. Sometimes this term is used to denote a perfect binary tree, adding to the confusion.

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

A perfect binary tree is also a complete and a full binary tree, but a complete binary tree may or may not be a full binary tree.

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

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

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.

显然，您所引用的文本的作者属于该类别。

So apparently the author of the text you refer to, falls into that category.

这篇关于什么是近乎完整的二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！