Сериализация дерева в массив: форматы и восстановление структуры

Сериализация дерева в массив сводится к одному правилу: узлы обходят в фиксированном порядке, пустые потомки помечают маркером, а на приёмнике той же логикой собирают структуру обратно. Второй рабочий путь — хранить один или два обхода (preorder, inorder, postorder) и восстанавливать дерево по ним. Оба подхода линейны: O(n) на запись и O(n) на чтение.

Выбор формата определяют три числа: сколько элементов попадает в массив, сколько нужно дополнительной памяти и как глубоко уходит рекурсия. Полное дерево из 7 узлов в уровневом виде с обрезанным хвостом даёт 7 элементов, preorder с маркерами — 15, пара preorder и inorder — 14. Вырожденное дерево из 7 узлов, где у каждого узла есть только левый потомок, в уровневой записи разрастается заметно сильнее, а в preorder с маркерами остаётся на 15. Эти цифры и определяют практический выбор.

Плоский массив удобен как транспорт: парсер читает значения одним проходом, данные сжимаются gzip, brotli или zstd и упаковываются в бинарные форматы вроде Protobuf, MessagePack или FlatBuffers. Вложенный JSON держит имена полей «val», «left», «right» в каждом узле, то есть тратит 20–30 байт на узел только на служебные строки, тогда как массив хранит значения и маркеры. Что это даёт на уровне доступа к данным и как массив соотносится со связными структурами, разбираем в материале связные списки или массивы: что выбрать для хранения данных.

Типичные места применения: иерархия директив Nginx, вложенные секции Kubernetes-манифестов, деревья зависимостей пакетов, индексы СУБД, кэш в Redis, разбор логов с вложенным контекстом. Во всех случаях дерево живёт на одной стороне, а на другой его нужно быстро собрать заново.

Зачем сериализовать дерево в массив

Причина простая: транспорт и хранилище работают с линейными потоками. Сокет, колонка в таблице, файл и очередь сообщений принимают байты или строку, а не объект с указателями. Массив снимает три ограничения: он сериализуется одним проходом без рекурсивного спуска по вложенности, одинаково выглядит в JSON, MessagePack и Protobuf, и предсказуемо сжимается, потому что соседние значения часто коррелируют.

Второй аргумент — стоимость разбора. Вложенный JSON требует, чтобы парсер держал стек вложенности, проверял соответствие фигурных скобок и строил промежуточные объекты. Плоский массив с числами и маркерами читается циклом с курсором: восстановление BFS-записи держит в памяти одну очередь, восстановление preorder-записи — стек глубиной в высоту дерева.

Третий аргумент — хранение. Одна колонка с сериализованным деревом избавляет от рекурсивных SQL-запросов и от соединений таблицы с самой собой. Как раскладывать такие массивы по схемам и когда лучше вынести узлы в отдельные строки, подробно разобрано в статье как хранить массивы в реляционной базе данных.

Формат с маркерами пустых узлов: сериализация и восстановление

Пустой потомок нельзя оставить простым пропуском: парсер потеряет границу между отсутствующим левым и существующим правым ребёнком. Каждую пустую ссылку кодируют маркером: null в JSON, # в текстовом виде, -1 или 0 для деревьев с неотрицательными значениями. Маркер выбирают вне диапазона реальных данных, иначе дерево восстановится неверно. Необходимость null-маркеров при сериализации обычного бинарного дерева и невозможность различить структуры без них описаны в разборе задачи Serialize and Deserialize Binary Tree; там же null-узлы в BFS-записи обозначаются символом «#».

Пример: корень 1 с потомками 2 и 3, у узла 2 левый потомок пуст, правый равен 4. Уровневый обход даёт [1, 2, 3, null, 4]. Хвостовые маркеры последнего уровня отбрасывают: они не несут информации, потому что после последнего реального узла структура однозначно определяется предыдущими парами. Если оставить все маркеры, массив занимает больше позиций, чем узлов.

