পাইথনে পোস্টঅর্ডার থেকে বাইনারি সার্চ ট্রি তৈরি করুন

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

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

चरण निम्नलिखित हैं:

• इनऑर्डर = पोस्टऑर्डर ट्रैवर्सल की सॉर्टेड सूची।
• build_tree() नामक एक मेथड परिभाषित करें, यह inorder, postorder लेगा:
  • यदि inorder सूची खाली नहीं है:
    • root := postorder के अंतिम मान के साथ एक ट्री नोड बनाएं, फिर उस तत्व को हटा दें
    • ind := inorder सूची में root डेटा का इंडेक्स
    • root का राइट := build_tree(inorder[ind+1:], postorder)
    • root का लेफ्ट := build_tree(inorder[:ind], postorder)
  • root लौटाएं

उदाहरण

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

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]