পাইথনে বিএসটি সিরিয়ালাইজ এবং ডিসিরিয়ালাইজ করুন

ধরুন আমরা একটি বাইনারি সার্চ ট্রিকে সিরিয়ালাইজ এবং ডিসিরিয়ালাইজ করার জন্য একটি অ্যালগরিদম ডিজাইন করতে চাই। সিরিয়ালাইজেশন হল কোনো কিছুকে (ডেটা স্ট্রাকচার বা অবজেক্ট) বিটের ক্রমানুসারে রূপান্তর করার প্রক্রিয়া যাতে এটি একটি ফাইল বা মেমরি বাফারে সংরক্ষণ করা যায়, বা নেটওয়ার্ক সংযোগ লিঙ্ক জুড়ে প্রেরণ করা যায়। এটি পরে পুনর্গঠন করা যেতে পারে যে প্রক্রিয়াটি ডিসিরিয়ালাইজেশন।

সুতরাং, যদি ইনপুটটি [5,2,9,1,3,7] এর মতো হয়, তবে আউটপুটটি হবে সিরিয়ালাইজড আউটপুট 5.2.9.1.3.7.N.N.N.N.N.N.Dserialized আউটপুট:1, 2, 3, 5, 7, 9, (অর্ডার ট্রাভার্সাল)

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

• একটি ফাংশন serialize() সংজ্ঞায়িত করুন। এটি রুট নেবে

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

• একটি সারি সংজ্ঞায়িত করুন এবং রুট সন্নিবেশ করুন

• সারি খালি না থাকার সময়, করুন

  • সারি খালি না থাকার সময়, করুন

    • বর্তমান :=সারি[0]

    • রেস এর শেষে বর্তমান সন্নিবেশ করুন

    • সারি থেকে প্রথম উপাদান মুছুন

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

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

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

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

  • যদি current.left শূন্য না হয়, তাহলে

    • সারির শেষে current.left সন্নিবেশ করুন

  • অন্যথায়,

    • সারির শেষে কোনোটিই সন্নিবেশ করান না

  • যদি current.right শূন্য না হয়, তাহলে

    • সারির শেষে বর্তমান সন্নিবেশ করুন

  • অন্যথায়,

    • সারির শেষে কোনোটিই সন্নিবেশ করান না

• s:=ফাঁকা স্ট্রিং

• আমি 0 থেকে রেজের আকারের মধ্যে, কর

  • যদি res[i] অ-শূন্য হয়, তাহলে

    • s :=s concatenate res[i].data

  • অন্যথায়,

    • s :=s concatenate "N"

  • যদি আমি res-1 এর আকারের সমান হয়, তাহলে

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

  • s :=s concatenate "."

• s

  ফেরত দিন

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

• ডেটা :=ডট ব্যবহার করে ডেটা ভাগ করার পর অংশগুলির একটি তালিকা

• স্ট্যাক :=একটি নতুন তালিকা

• যদি ডেটা[0] 'N' এর মত হয়, তাহলে

  • কোনটিই ফেরত দিন

• root :=ডেটা ডেটা দিয়ে একটি নতুন নোড তৈরি করুন[0]

• স্ট্যাকের শেষে রুট ঢোকান

• i :=1

• বর্তমান :=0

• যখন আমি <ডেটার আকার, কর

  • বাম:=মিথ্যা

  • যদি ডেটা[i] 'N' এর মতো না হয়, তাহলে

    • temp :=ডেটা ডেটা দিয়ে একটি নতুন নোড তৈরি করুন[i]

    • স্ট্যাক[বর্তমান]।লেফট :=টেম্প

    • স্ট্যাকের শেষে তাপমাত্রা সন্নিবেশ করুন

  • অন্যথায়,

    • স্ট্যাক[বর্তমান].লেফট :=কোনোটিই নয়

  • i :=i + 1

  • যদি ডেটা[i] 'N' এর মতো না হয়, তাহলে

    • temp :=ডেটা ডেটা দিয়ে একটি নতুন নোড তৈরি করুন[i]

    • স্ট্যাক [বর্তমান]। ডান :=টেম্প

    • স্ট্যাকের শেষে তাপমাত্রা সন্নিবেশ করুন

  • অন্যথায়,

    • স্ট্যাক[বর্তমান]।ঠিক :=কোনোটিই নয়

  • বর্তমান :=বর্তমান + 1

  • i :=i + 1

• রিটার্ন রুট

উদাহরণ

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

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
def print_tree(root):
   #print using inorder traversal
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Codec:
   def serialize(self, root):
      res =[]
      queue = [root]
      while queue:
         while True and queue:
            current = queue[0]
            res.append(current)
            queue.pop(0)
            if current:
               break
         if not current:
            break
         if current.left:
            queue.append(current.left)
         else:
            queue.append(None)
         if current.right:
            queue.append(current.right)
         else:
            queue.append(None)
      s=""
      for i in range(len(res)):
         if res[i]:
            s+=str(res[i].data)
         else:
            s+="N"
         if i == len(res)-1:
            break
         s+="."
      return s
   def deserialize(self, data):
      data = data.split(".")
      stack = []
      if data[0]=='N':
         return None
      root = TreeNode(int(data[0]))
      stack.append(root)
      i = 1
      current = 0
      while i <len(data):
         left= False
         if data[i] !='N':
            temp = TreeNode(int(data[i]))
            stack[current].left = temp
            stack.append(temp)
         else:
            stack[current].left = None
         i+=1
         if data[i] !='N':
            temp = TreeNode(int(data[i]))
            stack[current].right = temp
            stack.append(temp)
         else:
            stack[current].right = None
         current+=1
         i+=1
         return root

ob = Codec()
root = make_tree([5,2,9,1,3,7])
ser = ob.serialize(root)
print('Serialization:',ser)
print_tree(ob.deserialize(ser))

ইনপুট

[5,2,9,1,3,7]

আউটপুট

Serialization: 5.2.9.1.3.7.N.N.N.N.N.N.N
1, 2, 3, 5, 7, 9,