Python中BST反序列化的错误实现

Question

这是我用Python实现的BST。你知道吗

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, item):
        self.root = self.insert_helper(item, self.root)
        self.size += 1
        return self.root

    def insert_helper(self, item, root):
        if root is None:
            p = Node(item)
            root = p
            return root
        if item > root.data:
            root.right = self.insert_helper(item, root.right)
        else:
            root.left = self.insert_helper(item, root.left)
        return root


class Node:
    def __init__(self, data):
        if data is None:
            raise ValueError('Cannot create Node with None value.')
        self.data = data
        self.left = None
        self.right = None

现在我试图将BST serialize和deserialize放入一个列表中，反之亦然。你知道吗

这是序列化代码。你知道吗

def serialize(root):
    tree_list = []
    serialize_helper(root, tree_list)
    return tree_list


def serialize_helper(root, tree_list):
    if root is None:
        tree_list.append(sys.maxsize)
        return
    tree_list.append(root.data)
    serialize_helper(root.left, tree_list)
    serialize_helper(root.right, tree_list)

这很管用期待着。这个是反序列化的代码。你知道吗

def deserialize(tree_list):
    index = 0
    return deserialize_helper(tree_list, index)


def deserialize_helper(tree_list, index):
    if index == len(tree_list) or tree_list[index] == sys.maxsize:
        return None
    root = Node(tree_list[index])
    index += 1
    root.left = deserialize_helper(tree_list, index)
    root.right = deserialize_helper(tree_list, index)
    return root

这段代码有缺陷，在左侧和右侧都复制了一个子节点。我已经调试了代码，似乎当递归折叠出来时，索引减少了，因此我得到了这个行为。有人能帮我吗。你知道吗

Answer 1

我无法轻易得到保罗的答案，所以我终于设法解决了这个问题。感谢Paul帮助我理解了不变性和副作用问题，这是主要的bug。我使用了迭代器而不是整数索引。你知道吗

def deserialize(tree_list):
    itr = iter(tree_list)
    return deserialize_helper(tree_list, itr)


def deserialize_helper(tree_list, itr):
    item = next(itr)
    if item is None or item == sys.maxsize:
        return None
    p = Node(item)
    p.left = deserialize_helper(tree_list, itr)
    p.right = deserialize_helper(tree_list, itr)
    return p

Answer 2

在Python中有两大类对象：不可变对象和可变对象。必须了解它们之间的区别：

a = [] # a list, lists are mutable
b = a  # b and a now reference the same object
b.append(1)  # change b and the change will be in-place
print(a)     # since a references the same object
# [1]

a = 1 # an int, ints are immutable
b = a # b and a may well reference the same object, but
b += 1   # since the object cannot change a new object is bound to b
print(a) # leaving a unaffected
# 1

类似地，如果您将一个列表传递给一个函数，而该函数更改了该列表，但没有显式地返回它，那么调用方仍然可以看到这些更改，事实上，任何持有该列表引用的人都可以看到这些更改。有人说这是副作用。您正在序列化程序中使用此技术。你知道吗

如果将index这样的不可变对象传递给函数，并在函数中对其进行操作，则原始对象不会更改。函数中的名称只是绑定到调用方不可见的新对象，除非显式返回它们。你知道吗

因此，要修复反序列化程序，请尝试返回子树和当前索引，如下所示

return root, index

所以打电话的人可以像这样更新他们的

root.left, index = deserialize_helper(tree_list, index)