Сериализация через BFS с маркерами

Алгоритм: очередь, в неё кладём корень, вынимаем узел, пишем значение, добавляем в очередь левого и правого потомка, включая пустые. Пустой узел дописывает в массив маркер и не порождает новых элементов очереди. В конце обрезаем хвостовые маркеры.

from collections import deque

def serialize_bfs(root):
    if root is None:
        return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.val)
        q.append(node.left)
        q.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

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

Восстановление дерева из BFS-массива

Порядок работы:

Пустой массив означает пустое дерево, возвращаем None.
Первый элемент становится корнем и попадает в очередь.
Курсор i = 1. Для каждого узла из очереди читаем два следующих элемента: они задают левого и правого потомка. Маркер означает отсутствие потомка, реальное значение создаёт узел и добавляет его в очередь.
Цикл идёт, пока очередь не опустеет или курсор не дойдёт до конца массива.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def deserialize_bfs(data):
    if not data:
        return None
    root = TreeNode(data[0])
    q, i = deque([root]), 1
    while q and i < len(data):
        node = q.popleft()
        if i < len(data):
            v = data[i]; i += 1
            if v is not None:
                node.left = TreeNode(v)
                q.append(node.left)
        if i < len(data):
            v = data[i]; i += 1
            if v is not None:
                node.right = TreeNode(v)
                q.append(node.right)
    return root

Проверка на [1, 2, 3, None, 4]: корень 1, левый потомок 2, правый 3, у узла 2 появляется правый потомок 4, левый остаётся пустым. Сложность O(n) по времени, память O(w), где w — максимальная ширина дерева; для полного дерева это n/2 узлов в очереди.

Префиксная запись обходов: preorder, inorder, postorder

Три обхода различаются позицией корня. Preorder пишет корень, затем левое и правое поддерево. Inorder идёт левое, корень, правое. Postorder — левое, правое, корень. Для дерева 1 с потомками 2 и 3 получаем preorder [1, 2, 3], inorder [2, 1, 3], postorder [2, 3, 1].

Один обход не задаёт дерево однозначно. Последовательность [1, 2, 3] в preorder описывает и цепочку 1-2-3 по левым потомкам, и корень 1 с двумя потомками 2 и 3. Для восстановления без маркеров нужны два обхода: preorder плюс inorder либо postorder плюс inorder. Пара preorder и postorder для общего бинарного дерева не работает: у дерева из корня 1 и левого потомка 2 и у дерева из корня 1 и правого потомка 2 оба обхода совпадают ([1, 2] и [2, 1]).

Даже если каждый узел имеет 0 или 2 детей, preorder-запись не делает дерево уникальным: деревья 5[1,4[2,3]] и 5[3[1,2],4] дают одинаковый preorder-обход 1 2 3 4 5. Уникальность требует дополнительной информации, например пометки узлов как внутренних или листовых. Этот пример разобран в обсуждении преобразования preorder-списка бинарного дерева в postorder.

Отдельный случай — бинарное дерево поиска. Его inorder выдаёт отсортированную последовательность, поэтому для BST хватает одного preorder: первое значение — корень, а принадлежность последующих значений к левому или правому поддереву определяется сравнением с корнем и границами диапазонов, без null-маркеров. Это свойство и алгоритм восстановления BST по preorder-записи описаны в разборе задачи Serialize and Deserialize BST.

Восстановление дерева по preorder и inorder

Логика опирается на два факта: первый элемент preorder — корень, а позиция этого корня в inorder делит её на левое и правое поддеревья. Число узлов слева задаёт границу срезов в preorder.

Берём preorder[0] как корень.
Находим индекс корня k в inorder.
Узлы inorder[:k] относятся к левому поддереву, inorder[k+1:] — к правому.
В preorder левому поддереву соответствует отрезок длиной k, начиная со второго элемента; остальное уходит правому. Рекурсивно повторяем шаги.

