ค้นหาทรีย่อยที่สมบูรณ์ที่สุดใน Binary Tree ที่ระบุใน Python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาขนาดของ sub-tree ที่สมบูรณ์สูงสุดใน Binary Tree นี้ อย่างที่เราทราบกันดีว่าไบนารีทรีที่สมบูรณ์นั้นเป็นไบนารีทรี หากทุกระดับถูกเติมโดยสมบูรณ์โดยที่ระดับสุดท้ายอาจไม่มีคีย์ และระดับสุดท้ายมีคีย์ทั้งหมดเหลือไว้ให้มากที่สุด

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นเอาต์พุตจะเป็น 4 ตามขนาด และการส่งผ่านแบบไม่เรียงลำดับจะเป็น 10, 45, 60, 70

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดประเภทการส่งคืนด้วยพารามิเตอร์ไม่กี่อย่าง เช่น isComplete, isPerfect ซึ่งในตอนแรกจะเป็นเท็จ จากนั้นจึงกำหนดขนาดและรูททรี ขนาดเริ่มต้นคือ 0 และ rootTree เป็นค่าว่าง
• ret_type :=returnType
• ถ้ารูทเป็นโมฆะ
  • ret_type.isPerfect :=จริง
  • ret_type.isComplete :=จริง
  • ret_type.size :=0
  • ret_type.rootTree :=ไม่มี
  • ส่งคืน ret_type
• left_tree :=checkCompleteness(root.left)
• right_tree :=ตรวจสอบความสมบูรณ์ (root.right)
• ถ้า (left_tree.isPerfect เป็น True และ right_tree.isComplete เป็น True และความสูงของต้นไม้ซ้ายและขวาเท่ากัน ดังนั้น
  • ret_type.isComplete :=จริง
  • ret_type.isPerfect :=right_tree.isPerfect
  • ret_type.size :=left_tree.size + right_tree.size + 1
  • ret_type.rootTree :=รูท
  • ส่งคืน ret_type
• ถ้า (left_tree.isComplete เป็น True และ right_tree.isPerfect เป็น True และความสูงของต้นไม้ซ้ายและขวาเท่ากัน ดังนั้น
  • ret_type.isComplete :=จริง
  • ret_type.isPerfect :=เท็จ
  • ret_type.size :=left_tree.size + right_tree.size + 1
  • ret_type.rootTree :=รูท
  • ส่งคืน ret_type
• ret_type.isPerfect :=เท็จ
• ret_type.isComplete :=เท็จ
• ret_type.size :=สูงสุดของ left_tree.size, right_tree.size
• ถ้า left_tree.size> right_tree.size แล้ว
  • ret_type.rootTree :=left_tree.rootTree
• มิฉะนั้น
  • ret_type.rootTree :=right_tree.rootTree
• ส่งคืน ret_type

หลาม

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

import math
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class returnType :
   def __init__(self):
      self.isPerfect = None
      self.isComplete = None
      self.size = 0
      self.rootTree = None
def getHeight(size):
   return int(math.ceil(math.log(size + 1)/math.log(2)))
def checkCompleteness(root) :
   ret_type = returnType()
   if (root == None):
      ret_type.isPerfect = True
      ret_type.isComplete = True
      ret_type.size = 0
      ret_type.rootTree = None
      return ret_type
   left_tree = checkCompleteness(root.left)
   right_tree = checkCompleteness(root.right)
   if (left_tree.isPerfect == True and right_tree.isComplete == True and getHeight(left_tree.size) == getHeight(right_tree.size)) :
      ret_type.isComplete = True
      ret_type.isPerfect = right_tree.isPerfect
      ret_type.size = left_tree.size + right_tree.size + 1
      ret_type.rootTree = root
      return ret_type
   if (left_tree.isComplete == True and right_tree.isPerfect == True and getHeight(left_tree.size) == getHeight(right_tree.size) + 1):
      ret_type.isComplete = True
      ret_type.isPerfect = False
      ret_type.size = left_tree.size + right_tree.size + 1
      ret_type.rootTree = root
      return ret_type
      ret_type.isPerfect = False
      ret_type.isComplete = False
      ret_type.size =max(left_tree.size, right_tree.size)
      if(left_tree.size > right_tree.size ):
         ret_type.rootTree = left_tree.rootTree
      else:
         ret_type.rootTree = right_tree.rootTree
      return ret_type
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)
ans = checkCompleteness(root)
print( "Size:" , ans.size )
print("Inorder Traversal: ", end = '')
print_tree(ans.rootTree)

อินพุต

root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)

ผลลัพธ์:

Size: 4
Inorder Traversal: 10, 45, 60, 70,