Pythonバイナリツリーのシリアライズ/デシリアライズ

Question

私は、バイナリツリー用のPythonでシリアライズ/デシリアライズアルゴリズムを実装しようとしています。

class Node: 
    count = 1 
    def __init__(self, value): 
     self.value = value 
     self.left = None 
     self.right = None 

    def insert(self, value): 
     if self.value > value: 
      if self.left is None: 
       self.left = Node(value) 
       Node.count += 1 
      else: 
       self.left.insert(value) 
     else: 
      if self.right is None: 
       self.right = Node(value) 
       Node.count += 1 
      else: 
       self.right.insert(value) 

# Using preorder 
def serialize(root, serial): 
    if root != None: 
     serial.append(root.value) 
     serialize(root.left, serial) 
     serialize(root.right, serial) 
    else: 
     serial.append('x') 

def deserialize(newRoot, serial): 
    if serial[0] == 'x': 
     serial.pop(0) 
    else: 
     if len(serial) > 0: 
      newRoot = Node(serial.pop(0)) 
      print(newRoot.value) 
      deserialize(newRoot.left, serial) 
      deserialize(newRoot.right, serial) 

print("This program serializes a tree\n") 

root = Node(3) 
root.insert(1) 
root.insert(2) 
root.insert(4) 
root.insert(5) 
root.insert(0) 

# Serialize 
serial = [] 
serialize(root, serial) 
print(serial) 

# Deserialize 
newRoot = Node(None) 
deserialize(newRoot, serial) 
print(newRoot.value) 

問題は、Pythonは値によってそれを渡すためnewRootトをデシリアライズで更新されません、次のとおりです。

は、ここに私のコードです。これを回避するには、どうすれば最も優雅なやり方でできるのですか？ C/C++では、newRootへのポインタを渡すだけで、それに応じて更新されるはずです。ありがとう！

Answer 1

新しく作成したノードを返し、左右のノードとして割り当てることができます。また、popリストの最初の要素は、最後の要素をpopよりも高価ですので、リストの先頭にreverseを入れてから再帰で使用すると、より効果的になります。コードは次のようになります。

def deserialize(serial): 
    serial.reverse() 
    return _deserialize(serial) 

def _deserialize(serial): 
    if not serial: 
     return None 

    node = None 
    value = serial.pop() 
    if value != 'x': 
     node = Node(value) 
     node.left = _deserialize(serial) 
     node.right = _deserialize(serial) 
    return node 

root = deserialize(serial) 
print(root.value)