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

ধরুন আমাদের কাছে একটি বাইনারি গাছের ইনঅর্ডার এবং পোস্টঅর্ডার ট্রাভার্সাল সিকোয়েন্স আছে। আমাদের এই ক্রম থেকে গাছ তৈরি করতে হবে। তাই যদি পোস্টঅর্ডার এবং ইনঅর্ডার ক্রম [9,15,7,20,3] এবং [9,3,15,20,7] হয়, তাহলে গাছটি হবে −

আসুন ধাপগুলো দেখি -

• বিল্ড_ট্রি() একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি ইনঅর্ডার, পোস্টঅর্ডার −

  লাগবে

• যদি ইনঅর্ডার তালিকা খালি না হয় -

  • root :=পোস্টঅর্ডারের শেষ মান দিয়ে একটি ট্রি নোড তৈরি করুন, তারপর সেই উপাদানটি মুছুন

  • ind :=ক্রম তালিকায় রুট ডেটার সূচী

  • রুটের ডানদিকে :=বিল্ড_ট্রি (ইনডেক্স ইন্ডেক্স থেকে শেষ পর্যন্ত, পোস্টঅর্ডার)

  • রুটের বাম :=বিল্ড_ট্রি (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):
   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()
print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))

ইনপুট

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

আউটপুট

[9,3,15,20,7]