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

मान लीजिए कि हमारे पास एक दिया गया बाइनरी ट्री है; हमें दिए गए बाइनरी ट्री में सबसे बड़े परफेक्ट उप-वृक्ष का आकार ज्ञात करना है। जैसा कि हम जानते हैं कि पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जिसमें सभी आंतरिक नोड्स में दो बच्चे होते हैं और सभी पत्ते समान स्तर पर होते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट 3 होगा, और सबट्री है

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

• RetType नामक एक ब्लॉक को परिभाषित करें, इसमें isPerfect, ऊंचाई और rootTree होगा, वे सभी प्रारंभ में 0

  हैं

• get_prefect_subtree() नामक फ़ंक्शन को परिभाषित करें, यह रूट लेता है

• r_type :=एक नया RetType

• अगर रूट कोई नहीं के समान है, तो

  • r_type.isPerfect :=True

  • r_type.ऊंचाई :=0

  • r_type.rootTree :=null

  • वापसी r_type

• left_subtree :=get_prefect_subtree(root.left)

• right_subtree :=get_prefect_subtree(root.right)

• अगर लेफ्ट_सबट्री परफेक्ट है और राइट_सबट्री परफेक्ट है और लेफ्ट_सबट्री की ऊंचाई राइट_सबट्री की ऊंचाई के समान है, तो

  • r_type की ऊंचाई:=left_subtree की ऊंचाई + 1

  • सेट r_type एकदम सही है

  • r_type.rootTree :=root

  • वापसी r_type

• सेट r_type सही नहीं है

• r_type.height :=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,