Loading a binary tree from a string (parent-left-right)

Question

I have a binary tree similar to this

the object that represents it is as follows (java)

public class node { private String value = ""; private TreeNode aChild; private TreeNode bChild; .... } 

I want to read data and build a tree from a string.
So I wrote a little method to serialize it, and I have it like this
(Parent-left-right)
0, null, O @ 1, left, A @ 2, left, C @ 3, left, D @ 4, left, E @ 4, right, F @ 1, right, B @

Then I read it and I got it as a list - objects in this order O, A, C, D, E, F, B

And now my question is: how to build a tree?
repeat and put it on the stack, turn?
should serialize a different order?

(basically I want to learn the best practices for building a tree from string data)
can you refer to the link on this topic?

Answer 1

Given your second string representation, there is no way to get the source tree. Therefore, if any tree with this sequence is acceptable, you will need to include mor information in your line. One possible way would be to represent null links in some way. Another will use parentheses or similar.

Given your first view, data recovery is still possible. One algorithm that reveals level information is as follows:

• Maintain link x current position in the tree
• For each node n you want to add, move this link x up into your tree until the level x is not less than level n
• Make sure that now level x is exactly one less than level n
• Make x the parent of n and n the next child of x
• Move x to point n now

This works if you have parent links in your sites. If you do not, you can keep a list of the most recent node for each level. x will correspond to the last element of this list, and moving x up the tree means removing the last element from the list. Level x will be the length of the list.

Answer 2

Your serialization is poorly explained, especially with regard to how you represent the missing nodes. There are several ways, for example, representing a tree structure using () s or using a binary tree in an array method. Both can be easily serialized. Take a look at Efficient binary tree array storage for further explanations.