Вопросы для интервью - Сериализация и десериализация n-арного дерева
Я недавно столкнулся с этим вопросом во время интервью, и интервьюер попросил меня создать две функции. Функция 1 должна взять n-арное дерево и преобразовать его в байтовый массив, а функция 2 должна взять байт [] и построить n-арное дерево. Если бы это было бинарное дерево, я бы сделал обход предварительного заказа со специальным символом для нуля и сохранил бы его в массиве и преобразовал бы в byte[], но здесь n-арное дерево (со многими дочерними элементами). Я не знаю, как сохранить это и перестроить n-арное дерево с массивом. Любые идеи или формулы для хранения этого n-арного дерева в массиве? Я ценю вашу помощь.
3 ответа
Необходимо различать два случая: 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.
Выглядит для меня как хорошее применение для рекурсии. Напишите метод (подпрограмма, функция), который записывает один узел и все дерево под ним. Он записывает узел, затем записывает количество дочерних элементов (ноль для конечных узлов), а затем вызывает себя для записи каждого дочернего элемента, если таковые имеются. Теперь вызовите метод на верхнем узле дерева, и вы его сериализовали.
Чтобы десериализовать, напишите метод, который читает в узле. Он будет читать в самом узле, читать количество дочерних узлов, а затем читать в каждом дочернем узле, если таковые имеются. Вызовите его один раз в потоке, и он передаст вам верхний узел со всеми узлами-потомками на месте - все дерево.
Мораль этой истории в том, что рекурсия (которая на самом деле является просто удобным способом получить и использовать стек) действительно полезна для работы с графиками. И гораздо больше вещей, чем вы думаете, являются графиками.
На самом деле википедия помогла мне найти решение. Я могу сохранить n-арное дерево в массив и преобразовать в byte[], а затем преобразовать byte[] обратно в массив, используя следующую формулу. C-й дочерний элемент найден по индексу k*i + 1 + c. по индексу я -1/2
Вот код, 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