Python 检查给定二叉树是否为堆

假设我们有一个二叉树；我们必须检查它是否为堆。堆具有以下属性：堆将是一个二叉树，该树应该是一个完全二叉树（因此，除了最后一层之外，所有层都应是满的）。该树的每个节点的值都应该大于或等于其子节点的值（最大堆）。

因此，如果输入类似于：

则输出将为 true

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数 `number_of_nodes()`。这将接收根节点。
  • 如果根节点为空，则
    • 返回 0
  • 否则，
    • 返回 (1 + number_of_nodes(root.left) + number_of_nodes(root.right))
  • 定义一个函数 `has_heap_property()`。这将接收根节点。
  • 如果 root.left 为空且 root.right 为空，则
    • 返回 True
  • 如果 root.right 为空，则
    • 当 root.val >= root.left.val 时返回 true
  • 否则，
    • 如果 (root.val >= root.left.val 且 root.val >= root.right.val)，则
      • 返回 (has_heap_property(root.left) and has_heap_property(root.right))
    • 否则，
      • 返回 False
  • 定义一个函数 `is_complete_tree()`。这将接收根节点，索引和节点计数。
  • 如果根节点为空，则
    • 返回 True
  • 如果 index >= node_count，则
    • 返回 False
  • 返回 (is_complete_tree(root.left, 2 * index + 1, node_count) and is_complete_tree(root.right, 2 * index + 2, node_count))
  • 在主方法中执行以下操作：
  • node_count := number_of_nodes()
  • 如果 is_complete_tree(root, 0, node_count) and has_heap_property(root) 不为零，则
    • 返回 True
  • 否则，
    • 返回 False

示例

让我们看看下面的实现以更好地理解：

 在线演示

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None
   def number_of_nodes(self, root):
      if root is None:
         return 0
      else:
         return (1 + self.number_of_nodes(root.left) + self.number_of_nodes(root.right))
   def has_heap_property(self, root):
      if (root.left is None and root.right is None):
         return True
      if root.right is None:
         return root.val >= root.left.val
      else:
         if (root.val >= root.left.val and
            root.val >= root.right.val):
            return (self.has_heap_property(root.left) and self.has_heap_property(root.right))
         else:
            return False
   def is_complete_tree(self, root,index, node_count):
      if root is None:
         return True
      if index >= node_count:
         return False
      return (self.is_complete_tree(root.left, 2 * index + 1, node_count) and self.is_complete_tree(root.right, 2 * index + 2, node_count))
   def is_heap(self):
      node_count = self.number_of_nodes(self)
      if (self.is_complete_tree(self, 0, node_count) and self.has_heap_property(self)):
         return True
      else:
         return False
root = TreeNode(99)
root.left = TreeNode(46)
root.right = TreeNode(39)
root.left.left = TreeNode(14)
root.left.right = TreeNode(5)
root.right.left = TreeNode(9)
root.right.right = TreeNode(33)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(12)
print(root.is_heap())

输入

root = TreeNode(99)
root.left = TreeNode(46)
root.right = TreeNode(39)
root.left.left = TreeNode(14)
root.left.right = TreeNode(5)
root.right.left = TreeNode(9)
root.right.right = TreeNode(33)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(12)

输出

True

更新于：2020-08-27

512 次浏览

开启您的 职业生涯

完成课程后获得认证

开始学习
广告