Сериализация заключается в сохранении дерева в файле, чтобы впоследствии его можно было восстановить. Структура дерева должна быть сохранена. Десериализация читает дерево обратно из файла.
Ниже приведены несколько более простых версий проблемы:
Если данное дерево является бинарным деревом поиска?
Если данное Бинарное дерево является Бинарным деревом поиска, мы можем сохранить его, сохранив предварительный заказ или обратный порядок. В случае деревьев бинарного поиска для предварительного просмотра структуры достаточно только обхода по предзаказу или после заказа .
Если данное Бинарное Дерево — Полное Дерево?
Двоичное дерево завершено, если все уровни полностью заполнены, за исключением, возможно, последнего уровня, и все узлы последнего уровня находятся как можно левее (двоичные кучи являются полным двоичным деревом). Для полного двоичного дерева обход уровня порядка достаточен для хранения дерева. Мы знаем, что первый узел является корневым, следующие два узла являются узлами следующего уровня, следующие четыре узла являются узлами 2-го уровня и так далее.
Если данное Бинарное Дерево — Полное Дерево?
Полный двоичный файл — это двоичное дерево, в котором каждый узел имеет 0 или 2 дочерних элемента. Такие деревья легко сериализовать, так как у каждого внутреннего узла есть 2 дочерних элемента. Мы можем просто сохранить обход предварительного заказа и сохранить бит для каждого узла, чтобы указать, является ли этот узел внутренним узлом или конечным узлом.
Как хранить общее бинарное дерево?
Простое решение — хранить как обходы Inorder, так и Preorder. Для этого решения требуется пространство, в два раза превышающее размер двоичного дерева.
Мы можем сэкономить место, сохранив обход Preorder и маркер для указателей NULL.
Let the marker for NULL pointers be '-1' Input: 12 / 13 Output: 12 13 -1 -1 -1 Input: 20 / \ 8 22 Output: 20 8 -1 -1 22 -1 -1 Input: 20 / 8 / \ 4 12 / \ 10 14 Output: 20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 -1 Input: 20 / 8 / 10 / 5 Output: 20 8 10 5 -1 -1 -1 -1 -1 Input: 20 \ 8 \ 10 \ 5 Output: 20 -1 8 -1 10 -1 5 -1 -1
Десериализация может быть сделана простым чтением данных из файла по одному.
Ниже приводится реализация вышеуказанной идеи на C ++.
|
Выход:
Inorder Traversal of the tree constructed from file: 4 8 10 12 14 20 22
Сколько дополнительного места требуется в вышеуказанном решении?
Если имеется n ключей, то для вышеприведенного решения требуются маркеры n + 1, что может быть лучше простого решения (двойное хранение ключей) в ситуациях, когда ключи большие или ключи имеют большие элементы данных, связанные с ними.
Можем ли мы оптимизировать это дальше?
Вышеуказанное решение может быть оптимизировано многими способами. Если мы поближе рассмотрим выше сериализованные деревья, мы можем заметить, что для всех листовых узлов требуются два маркера. Одна простая оптимизация заключается в сохранении отдельного бита для каждого узла, чтобы указать, что узел является внутренним или внешним. Таким образом, нам не нужно хранить два маркера с каждым узлом листа, так как листья могут быть идентифицированы дополнительным битом. Нам все еще нужен маркер для внутренних узлов с одним потомком. Например, на следующей диаграмме «используется для указания внутреннего бита набора узлов, а« / »используется в качестве маркера NULL. Диаграмма взята отсюда .

Обратите внимание, что в двоичном дереве всегда больше конечных узлов, чем внутренних узлов (количество конечных узлов равно числу внутренних узлов плюс 1, поэтому такая оптимизация имеет смысл.
Как сериализовать n-арное дерево?
В n-арном дереве нет обозначенного левого или правого потомка. Мы можем хранить маркер «конец детей» с каждым узлом. Следующая диаграмма показывает сериализацию, где ')' используется как маркер конца дочернего элемента. Скоро мы рассмотрим реализацию n-арного дерева. Диаграмма взята отсюда .

Ссылки:
http://www.cs.usfca.edu/~brooks/S04classes/cs245/lectures/lecture11.pdf
Эта статья предоставлена Шивамом Гуптой. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Сериализация и десериализация N-арного дерева
- Сложность различных операций в двоичном дереве, двоичном дереве поиска и дереве AVL
- Минимальный своп, необходимый для преобразования двоичного дерева в двоичное дерево поиска
- Проверьте, является ли двоичное дерево полным двоичным деревом или нет | Итеративный подход
- Преобразовать двоичное дерево в двоичное дерево с резьбой | Установите 1 (используя очередь)
- Преобразовать двоичное дерево в двоичное дерево с резьбой | Набор 2 (Эффективный)
- Проверить, является ли двоичное дерево поддеревом другого двоичного дерева | Набор 2
- Разница между двоичным деревом и двоичным деревом поиска
- Преобразование двоичного дерева в двоичное дерево поиска с использованием набора STL
- Проверьте, является ли данное двоичное дерево перекошенным двоичным деревом или нет?
- Преобразование двоичного дерева в двоичное дерево поиска
- Проверить, является ли двоичное дерево поддеревом другого двоичного дерева | Комплект 1
- Проверьте, является ли двоичное дерево полным двоичным деревом или нет
- Распечатать уровни двоичного дерева в отсортированном порядке | Набор 3 (дерево задано как массив)
- Преобразовать произвольное двоичное дерево в дерево, которое содержит свойство Children Sum
0.00 (0%) 0 votes