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

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

একটি ট্রি গঠনের জন্য আমাদের ইনঅর্ডার ট্রাভার্সালও প্রয়োজন, কিন্তু বাইনারি সার্চ ট্রির জন্য, ইনঅর্ডার ট্রাভার্সাল সাজানো আকারে হবে।

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

• ইনঅর্ডার =পোস্টঅর্ডার ট্রাভার্সালের সাজানো তালিকা।

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

  লাগবে

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

  • 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()
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]