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 次瀏覽

開啟您的 職業生涯

完成課程後獲得認證

開始學習
廣告