时间戳

首页 > 解决方案 > （最大）堆什么时候可以成为 BST？

binary-tree - （最大）堆什么时候可以成为 BST？

问题描述

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

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

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

标签： binary-treebinary-search-treeheap

解决方案

开始：

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

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

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

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

最大堆但不是 bst

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

  1. 我认为这是正确的，正如我在 (1) 中所解释的那样

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

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

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

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

（如有不妥请指出。谢谢！）

推荐阅读