It's not a secret anymore!*
The moose likes Beginning Java and the fly likes Form a tree parent -childs from String Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Form a tree parent -childs from String" Watch "Form a tree parent -childs from String" New topic
Author

Form a tree parent -childs from String

Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
Hello all,

I have a list of strings which is sorted and looks something like this

Test>
Test>A
Test>A>B
Test>A>D
Test>A>D>E
Test>C

Test1>
Test1>X
Test1>Y

I need to create a tree structure which would help me to loop through the values easily. I though of creating a bean which contains the parent name and list of children.But i am stuck on how to populate the bean and on how to retrieve the values if i am going to have a list of beans.

Thanks,
Srikkanth
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
Think of trie algoritm.
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

What code do you have so far?
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
This is the tree model which i have in mind.



I'm really stuck on looping through the string and populating the model.




David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

I would think that recursively descending the tree to find the appropriate parent would be a good first step.
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
David Newton wrote:I would think that recursively descending the tree to find the appropriate parent would be a good first step.


Thanks David.I'll try and let you know
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
Adding everything from root to last leaf in the list will soon start getting big. with each new number of new leaf or stem. This way you are storing things repeatedly
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
Rahul.p Kumar wrote:Adding everything from root to last leaf in the list will soon start getting big. with each new number of new leaf or stem. This way you are storing things repeatedly


Sorry I don't get you.I'm not trying to store the values repeatedly. I'm trying to create a tree of the TestModel objects

Thanks,
Srikkanth
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
when you say
# li.add("Test>A");
# li.add("Test>A>B");
# li.add("Test>A>D");
# li.add("Test>A>D>E");
# li.add("Test>C");
# li.add("Test1>");
# li.add("Test1>X");
# li.add("Test1>Y");


aren't you storing Test as many times, then A 4 times and so on....
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

Only if he's doing it wrong.
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
No that is the list of strings which is the input for me to create the Tree.
Hope i'm making myself clear.

Thanks,
Srikkanth
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
so first time Test comes, you store, next time Test>A comes, you store both Test and A in original format, isn't it?
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
Yes you are right.
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
why can't you try a nested hashmap datastructure, as I earlier mentioned.
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
Hello Rahul,
I cannot use a HashMap i guess.I feel the data structure i have will do the job, but I'm having problems building the tree with list of Strings stuck on adding the children recursively.

Thanks,
Srikkanth
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

What you have will work just fine (although I'd also use a map--but that's more a matter of preference).

Where are you stuck? What have you tried so far?
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
while adding childNode, you are checking contains(), which uses equals(), so make sure you have overridden equals() and hence hashcode() as well
Rahul P Kumar
Ranch Hand

Joined: Sep 26, 2009
Posts: 188
you want to do probably like this:
at top "tree" is there. it has then a list of objects Test and Test1. Each of which has further List of objects, say Test has list of objects A and B. So nexst time an input like Test>A>C comes, first enquire list of "tree" at top. If it has Test, then further enquire in same fashion, as soon as it says it does not have that element, from there on start adding the elements.
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185


What I'm trying to do is to create a TestModel for each String in the list and then find the parent so that it can be added to the child nodes.But for some reason it is always adding to the root node.

David and Rahul,
Thanks for all your time

P.S If i get the the findParent method working, I guess it will work fine.What do you think?

Thanks,
Srikkanth
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
Here is an update to the same code findParent method



So, now have the tree created but only for two levels.

Leaf D is attached to node B,when in fact it should have gone into A.

Thanks,
Srikkanth

David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

Recursion is often tricky--I usually recommend "playing computer": trace out the algorithm manually, with a paper and pencil, in order to figure stuff like this out.
Srikkanth Mohanasundaram
Ranch Hand

Joined: Feb 07, 2007
Posts: 185
David Newton wrote:Recursion is often tricky--I usually recommend "playing computer": trace out the algorithm manually, with a paper and pencil, in order to figure stuff like this out.


Did exactly that to get the recursion right. Thanks David.Thanks Rahul

Srikkanth
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Form a tree parent -childs from String