loading binary tree from string (parent-left-right)

Question

I have a binary tree that looks like this

enter image description here

the object that represents it looks like this (java)

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

I want to read the data and build the tree from a string.
So I wrote some small 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 have it as a list - objects in this order O,A,C,D,E,F,B

And now my question is - how to I build the tree?
iterating and putting it on a stack, queue ?
should I serialize on a different order ?

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

MvG · Accepted Answer · 2012-07-21 23:44:44Z

Given your second string representation, there is no way to retrieve the original tree. So unless any tree with that sequence is acceptable, you'll have to include mor information in your string. One possible way would be representing null references in some fashion. Another would be using parentheses or similar.

Given your first representation, restoring the data is still possible. One algorithm expliting the level information would be the following:

Maintain a reference x to the current position in your tree
For every node n you want to add, move that reference x up in your tree as long as the level of x is no less than the level of n
Check that now the level of x is exactly one less than the level of n
Make x the parent of n, and n the next child of x
Move x to now point at n

This works if you have parent links in your nodes. If you don't, then you can maintain a list of the most recent node for every level. x would then correspond to the last element of that list, and moving x up the tree would mean removing the last element from the list. The level of x would be the length of the list.

Community · Accepted Answer · 2017-05-23 11:53:33Z

0

Your serialization is not well explained, especially regarding how you represent missing nodes. There are several ways, such as representing the tree structure with ()s or by using the binary tree in an array technique. Both of these can be serialized easily. Take a look at Efficient Array Storage for Binary Tree for further explanations.

edited May 23, 2017 at 11:53

CommunityBot

11 silver badge

answered Jul 21, 2012 at 23:59

walrii

3,5322 gold badges33 silver badges47 bronze badges

Collectives™ on Stack Overflow

loading binary tree from string (parent-left-right)

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related