Python Serializing/Deserializing 一棵二叉树

Question

我正在尝试在 python 中为二叉树实现 serializing/deserializing 算法。

这是我的代码：

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

您可以return新创建的节点并将它们分配为左右节点。此外，poping 列表的第一个元素比 poping 最后一个元素的成本更高，因此 reverseing 列表的开头然后在递归中使用它会更高效在你的情况下。所以代码会变成这样：

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

您可以在反序列化函数和 return 根中创建左右子树。这是我的代码：

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('')

Python Serializing/Deserializing 一棵二叉树

Python Serializing/Deserializing a binary tree

python

tree

serialization

binary-tree

graph-algorithm