Существует проблема, предложенная Google для разработки алгоритма сериализации и десериализации двоичного дерева. Я нашел одно из решений онлайн. Часть, которую я не очень понимаю, это то, почему условие необходимо в строке 20, где «if node == None:», self. root = Node (value)? Потому что, в конце концов, эта программа предложит пользователю ввести узлы в форме, например: 1,3,5, чтобы программа работала, поэтому, следовательно, не будет случая, когда узел = нет, потому что ввод пользователя необходим? Я неправильно понимаю что-то еще здесь?
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
class Tree:
def __init__(self):
self.root = None
def addNode(self, node, value): #Why when node==None, self.root= Node(value)?
if node == None:
self.root = Node(value)
else:
if value < node.value:
if not node.left:
node.left = Node(value)
else:
self.addNode(node.left, value)
else:
if not node.right:
node.right = Node(value)
else:
self.addNode(node.right, value)
def serialize(root):
values = []
def serializer(node):
if not node:
values.append('?')
else:
values.append(str(node.value))
serializer(node.left)
serializer(node.right)
serializer(root)
return ','.join(values)
def deserialize(s):
values = iter(s.split(','))
def deserializer():
val = next(values)
if val == '?':
return None
else:
node = Node(int(val))
node.left = deserializer()
node.right = deserializer()
return node
return deserializer()
if __name__ == '__main__':
# Read input, numbers separated by commas
numbers = [int(n) for n in input().split(',')]
theTree = Tree()
for number in numbers:
theTree.addNode(theTree.root, number)
s1 = serialize(theTree.root)
s2 = serialize(deserialize(s1))
print(s1)
print(s2)
assert s1 == s2