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

pythonserver side programmingprogramming更新于 2025/10/17 5:32:17

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

因此，如果输入如下

则输出将为 true

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

定义一个函数 number_of_nodes() 。这将根植
如果 root 为空，则
- 返回 0
否则，
- 返回(1 + number_of_nodes(root.left) + number_of_nodes(root.right))
定义一个函数 has_heap_property() 。这将生根
如果 root.left 为 null 且 root.right 为 null，则
- 返回 True
如果 root.right 为 null，则
- 当 root.val >= root.left.val 时返回 true
否则，
- 如果 (root.val >= root.left.val 且 root.val >= root.right.val，则
  - 返回(has_heap_property(root.left) 和 has_heap_property(root.right))
- 否则，
  - 返回 False
定义一个函数is_complete_tree() 。这将采用 root、index、node_count
如果 root 为空，则
- 返回 True
如果 index >= node_count，则
- 返回 False
return(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) 且 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)