什么时候（最大）堆可以是 BST？

Question

干杯，假设我们有一个不允许重复元素的 MAX 堆。这个堆有可能是 BST 吗？选择下面的正确答案：

1. 堆永远不可能是 BST
2. 堆始终是 BST
3. 如果堆中只有一个节点（根），则堆可以是 BST
4. 堆可以是 BST 当且仅当它最多有 2 个节点时

哪一个是合适的答案？我会选择（3）和（4），以及我对所有答案的解释。谢谢！

Answer 1

开始：

（最大）堆是一个完全二叉树，其中每个节点的值都大于或等于其子节点的值。

A BST 是一棵二叉树，其中每个节点最多有 2 个子节点，并且每个节点的值都大于其左子树的所有值，并小于其右子树的所有值。

1. 我想到的堆只有一个值，例如8. 由于它没有子节点，因此这棵树仅由其根组成。这棵树是完整的，根的值大于其子树的值，因此它是一个堆。这棵树也是一个没有孩子的 BST。所以有一个堆也是一个 BST。

2. 这当然是错误的。设最大堆为：

当然，这是一个最大堆，但不是 BST，因为 6 放置在 8 的右侧。

3. 我认为这是正确的，正如我在（1）中也解释过的那样

4. 最多两个节点意味着我们可以有 0、1 或 2 个节点。

如果我们有 0 个节点，则它成立。

如果我们有 1 个节点，它也成立，我们证明了这一点。

如果我们有 2 个节点，它也成立。让最大堆有 2 个节点。要使其成为最大堆，它必须是完整的树，因此根据定义，第二个节点应放置在第一个节点（根）的左侧。根据最大堆的定义，第二个节点还包含小于第一个节点（根）的值。这也是具有 2 个节点的 BST 树。所以这是正确的。

（如有错误请指出，谢谢！）

Answer 2

这很棘手！让我们一一深入研究所有选项。

从您问题的选项来看：

堆永远不可能是 BST

错了。 因为具有一两个元素的堆也可以是有效的 BST。 （参见第三个选项的示例）

堆始终是 BST

错了。从你的例子中可以清楚地看出，堆有时无法保存 BST 的属性，特别是 Max-Heap。

如果堆中只有一个节点（根），则堆可以是 BST

错了。因为一棵有两个孩子的树也可以拥有 BST 的财产。

示例-

              3
               \ 
                5 

上面的节点结构是BST，也是一个Min-Heap。

堆可以是 BST 当且仅当它最多有 2 个节点时

你猜怎么着！也错了！因为单个节点可以是有效的 BST 以及最大/最小堆。

Answer 3

我认为这个问题最合适的答案是选项（3）。

堆树要成为二叉搜索树（BST），主要必须满足两个条件，它们是：

Condition 1

：每个节点最多有两个子节点（每个节点的最大度数等于 2）。

Condition 2

：左子树为空或具有较小的值。同样，右子树要么为空，要么具有更大的值。

让我们看看为什么其他选项不正确以及为什么选项（3）是最合适的。

Option (1): A heap can never be a BST

：
这是错误的，因为在某些情况下，堆树可以变成 BST。当堆树满足以上两个条件时，它就成为二叉搜索树。

Option (2): A heap is always a BST

：
这也是错误的，因为不满足上述两个条件中任何一个的堆树都不能是 BST。

Option (4): A heap can be BST if and only if it has up to 2 nodes

：
此选项不是最合适的选择，因为如果子节点是根节点的右子树，则具有两个节点的堆树仍然违反

condition 2

。

Option (3): A heap can be a BST if there is only one node inside it (root)

：
这是最合适的答案，因为它遵循上述两个条件。如果只有一个节点，则满足根节点

condition 1

和

condition 2

，因为没有子节点。