How can tree be serialized and deserialized?
Solution 1: If we
can serialize/deserialize a generic OM, then the tree can also be
handled by that approach. This can be done by making use of own
memory manager which allocates memory planes such that all objects
pointed to from an object fall in the same memory plane.
If
that is true, then it means that all objects in the same plane are at
some offset from the beginning of the memory plane. During
serialization, one can make one pass through all the objects in one
memory plane and convert their pointers to offsets by subtracting the
memory plane starting pointer from them.
Then
we write out the entire memory plane into the file.
When
we reload the memory plane, we add the starting of the memory plane
to each pointer (which was restored as an offset rather than a
pointer) to get the correct pointer.
If
the objects were not in one plane, then for serialization, one cannot
subtract the lowest pointer among them from all pointers because that
offset will not be the same on restoration (since objects are not in
one plane, we will not be restoring them together, so they will
occupy different memory positions such that the offsets from the
lowest pointer will not be the same as they were before
serialization).
Solution
2: An
approach specific to trees is that you write out both the preorder
and inorder traversal of the tree and then reconstruct the tree by
reading both these orders.
Solution
3: If we
have a special marker for null child, then preorder or levelorder
traversal can be used to serialize a tree and it can be easily
deserialized in O(n). The special null markers help to terminate the
branches and leave no room for ambihuity when constructing the tree.
The same is not possible in postorder or levelorder traversals
because there children are printed first.
Solution
4: Can you
restore the tree by storing level of each node along with inorder
traversal of the tree? Just inorder traversal is not sufficient
because given an incomplete tree, next node can be added anywhere
(even if we have to add it in inorder fashion). So if level is
fixed, then can we restore the tree completely?
(De)Serialization with a special marker for no children
If we write a special marker to indicate end of children for every node, then it is very easy to serialize and deserialize a tree.
It can in fact be extended to an nary tree as well.
Example: For the above tree, we can write it as: ABD$E$$C$ which would imply grouping like this:
ABD$E$$C$$
The following code can be used to serialize and deserialize.
void serialize(TreeNode root)
{
if (root == null) return;
writeToFile (root.data);
if (root.children != null)
{
for (TreeNode child: root.children)
serialize(child);
}
writeToFile (MARKER);
}
TreeNode deSerialize()
{
char val = readFromFile();
if ( val == MARKER )
return null;
TreeNode root = new TreeNode(val);
while (true)
{
TreeNode child = deSerialize();
if (child == null)
break;
root.children.add(child);
}
return root;
}
We can also write the number of children before writing any children of a node.
This will obviate the need to write MARKER.
