• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Form a tree parent -childs from String

 
Srikkanth Mohanasundaram
Ranch Hand
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Think of trie algoritm.
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What code do you have so far?
 
Srikkanth Mohanasundaram
Ranch Hand
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would think that recursively descending the tree to find the appropriate parent would be a good first step.
 
Srikkanth Mohanasundaram
Ranch Hand
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Only if he's doing it wrong.
 
Srikkanth Mohanasundaram
Ranch Hand
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes you are right.
 
Rahul P Kumar
Ranch Hand
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
why can't you try a nested hashmap datastructure, as I earlier mentioned.
 
Srikkanth Mohanasundaram
Ranch Hand
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 243
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic