这是我用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
这段代码有缺陷,在左侧和右侧都复制了一个子节点。我已经调试了代码,似乎当递归折叠出来时,索引减少了,因此我得到了这个行为。有人能帮我吗。你知道吗
我无法轻易得到保罗的答案,所以我终于设法解决了这个问题。感谢Paul帮助我理解了不变性和副作用问题,这是主要的bug。我使用了迭代器而不是整数索引。你知道吗
在Python中有两大类对象:不可变对象和可变对象。必须了解它们之间的区别:
类似地,如果您将一个列表传递给一个函数,而该函数更改了该列表,但没有显式地返回它,那么调用方仍然可以看到这些更改,事实上,任何持有该列表引用的人都可以看到这些更改。有人说这是副作用。您正在序列化程序中使用此技术。你知道吗
如果将
index
这样的不可变对象传递给函数,并在函数中对其进行操作,则原始对象不会更改。函数中的名称只是绑定到调用方不可见的新对象,除非显式返回它们。你知道吗因此,要修复反序列化程序,请尝试返回子树和当前索引,如下所示
所以打电话的人可以像这样更新他们的
相关问题 更多 >
编程相关推荐