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