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

ধরুন আমাদের একটি বাইনারি ট্রি আছে আমাদের একটি স্ট্রিং তৈরি করতে হবে যা প্রি-অর্ডার ট্রাভার্সিং উপায় সহ একটি বাইনারি ট্রি থেকে বন্ধনী এবং পূর্ণসংখ্যা নিয়ে গঠিত। একটি নাল নোড খালি প্যারেনথেসিস জোড়া "()" দ্বারা প্রতিনিধিত্ব করা হবে। এবং আমাদের সমস্ত খালি বন্ধনী জোড়া বাদ দিতে হবে যেগুলি স্ট্রিং এবং আসল বাইনারি ট্রির মধ্যে এক-এক-ম্যাপিং সম্পর্ককে প্রভাবিত করে না৷

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

তাহলে আউটপুট হবে 5(6()(8))(7)

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

• উত্তর :=ফাঁকা স্ট্রিং
• একটি ফাংশন পট() সংজ্ঞায়িত করুন। এটি নোড, এস
নেবে
• যদি শূন্য হয়, তাহলে
  • খালি স্ট্রিং ফেরত দিন
• যদি নোডের বাম বা ডান শূন্য হয়, তাহলে
  • রিটার্ন node.data
• ss :=node.data
• যদি node.left শূন্য না হয়, তাহলে
  • ss :=ss concatenate '(' concatenate pot(node.left, blank string) concatenate ')'
• অন্যথায়,
  • ss :=ss concatenate '()'
• যদি node.right শূন্য না হয়, তাহলে
  • ss :=ss concatenate '(' concatenate pot(node.right, blank string) concatenate ')'
• ss রিটার্ন করুন
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
• রিটার্ন পট(টি, ফাঁকা স্ট্রিং)

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

উদাহরণ

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:
   def tree2str(self, t: TreeNode):
      ans = ''
      def pot(node, s):
         if node == None or node.data == 0:
            return ''
         if node.left == node.right == None:
            return str(node.data)
         ss = str(node.data)
         if node.left != None:
            ss = ss + '(' + pot(node.left, '') + ')'
         else:
            ss = ss + '()'
         if node.right != None:
            ss = ss + '(' + pot(node.right, '') + ')'
         return ss
      return pot(t, '')
ob = Solution()
root = make_tree([5,6,7,None,8])
print(ob.tree2str(root))

ইনপুট

[5,6,7,None,8]

আউটপুট

5(6()(8))(7)