Небольшой проект, в котором реализован кодек для древовидной структуры произвольной глубины:
encode(tree) -> string и decode(string) -> tree.
Цель — получить компактное строковое представление дерева и гарантировать, что по этой строке можно полностью восстановить исходную структуру (с любым уровнем вложенности).
- Дерево произвольной глубины (n-ary tree)
- Узлы с обязательными полями:
id— уникальный идентификаторchildren— массив дочерних узлов (может быть пустым)
- Преобразование
tree -& 63D6 gt; compact string -> tree - Проверка корректности восстановления (assert/сравнение результатов в консоли)
Алгоритм использует рекурсивный обход дерева и преобразует структуру в строку так, чтобы:
- количество проходов по объекту было минимальным
- строка была как можно короче, но при этом однозначно декодировалась
- декодирование восстанавливало исходное дерево без потерь
Сложность по времени: O(n), где n — количество узлов.
Память: O(h) на стек рекурсии (где h — глубина дерева).
const tree = {
id: 1,
children: [
{ id: 2, children: [] },
{
id: 3,
children: [
{ id: 4, children: [] },
],
},
],
};