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

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

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

• मान लीजिए कि विधि को प्रीऑर्डर और इनऑर्डर सूचियों के साथ बिल्डट्री कहा जाता है
• रूट:=पोस्टऑर्डर से अंतिम नोड, और पोस्टऑर्डर से पहला नोड हटाएं
• root_index :=इनऑर्डर सूची से root.val की अनुक्रमणिका
• बाएं या रूट:=बिल्डट्री (रूट_इंडेक्स + 1 से अंत तक इनऑर्डर का सबसेट, पोस्टऑर्डर)
• दाएं या रूट:=बिल्डट्री (इंडेक्स 0 से रूट_इंडेक्स, पोस्टऑर्डर में इनऑर्डर का सबसेट)

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

उदाहरण

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   #print using inorder traversal
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Solution(object):
   def buildTree(self, preorder, inorder):
   if inorder:
      root = TreeNode(preorder.pop(0))
      root_index = inorder.index(root.data)
      root.left = self.buildTree(preorder,inorder[:root_index])
      root.right = self.buildTree(preorder,inorder[root_index+1:])
      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, 15, 7, 20, 3,