Сериализация 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)

Проблема в том, что newRoot не обновляется при десериализации, потому что python передает его по значению. Как мне обойти это, желательно самым элегантным способом? В 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)

Answer 2

Вы можете создать левое и правое поддерево в функции десериализации и вернуть корень. Вот мой код:

      node_list = []
MARKER = -1
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
    
def serialize(root):
    if root is None:
        node_list.append(MARKER)
        return

    node_list.append(root.val)
    serialize(root.left)
    serialize(root.right)

def deserialize(root, node_list):
    if node_list:
        val = node_list.pop(0)
    else:
        return
    
    if val == MARKER:
        return

    # Create root, left and right recursively
    root = Node(val)
    root.left = deserialize(root.left, node_list)
    root.right = deserialize(root.right, node_list)
    return root

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=' ')
        inorder_traversal(root.right)

if __name__=="__main__":
    # Create tree
    root = Node(20)
    root.left = Node(8)
    root.right = Node(22)
    root.left.left = Node(4)
    root.left.right = Node(12)
    root.left.right.left = Node(10)
    root.left.right.right = Node(14)

    print("Inorder traversal before serialization..")
    inorder_traversal(root)
    print('')

    # serialize the tree and insert elements into a list
    serialize(root)
    print(node_list)

    root1 = None
    root1 = deserialize(root1, node_list)
    print("Inorder traversal after deserialization..")
    inorder_traversal(root1)
    print('')