Пример: preorder [3, 9, 20, 15, 7], inorder [9, 3, 15, 20, 7]. Корень 3, слева [9], справа preorder [20, 15, 7] и inorder [15, 20, 7]. Корень правого поддерева 20, его левый потомок 15, правый 7. Результат: 3 с левым 9 и правым 20, у которого дети 15 и 7.

def build_from_pre_in(preorder, inorder):
    if not preorder:
        return None
    root_val = preorder[0]
    k = inorder.index(root_val)
    node = TreeNode(root_val)
    node.left = build_from_pre_in(preorder[1:k + 1], inorder[:k])
    node.right = build_from_pre_in(preorder[k + 1:], inorder[k + 1:])
    return node

Вариант со срезами читается легко, но копирует подмассивы и ищет индекс линейно: на вырожденном дереве это O(n²) времени и лишняя память. Словарь позиций {значение: индекс}, собранный один раз, плюс работа с границами вместо срезов дают O(n) времени и O(n) дополнительной памяти.

Условие применимости: значения узлов уникальны. При дубликатах либо храните пары (значение, позиция в inorder), либо переходите на preorder с маркерами. Ещё одна проверка перед разбором: длины массивов совпадают, а отсортированные копии равны, иначе обходы взяты от разных деревьев.

Для postorder и inorder схема та же, только корень берётся с конца postorder, а последние k элементов (где k — размер правого поддерева) уходят правой ветви.

Сериализация через preorder с маркерами

