Trees in Java

[Shruthi Babu]

I have a constructed a hash map with the following value .

The values of the hash map is another hash map

A - { B , C}
B - {D}
C - {D}
D - {E,F}

My output should be something like

A - B - D - E
A - B - D - F
A- C - D - E
A - C - D- F

What is the best way to find a solution to resolve this.
Any help in this regard is highly appreciated

[marc weber]

Can you explain in words (not Java) the process you want to follow? If you can do this, it should make the coding easier.

[Shruthi Babu]

Basicall I need to traverse the hash map to get the output I mentioned . I tried using recursive function but I am not able to get any solution.

Any help in this regard is really of great help

[Rob Spoor]

It would probably be something like this (I'm using Set here because it seems more appropriate):

public TreeNode createNode(Object value, Map<Object,Set<Object>> map)
{
    DefaultMutableTreeNode node = new DefaultMutableTreeNode(value);
    Set<Object> set = map.get(value);
    if (set != null)
    {
        for (Object o: set)
        {
            node.add(createNode(o, map));
        }
    }
    return node;
}

[Shruthi Babu]

Thanks for the input . I see TreeNode is in swings. Can I use this approach for plain java code?

[Shruthi Babu]

I am also using Java 1.4.2 will this still work?

[Rob Spoor]

Originally posted by Div Bala:
Thanks for the input . I see TreeNode is in swings. Can I use this approach for plain java code?

Sure you can. Although TreeNode is in the javax.swing.tree package, you can use it anywhere. It's still a tree, and you can traverse it using the children() enumeration and getParent().

Originally posted by Div Bala:
I am also using Java 1.4.2 will this still work?

Sure, you just need to remove the generics and do some casting instead, and use an iterator to iterate through the set:

public TreeNode createNode(Object value, Map map)
{
    DefaultMutableTreeNode node = new DefaultMutableTreeNode(value);
    Set set = (Set)map.get(value);
    if (set != null)
    {
        for (Iterator i = set.iterator(); i.hasNext(); )
        for (Object o: set)
        {
            Object o = i.next();
            // actually, my first code had a bug.
            // add() expects a MutableTreeNode, not TreeNode.
            // therefore, cast it
            node.add((DefaultMutableTreeNode)createNode(o, map));
        }
    }
    return node;
}

[Shruthi Babu]

Thanks for the help.

I am having difficulty in understanding the logic say for example

I have something like
A - B,C
B - E
C- E

How will the tree maintain all the possible combinations as A - B - E
A-C- E ?

Sorry to bother you with questions.

[Rob Spoor]

Originally posted by Div Bala:
Thanks for the help.

I am having difficulty in understanding the logic say for example

I have something like
A - B,C
B - E
C- E

How will the tree maintain all the possible combinations as A - B - E
A-C- E ?

Sorry to bother you with questions.

You start the tree with object A; this will be the root node.
A will have two children: B and C. Each of these has one child, E. So the tree will look like this:

A - B - E
 \- C - E

If you now traverse the tree, storing the entire path, you will get both A-B-E and A-C-E.

[Shruthi Babu]

Ok got it. Thanks.

Can you help me with the traversal part? Again should I write a recursive function?

What if there are two root nodes say like

A - C , D
B - C , D

Thanks
Rohini

[Rob Spoor]

Originally posted by Div Bala:
Can you help me with the traversal part? Again should I write a recursive function?

Yes you should.

public void collectPaths(TreeNode node, List path)
{
    path.add(node);
    if (node.getChildCount() == 0)
    {
        // this is a leaf node
        System.out.println(path);
        // or do something else
    }
    else
    {
        for (Enumeration e = node.children(); e.hasMoreElements(); )
        {
            TreeNode child = (TreeNode)e.nextElement();
            // create a copy of the list
            List newPath = new ArrayList(path);
            collectPaths(child, newPath);
        }
    }
}

Initially path is an empty list when you call it with the root node.

What if there are two root nodes say like

A - C , D
B - C , D

Then you have to call the method(s) for both nodes.

All recursive tree operations have two assumptions:
1) there is one root
2) there are no cycles


1 because you always start at the root, and 2 because cycles could (will) cause your code to run forever - until you get either a StackOverFlowError or an OutOfMemoryError.

[Shruthi Babu]

Thank you very much for all your help.

[Tom Bigbee]

I'm with Rob on the Two or more Root Node thing

There is always one Root Node in a Tree, sometimes Users (abusers) try to make you implement a solution where one tree consists of many trees (for whatever reason), in that instance you can have a list of lists, where a list contains a list of One Root Node Trees. Anyway if you don't want to use Swing it easy enough to write your one Tree Solution, just remember you will have to write classes on top to implement you rules

    
public class TreeNode {
 
private static int nodeId = 0;
private int Id;
private TreeNode parentNode;
private int nodeLevel;

public TreeNode(TreeNode parentNode) {
this.parentNode = parentNode;
if(this.parentNode == null) {
this.nodeLevel = 1;
} else {
this.nodeLevel = this.getParentNodeLevel() + 1;
}
setId();
}

synchronized private void setId() {
Id = ++nodeId;
}

public int getId() {
return this.Id;
}

public TreeNode getParentNode () {
return parentNode;
}

public int getParentNodeLevel() {
if (parentNode == null) {
return 0;
} else {
return parentNode.getNodeLevel();
}
}

public int getNodeLevel() {
return nodeLevel;
}

public int hashCode() {
return Id;
}
 
public boolean equals(Object o) {
boolean isEqual = false;

if(!(o instanceof TreeNode)) {
return isEqual;
}

TreeNode treeNode = (TreeNode)o;
if(treeNode.parentNode == this.parentNode 
&& treeNode.Id == this.Id) {
isEqual = true;
}
return isEqual;
}
}