পাইথনে একটি বাইনারি গাছের একটি ইনঅর্ডার ট্রাভার্সাল করার জন্য প্রোগ্রাম

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

• বারবার বাম সাবট্রি অতিক্রম করুন।

• বর্তমান নোড অতিক্রম করুন৷

• বারবার ডান সাবট্রি অতিক্রম করুন।

আমাদের এই সমস্যাটি পুনরাবৃত্তিমূলক পদ্ধতিতে সমাধান করার চেষ্টা করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে [12,13,4,16,7,14,22]

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

• inorder :=একটি নতুন তালিকা

• স্ট্যাক :=একটি খালি স্ট্যাক

• নিম্নলিখিতটি অসীমভাবে করুন, করুন

  • যদি রুট শূন্য না হয়, তাহলে

    • স্ট্যাকের মধ্যে রুট পুশ করুন

    • root :=রুটের বাম

  • অন্যথায় যখন স্ট্যাক খালি না থাকে, তখন

    • root :=স্ট্যাকের শীর্ষ উপাদান এবং স্ট্যাক থেকে পপ

    • ইনসর্ডারের শেষে রুটের মান সন্নিবেশ করান

    • root :=রুটের ডানদিকে

  • অন্যথায়,

    • লুপ থেকে বেরিয়ে আসুন

• রিটার্ন ইনঅর্ডার

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

উদাহরণ

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None
class Solution:
   def solve(self, root):
      inorder = []
      stack = []
      while True:
         if root:
            stack.append(root)
            root = root.left
         elif stack:
            root = stack.pop()
            inorder.append(root.val)
            root = root.right
         else:
            break
      return inorder

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

ইনপুট

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

আউটপুট

[12, 13, 4, 16, 7, 14, 22]