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

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें पुनरावृत्त दृष्टिकोण का उपयोग करके इस पेड़ के पोस्ट ऑर्डर ट्रैवर्सल को खोजना होगा। तो अगर पेड़ जैसा है -

तब आउटपुट होगा:[9,15,7,10,-10]

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

• यदि रूट शून्य है, तो खाली सरणी लौटाएं

• एक सरणी रिट बनाएं

• स्टैक :=जोड़ी के साथ स्टैक को परिभाषित करें [रूट, 0]

• जबकि स्टैक खाली नहीं है -

  • नोड:=स्टैक के ऊपर, फिर स्टैक से तत्व हटाएं।

  • यदि नोड जोड़ी का दूसरा मान 0 है, तो

    • वर्तमान:=नोड जोड़ी का पहला मान

    • स्टैक में एक जोड़ी (वर्तमान, 1) डालें

    • अगर करंट का अधिकार मौजूद है

      • स्टैक में एक जोड़ी [वर्तमान का अधिकार, 0] डालें

    • अगर बायां करंट मौजूद है -

      • स्टैक में एक जोड़ी [वर्तमान के बाएँ, 0] डालें

  • अन्यथा जब पहले मान नोड जोड़ी का डेटा 0 नहीं है, तो नोड के पहले मान का डेटा रेस में डालें

• रिटर्न रेस

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

उदाहरण

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.data = data
   self.left = left
   self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def postorderTraversal(self, root):
      if not root:
         return []
      res = []
      stack = [[root,0]]
      while stack:
         node = stack[-1]
         stack.pop()
         if node[1]== 0 :
            current = node[0]
            stack.append([current,1])
            if current.right:
               stack.append([current.right,0])
            if current.left:
               stack.append([current.left,0])
         else:
            if node[0].data != 0:
               res.append(node[0].data)
      return res
ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.postorderTraversal(root))

इनपुट

[-10,9,10,None,None,15,7]

आउटपुट

[9, 15, 7, 10, -10]