पायथन में दिए गए बाइनरी ट्री में सबसे बड़ा पूर्ण उपट्री खोजें

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें इस बाइनरी ट्री में अधिकतम पूर्ण उप-ट्री का आकार ढूंढना है। जैसा कि हम जानते हैं, एक पूर्ण बाइनरी ट्री वह बाइनरी ट्री है जहां सभी स्तर पूरी तरह भरे होते हैं, संभवतः अंतिम स्तर को छोड़कर, और अंतिम स्तर में सभी कुंजियां यथासंभव बाईं ओर होती हैं।

इसलिए, यदि इनपुट इस तरह है:

तो आउटपुट आकार 4 होगा और इनऑर्डर ट्रैवर्सल होगा: 10, 45, 60, 70।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• कुछ पैरामीटर्स के साथ रिटर्न टाइप परिभाषित करें जैसे isComplete, isPerfect (प्रारंभ में false), size (प्रारंभ में 0), और rootTree (प्रारंभ में null)।
• ret_type := returnType
• यदि root null है, तो:
  • ret_type.isPerfect := True
  • ret_type.isComplete := True
  • ret_type.size := 0
  • ret_type.rootTree := None
  • 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 := max(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 is 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,