File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Trees in Java Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Trees in Java" Watch "Trees in Java" New topic
Author

Trees in Java

Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
Hi Gurus,

Can anyone let me know how can i construct a basic tree in java.. All i am looking for is to create a Tree(not a binary tree) and then traverse through that tree to find maximum weights of the tree paths.. but i cant figure out what wil be the structure of the Tree class (as java doesnt have pointers, so hwo to keep track of nodes)

Thanks in Advance,
Harry
Aadi Narayana Reddy
Greenhorn

Joined: Oct 17, 2005
Posts: 13
Hi,

I will provide u some basic knowledge to create nodes. Then u think abt it to create tree.

Just create a class which as 3 members;
those must be of Object type reference variables so that they can hold any type of data,
ex :
class NODE {
Object left;
Object data;
Object right;
}

Create object to this class
NODE ob1, ob2, ob3;
ob1 = new new NODE();
ob1.data = "firstnode"
ob1.left = null;
ob1.right = null;
Here we have one node with data called ob1.
then create two more objects like
ob2 = new NODE();
ob3 = new NODE();
ob2.data = "2";
ob2.left = null;
ob2.right = null;

ob3.data = "3";
ob3.left = null;
ob3.right = null;

and assigh like ob1.left = ob2; ob1.right=ob3;

So here we are having 3 nodes;
ob1, ob2, ob3;
ob1 is the root node, and the left node to this is ob2, right node is ob3;

but when u r implementing it in a program, dont hard code it,, try to write the code in generic format so that we can create no of objects.

aadi


G.Adi Narayana Reddy,
Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
Thanks Aadi for the reply..

But i dont want to create a Binary Tree so i can have any number of children, depending on the input in file... so i dont know how mny children really..

and i cnt cant create nodes like this or in any other generic way as if there are many nodes (like say 5000) it will be stack overflow error...

So any pointers on this...
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Who said that Java doesn't have pointers? This is a common misconception. References in Java are essentially pointers. You just cannot perform pointer arithmetic like you can in C and C++.

I think the example given above is great. Can you come up with your own idea to modify the example so that it allows each tree node to have any number of children? (Hint: check out the Collections API.)

Good luck with your project and let us know if you have any more questions.

Layne


Java API Documentation
The Java Tutorial
Aadi Narayana Reddy
Greenhorn

Joined: Oct 17, 2005
Posts: 13
hi,

can u explain ur problem once,, u told that u r gettting some input file and all. Send it to me clearly so that i try.


aadi
Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
Thanks Layne..

got it what u r saying.. i can use arraylist or vectors for that... but i am kinda confused as if i create a object of that Node class everytime.. then the stacks gonna overflow... i think i am getting something wrong here. well i will try once more..
Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
Thanks Aadi,

This is the kind of input that i have


100
0 -33 1 -45 1 -47 1 21 3 -12 4 5 1 1 5 5 4 -36 8 26 4
-4 6 3 7 -8 0 49 1 -38 7 -33 14 18 13 22 1 -44 3 -36 5 -21 14 25 16 -23 17 -5 24 -45 1 5 7 -12 23 -14 11 30 20 -34 25 48 14 36 6 40 4 36
12 37 34 46 35 -12 22 -7 14 45 10 33 17 -37
36 -20 32 -4 29 27 27 -15 0 -39 37 35 7 -49 14 -24 7 -42 7 13 46 -17 27 -31 22 -30 44 -25 5
-7 15 46 40 38 51 -48 48 -23 30 13 12 23 30 -20 6
49 20 -32 31 -26 34 21 47 -30 7 -42 55 -22
25 -43 56 16 35 -50 3 -1 16 -27 0 -8
8 28 54 -10 31 -8 47 46 35 30 23 -24 40 32 46 42
76 23 37 28 1 12 20 43 63 -19 85 24 9 -39 81 -37 76 4 81 -37 12 14 91 44 38 36 29 -43 62 0

