पायथन में स्टैक का उपयोग करके दिए गए पोस्टऑर्डर ट्रैवर्सल से एक बीएसटी का निर्माण करें

मान लीजिए कि हमारे पास बाइनरी सर्च ट्री का एक पोस्टऑर्डर ट्रैवर्सल है; हमें इससे बाइनरी सर्च ट्री ढूंढ़ना होगा।

इसलिए, यदि इनपुट [6, 12, 10, 55, 45, 15] जैसा है, तो आउटपुट होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को हल करें () परिभाषित करें। यह पोस्टऑर्डर लेगा

• n :=पोस्टऑर्डर का आकार

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

• stk :=एक स्टैक

• stk में रूट डालें

• मैं :=n - 2

• जबकि मैं>=0, करते हैं

  • x :=मान पोस्टऑर्डर के साथ एक नया नोड बनाएं[i]

  • जबकि stk खाली नहीं है और postorder[i]

    • अस्थायी :=stk के ऊपर

    • stk से शीर्ष तत्व हटाएं

  • अगर अस्थायी शून्य नहीं है, तो

    • अस्थायी.बाएं:=x

  • अन्यथा,

    • stk शीर्ष तत्व के दाईं ओर :=x

  • stk में x डालें

  • मैं :=मैं - 1

• वापसी जड़

• मुख्य विधि से निम्न कार्य करें -

• वापसी हल (पोस्टऑर्डर)

उदाहरण

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

class TreeNode:
   def __init__(self, data = 0):
      self.val = data
      self.left = None
      self.right = None
def solve(postorder):
   n = len(postorder)
   root = TreeNode(postorder[n - 1])
   stk = []
   stk.append(root)
   i = n - 2
   while ( i >= 0):
      x = TreeNode(postorder[i])
      temp = None
      while (len(stk) > 0 and postorder[i] < stk[-1].val) :
         temp = stk[-1]
         stk.pop()
      if (temp != None):
         temp.left = x
      else:
         stk[-1].right = x
      stk.append(x)
      i = i - 1
   return root
def build_tree(postorder):
   return solve(postorder)
def inord( node):
   if node:
      inord(node.left)
      print( node.val, end = " ")
      inord(node.right)
postorder = [6, 12, 10, 55, 45, 15]
root = build_tree(postorder)
print( "Inorder traversal:", end = " ")
inord(root)

इनपुट

[6, 12, 10, 55, 45, 15]

आउटपुट

6 10 12 15 45 55