Один обход решает задачу, если пустые ссылки помечены маркером. Для дерева 1 с потомками 2 и 3 получаем [1, 2, #, #, 3, #, #]: у листьев оба потомка пусты, поэтому после каждого реального узла идут два маркера.

def serialize_pre(root):
    parts = []
    def walk(n):
        if n is None:
            parts.append("#")
            return
        parts.append(str(n.val))
        walk(n.left)
        walk(n.right)
    walk(root)
    return parts

def deserialize_pre(parts):
    it = iter(parts)
    def build():
        v = next(it)
        if v == "#":
            return None
        node = TreeNode(int(v))
        node.left = build()
        node.right = build()
        return node
    return build()

Маркеры обязательны: без них дерево только с левым ребёнком и дерево только с правым ребёнком сериализуются в одну и ту же последовательность. Для разреженных и вырожденных деревьев запись с маркерами заметно компактнее уровневой.

Плата — рекурсивный разбор: глубина стека равна высоте дерева, для вырожденной цепочки это n. Python-интерпретатор ограничивает глубину рекурсии, чтобы предотвратить бесконечную рекурсию и переполнение C-стека; лимит можно изменить через sys.setrecursionlimit(). Максимально возможный лимит зависит от платформы, и поднимать его следует осторожно: слишком высокий лимит может привести к краху. Если новый лимит окажется ниже текущей глубины рекурсии, возникнет исключение. Поведение лимита рекурсии описано в документации модуля sys. Для глубоких деревьев либо аккуратно повышайте лимит, либо переписывайте разбор на явный стек с обратной укладкой поддеревьев.

Сравнение форматов: компактность и скорость разбора

Ниже размеры для двух деревьев с одинаковым числом узлов, n = 7: полного и вырожденного, где каждый узел имеет только левого потомка.

Формат	Полное дерево, 7 узлов	Вырожденное дерево, 7 узлов	Восстановление	Уникальные значения
BFS с маркерами, хвост обрезан	7	заметно больше, чем узлов	очередь, O(n)	не нужны
BFS с маркерами, все позиции	15	заметно больше, чем узлов	очередь, O(n)	не нужны
preorder с маркерами	15	15	рекурсия или стек, O(n)	не нужны
preorder + inorder	14	14	рекурсия и словарь позиций, O(n)	обязательны

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

По времени все четыре формата дают O(n). Различаются константы и пиковая память. BFS требует очереди шириной до n/2 узлов на полном дереве, preorder с маркерами обходится стеком высотой log₂n для того же дерева и высотой n для цепочки. Пара preorder и inorder дополнительно строит словарь позиций размером n. Запись маркеров у BFS и preorder даёт одинаковое их количество, а вот порядок обхода может влиять на сжатие: в preorder соседние значения чаще лежат в одном поддереве, что в ряде случаев улучшает сжатие общих префиксов ключей, однако это зависит от данных и алгоритма сжатия и требует отдельного замера.

Если массив уходит в файл или колонку БД, к формату добавляется вопрос упаковки: JSON, BLOB, MessagePack и Protobuf дают разный размер и разную скорость десериализации. Цифры и сценарии собраны в статье сравнение JSON, BLOB и бинарных форматов хранения.

Ориентиры для выбора:

Обмен с внешним API, учебные задачи, дампы в стиле LeetCode: BFS с маркерами и обрезанным хвостом.
Передача по сети узкого канала, разреженные и глубокие деревья: preorder с маркерами.
BST и структуры на его основе: один preorder, потому что inorder восстанавливается сортировкой.
Деревья с дубликатами значений: только форматы с маркерами.
Большие объёмы и бинарная упаковка: preorder с маркерами плюс MessagePack или Protobuf, где вместо строк используется varint.

Практические рекомендации и типичные ошибки

Ошибки, которые чаще всего ломают восстановление:

Маркер совпадает с легальным значением. Ноль как маркер для дерева с нулевыми весами делает структуру неоднозначной. Берите значение вне диапазона данных или храните отдельный битовый флаг «узел существует».
Хвостовые маркеры не обрезаны. На полном дереве массив вырастает примерно вдвое, и это удваивает трафик при передаче.
Рекурсивный разбор падает на глубоком дереве. Вырожденная цепочка большой высоты даёт RecursionError при стандартном лимите рекурсии.
Пустое дерево не обработано отдельно. Массивы [] и [null] должны давать одинаковый результат None, проверьте оба входа.
Для preorder и inorder подставлены массивы от разных деревьев. Контроль: равные длины и равные мультимножества значений.
В preorder-записи с маркерами не проверено соотношение маркеров и узлов: маркеров должно быть ровно n + 1.

Чек-лист перед тем, как формат уйдёт в прод:

Определите тип дерева: бинарное, N-арное, BST.
Посчитайте высоту и ширину на реальных данных, а не на тестовом наборе из десяти узлов.
Выберите формат по таблице выше и зафиксируйте значение маркера.
Покройте тестами пустое дерево, один узел, цепочку, полное дерево и дерево с повторяющимися значениями.
Замерьте размер массива и время разбора на данных, близких к продакшену.
Задокументируйте формат и его версию: смена схемы на живых данных дороже, чем выбрать её сразу.

Для дискового хранения добавьте проверку порядка байтов и выравнивания, если пишете не текст, а бинарный буфер: перенос файла между little-endian и big-endian платформами без явного указания порядка портит числа. Разбор этих деталей, включая ограничения файловых систем, есть в материале сериализация и персистентность массивов на диске.

N-арные деревья кодируются теми же идеями с одной поправкой. Вместо двух потомков храните счётчик детей перед их списком: пары (значение, число детей) в preorder. Корень 1 с детьми 2 и 3, где у узла 2 есть ребёнок 4, даёт [1,2, 2,1, 4,0, 3,0]: читаем пару, создаём узел и берём ровно столько следующих элементов как его детей. Валидация сводится к проверке, что суммарное число объявленных детей совпадает с числом оставшихся элементов. Уровневый обход N-арного дерева как отдельная задача разобран в примере N-ary Tree Level Order Traversal.

Начните с замеров: посчитайте высоту и ширину своего дерева, прогоните оба формата на копии боевых данных и сравните размер массива с временем разбора. Если дерево полное и неглубокое, берите BFS с обрезанным хвостом; если встречаются длинные цепочки или много пустых ветвей, берите preorder с маркерами. Решение фиксируйте до деплоя, а не после.