PythonでBSTをシリアル化および逆シリアル化

二分探索木をシリアル化および逆シリアル化するアルゴリズムを設計するとします。シリアル化は、何か（データ構造またはオブジェクト）をビットのシーケンスに変換して、ファイルまたはメモリバッファーに格納したり、ネットワーク接続リンクを介して送信したりできるようにするプロセスです。これは、プロセスが逆シリアル化された後で再構築できます。

したがって、入力が[5,2,9,1,3,7]のような場合、出力はシリアル化された出力5.2.9.1.3.7.N.N.N.N.N.N.N逆シリアル化された出力になります：1、2、3、5、7、9 （順方向トラバーサル）

これを解決するには、次の手順に従います-

• 関数serialize（）を定義します。これが定着します

• res：=新しいリスト

• 1つのキューを定義し、ルートを挿入します

• キューが空でない間は、実行してください

  • キューが空でないときに、実行します

    • 現在：=キュー[0]

    • resの最後に電流を挿入

    • キューから最初の要素を削除する

    • 電流がゼロ以外の場合、

      • ループから出てきます

  • currentがnullの場合、

    • ループから出てきます

  • current.leftがnullでない場合、

    • キューの最後にcurrent.leftを挿入します

  • それ以外の場合

    • キューの最後にNoneを挿入します

  • current.rightがnullでない場合、

    • キューの最後にcurrent.rightを挿入します

  • それ以外の場合

    • キューの最後にNoneを挿入します

• s：=空白の文字列

• 0から解像度のサイズまでの範囲のiの場合、実行します

  • res [i]がゼロ以外の場合、

    • s：=s連結res[i] .data

  • それ以外の場合

    • s：=s連結"N"

  • iがres-1のサイズと同じ場合、

    • ループから出てきます

  • s：=s連結"。"

• sを返す

• 関数deserialize（）を定義します。これにはデータが必要です

• data：=ドットを使用してデータを分割した後のパーツのリスト

• スタック：=新しいリスト

• data[0]が'N'と同じ場合、

  • なしを返す

• root：=データデータを使用して新しいノードを作成します[0]

• スタックの最後にルートを挿入します

• i：=1

• 現在：=0

• <データのサイズ、実行

  • 左：=False

  • data[i]が'N'と同じでない場合、

    • temp：=データデータを使用して新しいノードを作成します[i]

    • stack [current] .left：=temp

    • スタックの最後に温度を挿入

  • それ以外の場合

    • stack [current] .left：=None

  • i：=i + 1

  • data[i]が'N'と同じでない場合、

    • temp：=データデータを使用して新しいノードを作成します[i]

    • stack [current] .right：=temp

    • スタックの最後に温度を挿入

  • それ以外の場合

    • stack [current] .right：=None

  • current：=current + 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,