Один из методов, который мне нравится, заключается в том, чтобы сохранить обход предзаказа, но также включить туда нуль-узлы. Хранение нулевых узлов устраняет необходимость также хранить порядок дерева.
Некоторые преимущества этого метода
- В большинстве практических случаев хранение лучше, чем метод pre / post + inorder.
- Сериализация занимает всего один обход
- Десериализацию можно выполнить за один проход.
- Обход по порядку можно получить за один проход, не создавая дерево, что может быть полезно, если ситуация требует его.
Например, скажем, у вас есть двоичное дерево из 64-битных целых чисел, вы можете хранить дополнительный бит после каждого узла, говоря, является ли следующий узел нулевым или нет (первый узел всегда является корнем). Нулевые узлы можно представлять одним битом.
Таким образом, если имеется n узлов, использование пространства будет равно 8n байтов + n-1 битов индикатора + n + 1 битов для нулевых узлов = 66 * n битов.
В порядке до / после + вы в конечном итоге будете использовать 16n байт = 128 * n бит.
Таким образом, вы экономите пространство 62 * n бит по сравнению с этим методом pre / post + inorder.
Рассмотрим дерево
100
/ \
/ \
/ \
10 200
/ \ / \
. . 150 300
/ \ / \
. . . .
где '.' являются нулевыми узлами.
Вы будете сериализовать его как 100 10 . . 200 150 . . 300 . .
Теперь каждое (включая поддерево) «обход предзаказа с нулем» обладает свойством, что число нулевых узлов = количество узлов + 1.
Это позволяет вам создать дерево, учитывая сериализованную версию за один проход, так как первый узел является корнем дерева. Следующие узлы - это левое поддерево, за которым следует правое, которое можно посмотреть так:
100 (10 . .) (200 (150 . .) (300 . .))
Для создания обхода inorder вы используете стек и толкаете, когда видите узел, и выдвигаете (в список), когда видите нулевое значение. Результирующий список представляет собой обход по порядку (подробное объяснение этому можно найти здесь: C ++ / C / Java: Анаграммы - от исходной строки до цели; ).