The first line contains an integer n, 1 ≤ n ≤ 500000, indicating the number
of nodes, including the entrance node, implicitly labelled 0.

This is then followed by one or more lines, containing n-1 pairs of integers. All integers are separated by single spaces or newlines. The y�th
intersection is defined by the y�th pair of integers 'x p', where 1 ≤ y < n, 0 ≤ x < y, -1000 ≤ p ≤ 1000. & P is the profit value...


So its kind of weighted graph and then i have to traverse this graph and calculate the max profit...

so for this i tokenize the input.. put it in arraylist and then trying to create a tree from this Arraylist.. and then traverse through that tree to get the results... but im stuck...

So any pointers for this...
Aadi Narayana Reddy
Greenhorn

Joined: Oct 17, 2005
Posts: 13
hi singh,

So there are some integer values, but im not getting what is y? and yth pair of intersection.
what values i need to put in to the graph or tree?
and is it the pair of values or individual values?
i'll try, if u send me the info what i have asked ?


regards,
Aadi Narayana Reddy
Greenhorn

Joined: Oct 17, 2005
Posts: 13
hi singh,

i will tell u one solution, but make sure that whether it suits ur requirement or not ?
Tokenize the input values first using the StrinTokenizer class.
get the first 2 input values, and place it in TreeMap(java.util.class) object. and get the next 2 input values and do the same thing again.
so continue to put the all integer values. u can do it using a loop.

Usually TreeMap stores the (key, value) pairs in ascending order based on the key.
so u can change this behaviour so that the values are stored in treemap basesd on the value. U can do it by writing on comparable class and pass the object of it when u r creating the treemap object.

finally get the last value stored in the treemap, using the methods provided in the TreeMap class.

if u have any doubts u can ask me again.

regards,
Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
Thanks Mate.

but how can i create a tree then.. Can i have your email address, i iwll try & send u the PDF file for this problem.. if thats not a problem to you..

Essentialy a problem is of trees and paths.. so from that integer value i have to create trees and then profit is the value associated with each path of the tree... and i have to calculate the max profit by traversing through the paths (but thats a second part,cnt even complete first part )

and y is nothing but an integer... if u start from 1.. then first pair will be smthing like 0 -1.. where 0 is the parent and -1 is the profit associated with it...
[ October 19, 2005: Message edited by: Ernest Friedman-Hill ]
Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
Any help on this guys!!!
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18760
    
  40

Two possible answers...

One. The difference between a binary tree, and a tree that takes more than two children can just be how you envision it. For example, from the earlier example, you can tweek the node as such:



And create some get() and put() routines that will simulate the operations. Adding a child to the parent can just be done by adding it directly if there are no children, or adding to the end of the sibling route.

Two. Use containers. And maybe connect as such.



The children vector holds children node objects, which in turn, has vectors to its own children.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
Thanks Henry...

so that means for every node in Tree, i will have to create an instance of class Node and add respective data into each instance...or is there a way i can just create a single instance and then add node and data of each node..

Any sample skeleton of the class would be very helpful...
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Or instead of writing your own Node class from scratch, you could use the built-in DefaultMutableTreeNode class. Although it's in the javax.swing.tree package it isn't a GUI component.
Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
yeah, Good idea to use that Tree class of swings. but in my case i want to have profits associated with nodes... so probably better off by making my own Tree class...but kinda stuck with that....
Harry Singh
Ranch Hand

Joined: May 02, 2001
Posts: 124
Well with all of your help, i have made a skeleton of the TreeNode class and i have been able to make a tree(atleast i think so). Im putting up a code here, so if you guys can tell me if i got everything right..

Here is a Tree Node class


& then i am storing everything in Tree Map along with node number and its respective TreeNode object.



where treeData is an Arraylist containing data for making tree...

So can you guys lemme know if my interpretation of things is right... and if yes, then now how can i traverse the tree and get the maximum profit by following a path of the tree...

Thanks in advance
Harry
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Trees in Java