Pythonで特定の二分木で最大の完全なサブツリーを見つける

二分木があるとしましょう。この二分木で最大の完全なサブツリーのサイズを見つける必要があります。私たちが知っているように、完全な二分木は、おそらく最終レベルなしですべてのレベルが完全に満たされ、最終レベルに可能な限りすべてのキーが残っている場合、二分木です。

したがって、入力が次のような場合

その場合、出力はサイズとして4になり、順序どおりの走査は10、45、60、70になります

これを解決するには、次の手順に従います-

• isComplete、isPerfectなどのいくつかのパラメーターを使用して戻り型を定義します。これらは最初はfalseで、次にsizeとrootTree、sizeは最初は0、rootTreeはnullです。
• ret_type：=returnType
• rootがnullの場合、
  • ret_type.isPerfect：=True
  • ret_type.isComplete：=True
  • 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：=True
  • ret_type.isPerfect：=right_tree.isPerfect
  • ret_type.size：=left_tree.size + right_tree.size + 1
  • ret_type.rootTree：=root
  • ret_typeを返す
• （left_tree.isCompleteがTrueで、right_tree.isPerfectがTrueで、左右のツリーの高さが同じである場合、
  • ret_type.isComplete：=True
  • ret_type.isPerfect：=False
  • ret_type.size：=left_tree.size + right_tree.size + 1
  • ret_type.rootTree：=root
  • ret_typeを返す
• ret_type.isPerfect：=False
• ret_type.isComplete：=False
• 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を返す

Python

理解を深めるために、次の実装を見てみましょう-

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,