পাইথন প্রোগ্রামিং-এ বাইনারি ট্রি পোস্টঅর্ডার ট্রাভার্সাল

ধরুন আমাদের একটি বাইনারি গাছ আছে। আমাদের পুনরাবৃত্ত পদ্ধতি ব্যবহার করে এই গাছের পোস্ট অর্ডার ট্রাভার্সাল খুঁজে বের করতে হবে। তাই গাছটি যদি −

তারপর আউটপুট হবে:[9,15,7,10,-10]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি রুট নাল হয়, তাহলে খালি অ্যারে ফেরত দিন

• একটি অ্যারে ret তৈরি করুন

• স্ট্যাক :=জোড়া দিয়ে একটি স্ট্যাক সংজ্ঞায়িত করুন [root, 0]

• স্ট্যাক খালি না থাকার সময় −

  • node :=স্ট্যাকের উপরে, তারপর স্ট্যাক থেকে উপাদান মুছে দিন।

  • যদি নোড জোড়ার দ্বিতীয় মান 0 হয়, তাহলে

    • বর্তমান :=নোড জোড়ার প্রথম মান

    • স্ট্যাকের মধ্যে একটি জোড়া (বর্তমান, 1) সন্নিবেশ করুন

    • যদি বর্তমানের অধিকার উপস্থিত থাকে

      • স্ট্যাকের মধ্যে একটি জোড়া [কারেন্টের ডানদিকে, 0] সন্নিবেশ করান

    • যদি বর্তমানের বাম উপস্থিত থাকে -

      • স্ট্যাকের মধ্যে একটি জোড়া [কারেন্টের বামে, 0] সন্নিবেশ করান

  • অন্যথায় যখন প্রথম মানের নোড জোড়ার ডেটা 0 না হয়, তখন নোডের প্রথম মানের ডেটা res এ প্রবেশ করান

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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]