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

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

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

• एक विधि को परिभाषित करें 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()
print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))

इनपुट

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

आउटपुट

[9,3,15,20,7]