ค้นหา Perfect Subtree ที่ใหญ่ที่สุดใน Binary Tree ใน Python

สมมติว่าเรามีต้นไม้ไบนารีที่กำหนด เราต้องหาขนาดของทรีย่อย Perfect ที่ใหญ่ที่สุดใน Binary Tree ที่ให้มา อย่างที่เราทราบดีว่าไบนารีทรีที่สมบูรณ์แบบคือไบนารีทรีที่โหนดภายในทั้งหมดมีลูกสองคนและใบไม้ทั้งหมดอยู่ในระดับเดียวกัน

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

จากนั้นผลลัพธ์จะเป็น 3 และทรีย่อยคือ

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

• กำหนดหนึ่งบล็อกที่เรียกว่า RetType ซึ่งจะถือ isPerfect ความสูงและ rootTree ทั้งหมดเป็น 0

• กำหนดฟังก์ชันที่เรียกว่า get_prefect_subtree() ซึ่งจะทำการรูท

• r_type :=RetType ใหม่

• หากรูทเหมือนกับไม่มีแล้ว

  • r_type.isPerfect :=จริง

  • r_type.height :=0

  • r_type.rootTree :=null

  • ส่งคืน r_type

• left_subtree :=get_prefect_subtree(root.left)

• right_subtree :=get_prefect_subtree(root.right)

• ถ้า left_subtree สมบูรณ์แบบและ right_subtree สมบูรณ์แบบและความสูงของ left_subtree เท่ากับความสูงของ right_subtree แล้ว

  • ความสูงของ r_type :=ความสูงของ left_subtree + 1

  • set r_type เป๊ะมาก

  • r_type.rootTree :=รูท

  • ส่งคืน r_type

• set r_type ไม่สมบูรณ์แบบ

• r_type.height :=ความสูงของ left_subtree สูงสุด ความสูงของ right_subtree

• ถ้าความสูงของ left_subtree> ความสูงของ right_subtree แล้ว

  • r_type.rootTree :=left_subtree.rootTree

• มิฉะนั้น

  • r_type.rootTree :=right_subtree.rootTree

• ส่งคืน r_type

ตัวอย่าง

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class RetType:
   def __init__(self):
      isPerfect = 0
      height = 0
      rootTree = 0
def get_prefect_subtree(root):
   r_type = RetType()
   if (root == None) :
      r_type.isPerfect = True
      r_type.height = 0
      r_type.rootTree = None
      return r_type
   left_subtree = get_prefect_subtree(root.left)
   right_subtree = get_prefect_subtree(root.right)
   if (left_subtree.isPerfect and right_subtree.isPerfect and left_subtree.height == right_subtree.height) :
      r_type.height = left_subtree.height + 1
      r_type.isPerfect = True
      r_type.rootTree = root
      return r_type
   r_type.isPerfect = False
   r_type.height = max(left_subtree.height, right_subtree.height)
   if (left_subtree.height > right_subtree.height ):
      r_type.rootTree = left_subtree.rootTree
   else :
      r_type.rootTree = right_subtree.rootTree
   return r_type

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)

res = get_prefect_subtree(root)
h = res.height

print ("Size: " , pow(2, h) - 1)
print ("Tree: ", end = " ")
print_tree(res.rootTree)

อินพุต

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)

ผลลัพธ์

Size: 3
Tree: 5, 3, 6,