aspose file tools*
The moose likes Java in General and the fly likes Tree Structure  Implementation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Tree Structure  Implementation" Watch "Tree Structure  Implementation" New topic
Author

Tree Structure Implementation

Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

Hi Ranchers,
How should i implement a Tree Structure in Java Based application.?Any Links that you have come across if can be shared will be appreciated ?How would i map the entries to the database table?how many tables will i require for this implementation.

Regards
Deepak


When The Going Gets Tougher,The Tougher gets Going
Wouter Oet
Saloon Keeper

Joined: Oct 25, 2008
Posts: 2700

What have you tried so far? What didn't work? Smells a little of homework.


"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler
Please correct my English.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19696
    
  20

If you need code for the tree structure itself you can check out DefaultMutableTreeNode.

As for the tables, you will need just one. It needs one column with the key to the parent node. This key will be null for the root node(s).

If I have such a table and need to convert it into a tree I usually loop twice:
- loop 1 (over the records) will create a node record for each record. Because the parent record may not be created yet I store it.
- loop 2 (over the created nodes) will connect each node with its parent. A Map<KeyType,NodeType> is a useful tool for this.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19696
    
  20

Wouter Oet wrote:Smells a little of homework.

I agree, but the conversion of a flat structure (a table) into a tree structure is not trivial. That's why I provided one technique on how this can be done.
Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

Hi Rob,
Since im new to Tree Implementation,Can we have a sample code for the technique you just have advised.Im not able to proceed,Atleast if you could provide me some help this time,it would be helpful,I know ranch is not a code mill,but im finding it difficult to intially start up with the code for the same,help provided will be appreciated in this regards.

PS: I have asked for code since im not able to start up with this implementation.(technique as suggested by Rob)
Thanks
Deepak
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19696
    
  20

Deepak Lal wrote:Can we have a sample code for the technique you just have advised.

No. ShowSomeEffort already. I haven't seen any form of effort from you in quite a while. I already given you a pseudo-algorithm. All you need to do is translate that into code.

Im not able to proceed,Atleast if you could provide me some help this time,it would be helpful,I know ranch is not a code mill,but im finding it difficult to intially start up with the code for the same,help provided will be appreciated in this regards.

Like I said, the two lines of code I've given you should already be enough to code at least something. You should be able to do at least the following from it:
- loop over the records
- from a record, create a node object (custom class! I call it NodeType here)
- use a Map<KeyType,NodeType) to store the key to object mapping (the record's own key, not the parent key)

- loop over the map
- for each node object get the parent key
- lookup the parent using the key (that's what the map is for)
- set the parent object you just found for the current node object

That's specifying my pseudo-algorithm even further. If you can't translate that into code then I suggest you read some more books on Java before doing anymore programming.>
Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

Hi rob,
Im unable to proceed for below statements.

Assuming records are below




how to proceeed with below steps...Please help


use a Map><KeyType,NodeType> to store the key to object mapping (the record's own key, not the parent key)
- loop over the map
- for each node object get the parent key
- lookup the parent using the key (that's what the map is for)
- set the parent object you just found for the current node object


Im not clear with key to object mapping concept and i had another clarification that whether the solution given will also cater to parent having multiple children.?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Don't forget Rob's first piece of advice:

"If you need code for the tree structure itself you can check out DefaultMutableTreeNode. "

Look up that class (DefaultMutableTreeNode) and figure out how you would use to to set up Parent-Child relationships with your Objects of interest.


Steve
Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

Well Steve,i want to follow robs algorithm since it is easy but im not able to implement it.since im getting confused at Step3 and the next following steps


Steve could you help me out with this.



Wouter Oet
Saloon Keeper

Joined: Oct 25, 2008
Posts: 2700

No we're NotACodeMill. With all he hints and advices you've been given you should at least be able to come up with something that partially works.
Please ShowSomeEffort instead of constantly saying that it's too difficult.
Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

Wouter Oet wrote:No we're NotACodeMill. With all he hints and advices you've been given you should at least be able to come up with something that partially works.
Please ShowSomeEffort instead of constantly saying that it's too difficult.


Wouter,I have tried whateveri could,Im new bie to data structures,hence im asking for help on this topic.I do not know how to implement Rob's approach.i have proceeded till Step 2 as illustrated in one of the posts with code. i do not know for the next steps.



Could you tell me how to proceed now with Rob's approach for below said steps.I will be highly obliged if you could render help.


Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18570
    
    8

Deepak Lal wrote:Could you tell me how to proceed now with Rob's approach for below said steps.I will be highly obliged if you could render help.




Sure. You should proceed by writing code to do that. Or if you don't understand what code to write, you should ask a specific question.
Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

The second example helped me to achieve the Tree Implementation

http://www.javabeat.net/tutorials/94-composite-pattern-structural-patterns.html

Please correct me if my understanding is wrong.
Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

Rob ,
Could you throw some light on your algorithm,since i wanted to implement in the way you specified but still im unable to do so.I saw composite design pattern which explained me the concepts.Atleast for this one if you could help me out ,it would be great.
D. Ogranos
Ranch Hand

Joined: Feb 02, 2009
Posts: 214
The (perhaps confusing) point of Rob's algorithm is that the NodeType object is a tree node. This means, it should offer methods to set a parent entry and child entries.

So you loop through the map. Each NodeType there has a parent key. Use the map to find the NodeType object that corresponds to that key...thats the parent object! So, now you have a parent object, and a child object. Use the appropriate methods to set the relations between these two! Then continue with the next object from the map. When you're done, the tree structure has been re-built from the database.

Hope this helps.
 
wood burning stoves
 
subject: Tree Structure Implementation