পাইথনে স্ট্যাক ব্যবহার করে প্রদত্ত পোস্টঅর্ডার ট্রাভার্সাল থেকে একটি BST তৈরি করুন

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

সুতরাং, ইনপুট যদি [6, 12, 10, 55, 45, 15] এর মত হয়, তাহলে আউটপুট হবে

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

• একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি পোস্টঅর্ডার গ্রহণ করবে

• n :=পোস্টঅর্ডারের আকার

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

• stk :=একটি স্ট্যাক

• stk

  -এ রুট সন্নিবেশ করান

• i :=n - 2

• যখন i>=0, কর

  • x :=ভ্যালু পোস্টঅর্ডার[i]

    সহ একটি নতুন নোড তৈরি করুন

  • যখন stk খালি না থাকে এবং postorder[i]

    • temp :=stk এর শীর্ষ

    • stk

      থেকে শীর্ষ উপাদান মুছুন

  • যদি temp শূন্য না হয়, তাহলে

    • temp.left :=x

  • অন্যথায়,

    • stk শীর্ষ উপাদানের ডানদিকে :=x

  • stk

    -এ x ঢোকান

  • i :=i - 1

• রিটার্ন রুট

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• রিটার্ন সল্ভ(পোস্টরডার)

উদাহরণ

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

ক্লাস TreeNode:def __init__(self, data =0):self.val =data self.left =None self.right =Nonedef 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 এবং postorder[i ]  
ইনপুট
 <প্রে>[6, 12, 10, 55, 45, 15]

আউটপুট

6 10 12 15 45 55