पायथन में दिए गए पोस्टऑर्डर से एक बाइनरी सर्च ट्री का निर्माण करें

मान लीजिए कि हमारे पास बाइनरी सर्च ट्री का पोस्टऑर्डर ट्रैवर्सल अनुक्रम है। हमें इन अनुक्रमों से वृक्ष उत्पन्न करना है। तो, अगर पोस्टऑर्डर क्रम [9,15,7,20,3] है, तो पेड़ होगा -

एक ट्री बनाने के लिए हमें इनऑर्डर ट्रैवर्सल की भी आवश्यकता होती है, लेकिन बाइनरी सर्च ट्री के लिए, इनऑर्डर ट्रैवर्सल क्रमबद्ध रूप में होगा।

आइए चरणों को देखें -

• इनऑर्डर =पोस्टऑर्डर ट्रैवर्सल की क्रमबद्ध सूची।

• एक विधि को परिभाषित करें build_tree(), यह इनऑर्डर, पोस्टऑर्डर लेगा -

• अगर इनऑर्डर सूची खाली नहीं है -

  • रूट:=पोस्टऑर्डर के अंतिम मान के साथ एक ट्री नोड बनाएं, फिर उस तत्व को हटा दें

  • ind :=इनऑर्डर सूची में रूट डेटा की अनुक्रमणिका

  • जड़ का अधिकार :=build_tree(inorder in index ind to end, postorder)

  • रूट के बाईं ओर:=बिल्ड_ट्री (0 से इंडेक्स इंड -1 में, पोस्टऑर्डर)

• वापसी जड़

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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 Solution(object):
   def buildTree(self, inorder, postorder):
      if inorder:
         root = TreeNode(postorder.pop())
         ind = inorder.index(root.data)
         root.right = self.buildTree(inorder[ind+1:],postorder)
         root.left = self.buildTree(inorder[:ind],postorder)
         return root
ob1 = Solution()
postorder = [3,9,20,15,7]
inorder = list(sorted([3,9,20,15,7]))
print_tree(ob1.buildTree(inorder, postorder))

इनपुट

[9,3,15,20,7]
[9,15,7,20,3]

आउटपुट

[3,7,9,15,20]