Tìm Cây con hoàn hảo lớn nhất trong Cây nhị phân nhất định bằng Python

Giả sử chúng ta có một Cây nhị phân đã cho; chúng ta phải tìm kích thước của cây con Perfect lớn nhất trong Cây nhị phân đã cho đó. Như chúng ta đã biết cây nhị phân hoàn hảo là cây nhị phân trong đó tất cả các nút bên trong đều có hai nút con và tất cả các lá ở cùng mức.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 3 và cây con là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một khối được gọi là RetType, khối này sẽ chứa isPerfect, height và rootTree, ban đầu chúng đều là 0

• Xác định một hàm được gọi là get_prefect_subtree (), hàm này bắt nguồn từ gốc

• r_type:=a RetType mới

• nếu gốc giống như Không thì

  • r_type.isPerfect:=True

  • r_type.height:=0

  • r_type.rootTree:=null

  • trả về r_type

• left_subtree:=get_prefect_subtree (root.left)

• right_subtree:=get_prefect_subtree (root.right)

• nếu left_subtree là hoàn hảo và right_subtree là hoàn hảo và chiều cao của left_subtree bằng với chiều cao của right_subtree thì

  • height of r_type:=height of left_subtree + 1

  • set r_type is perfect

  • r_type.rootTree:=root

  • trả về r_type

• set r_type không hoàn hảo

• r_type.height:=chiều cao tối đa của left_subtree, chiều cao của right_subtree

• nếu chiều cao của left_subtree> chiều cao của right_subtree thì

  • r_type.rootTree:=left_subtree.rootTree

• nếu không,

  • r_type.rootTree:=right_subtree.rootTree

• trả về r_type

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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)

Đầu vào

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)

Đầu ra

Size: 3
Tree: 5, 3, 6,