Вопросы для интервью - Сериализация и десериализация n-арного дерева

Question

Я недавно столкнулся с этим вопросом во время интервью, и интервьюер попросил меня создать две функции. Функция 1 должна взять n-арное дерево и преобразовать его в байтовый массив, а функция 2 должна взять байт [] и построить n-арное дерево. Если бы это было бинарное дерево, я бы сделал обход предварительного заказа со специальным символом для нуля и сохранил бы его в массиве и преобразовал бы в byte[], но здесь n-арное дерево (со многими дочерними элементами). Я не знаю, как сохранить это и перестроить n-арное дерево с массивом. Любые идеи или формулы для хранения этого n-арного дерева в массиве? Я ценю вашу помощь.

Answer 1

Необходимо различать два случая: 1. полные n-арные деревья и 2. редкие n-арные или неполные деревья. В первом случае, предполагая, что N=5, поэтому каждый уровень i в Дереве будет иметь ровно (то есть, не меньше, не больше) 5 ^ i узлов; с другой стороны, во втором случае это правило не действует, так как дерево может быть заполнено случайным образом по построению.

Полные n-арные деревья могут быть сериализованы в массив; просто выходя из полного дерева двоичного поиска: узлы (промежуточные и конечные) связаны между собой уровнем i и фактическим N форумом N i + 1 + c *, где c - это c-й дочерний элемент. Приняв обход уровня порядка, дерево можно оптимально сериализовать в виде массива байтов (дополнительные символы не требуются, читайте далее). Здесь исчерпывающее объяснение.

К сожалению, для неполных n-арных деревьев, как и ожидалось, приведенная выше формула не применяется. Поэтому необходимо принять другой подход. Один из подходов состоит в сериализации специальных символов, указывающих на отсутствие дочерних элементов, или в лучшую сериализацию значений NULL для дочерних указателей. Этот подход не является оптимальным, поскольку требуется дополнительное количество символов (требуется всего N дополнительных байтов), но он довольно простой и жизнеспособный. Давайте рассмотрим пример:

       A
     / | \ 
    B  C  D
   / \     \
  E   F     G

Принимая обход предварительного заказа, вышеуказанное неполное n-арное дерево сериализуется следующим образом

 A B E / F / / C / D G / / /

'/' отображает NULL и предоставляет возможность десериализации Дерева в исходное. Предварительный заказ принят, чтобы посетить дерево и вывести вышеуказанный массив символов. Всего *2*N* байтов сериализуется, так как в этом случае значения дерева равны ровно 1 символу каждое. В качестве алгоритма десериализации все же может быть принят обход предварительного заказа: требуется несколько модификаций для распознавания шаблона отображения NULL, как показано выше. Пример кода на C++ здесь.

Заключение, сериализация и десериализация неполного или разреженного n-арного дерева немного сложнее и требует дополнительного количества байтов для принудительного отображения значений NULL.

Answer 2

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

Чтобы десериализовать, напишите метод, который читает в узле. Он будет читать в самом узле, читать количество дочерних узлов, а затем читать в каждом дочернем узле, если таковые имеются. Вызовите его один раз в потоке, и он передаст вам верхний узел со всеми узлами-потомками на месте - все дерево.

Мораль этой истории в том, что рекурсия (которая на самом деле является просто удобным способом получить и использовать стек) действительно полезна для работы с графиками. И гораздо больше вещей, чем вы думаете, являются графиками.

Answer 3

На самом деле википедия помогла мне найти решение. Я могу сохранить n-арное дерево в массив и преобразовать в byte[], а затем преобразовать byte[] обратно в массив, используя следующую формулу. C-й дочерний элемент найден по индексу k*i + 1 + c. по индексу я -1/2

Answer 4

Вот код, BFS + Queue, должен быть прямо для чтения.

class Node:
    def __init__(self, val):
        self.val = val 
        self.children = []

class Codec:
    def serialize(self, root):
        if root is None:
            return ""
        res = [root.val, "#"]
        q = collections.deque([root])
        while q:
            node = q.popleft()
            for child in node.children:
                res.append(child.val)
                q.append(child)
            res.append("#")
        return ",".join(res)

    def deserialize(self, s):
        if len(s) == 0:
            return
        vals = s.split(",")
        q = collections.deque()
        root = Node(vals[0])
        q.append(root)
        i = 1
        while q:
            node = q.popleft()
            i += 1
            while vals[i] != "#":
                child = Node(vals[i])
                node.children.append(child)
                q.append(child)
                i += 1
        return root