• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Trees in Java

 
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Harry Singh
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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...
 
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Aadi Narayana Reddy
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Any help on this guys!!!
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Harry Singh
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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...
 
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic