Python의 주어진 이진 트리에서 가장 큰 완전한 하위 트리 찾기

이진 트리가 있다고 가정합니다. 이 이진 트리에서 최대 전체 하위 트리의 크기를 찾아야 합니다. 우리가 알고 있듯이 모든 레벨이 최종 레벨 없이 완전히 채워지고 최종 레벨에 가능한 모든 키가 남아 있는 경우 완전한 이진 트리는 이진 트리입니다.

따라서 입력이 다음과 같으면

그러면 출력은 크기가 4가 되고 중위 순회는 10, 45, 60, 70,

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• isComplete, isPerfect와 같은 매개변수가 거의 없는 반환 유형을 정의합니다. 초기에는 false이고, 그 다음에는 size 및 rootTree, size는 초기에 0이고 rootTree는 null입니다.
• ret_type :=returnType
• 루트가 null이면
  • ret_type.isPerfect :=참
  • ret_type.isComplete :=참
  • ret_type.size :=0
  • ret_type.rootTree :=없음
  • ret_type 반환
• left_tree :=checkCompleteness(root.left)
• right_tree :=checkCompleteness(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,