Блог

Я работаю над этой проблемой, которую задал Google (не мне):

Учитывая корень двоичного дерева, реализуйте serialize(root), который сериализует дерево в строку, и deserialize(ы), который десериализует строку обратно в дерево.

Это то, что у меня есть до сих пор, но, похоже, я не могу заставить функцию serialize сохранять результаты (снизу дерева и вверх) в строку. Так что я могу распечатать результаты, просто не сохранять их…

 class Tree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.ser_str = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Tree(data)
                else:
                    self.left.insert(data)
            elif data >= self.data:
                if self.right is None:
                    self.right = Tree(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def serialize(self):
        if self.left:
            self.left.serialize()
        print(self.data)
        if self.right:
            self.right.serialize()

root = Tree(23)
root.insert(10);root.insert(124);root.insert(101);root.insert(1);root.insert(40)
print("here comes the sun")
test = root.serialize()
  

Как отмечалось в комментариях, проблема с вашим методом заключается в том, что вы просто печатаете данные, но никогда не объединяете их в строку и не возвращаете. Однако этот формат также не допускает однозначной десериализации дерева.

Если вы не хотите использовать библиотеки, подобные json , которые делают это тривиальным, вы можете прибегнуть к легко анализируемому формату, такому как польская нотация, где a b записывается как a b . В случае дерева data соответствует оператору, left а right ветвь and соответствует операндам.

 def serialize(t):
    if t is None:
        return "-"
    else:
        return f"{t.data} {serialize(t.left)} {serialize(t.right)}"
    
def deserialize(s):
    if isinstance(s, str): s = iter(s.split())
    # using an iterator of chunks makes this easier
    d = next(s)
    if d == "-":
        return None
    else:
        return Tree(d, deserialize(s), deserialize(s))
  

(Обратите внимание, что я создал эти функции, а не методы, и добавил несколько необязательных параметров в Tree конструктор, чтобы упростить код.)

При тестировании с вашим деревом это сериализовало дерево в 23 10 1 - - - 124 101 40 - - - - . (Затем я десериализовал дерево и снова сериализовал его и получил тот же формат, поэтому десериализация тоже должна работать.) Вы можете добавить скобки, чтобы лучше видеть древовидную структуру в строке: (23 (10 (1 - -) -) (124 (101 (40 - -) -) -)) , но формат однозначен даже без скобок.

Это в основном соответствует простому обходу дерева в предварительном порядке, тогда как вы выполняете обход по порядку, который, как и инфиксная нотация a b , не является однозначным без круглых скобок. Обход по порядку возвращает элементы в отсортированном порядке, что хорошо для некоторых применений, но не здесь, поскольку это означает, что по-разному структурированные деревья, содержащие один и тот же элемент, будут сериализованы в один и тот же отсортированный список. Вы могли бы, конечно, просто добавить скобки, но это значительно усложнит синтаксический анализ / десериализацию. С помощью скобок и по порядку ваше дерево будет (((- 1 -) 10 -) 23 (((- 40 -) 101 -) 124 -)) .

(Примечание: даже если сериализация неоднозначна, вы можете воссоздать из нее двоичное дерево, но форма этого дерева будет другой; в частности, это будет вырожденное двоичное дерево, если вы просто вставляете элементы в отсортированном порядке, поскольку они выходят из вашего in-order-обход.)