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

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

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

• मान लीजिए कि विधि को प्रीऑर्डर और इनऑर्डर सूचियों के साथ बिल्डट्री कहा जाता है
• रूट:=प्रीऑर्डर से पहला नोड, और प्रीऑर्डर से पहला नोड हटाएं
• root_index :=इनऑर्डर सूची से root.val की अनुक्रमणिका
• बाएं या रूट:=बिल्डट्री (प्रीऑर्डर, इनऑर्डर का सबसेट 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):
   #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([3,9,20,15,7], [9,3,15,20,7]))

इनपुट

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

आउटपुट

9, 3, 15, 20, 7,