Advanced: Populating, Printing Tree Structure

[Steve Johnson]

Been banging my head on this for two days now. Hope someone can help!

My test program below is in the form of a single JSP, with a Node class
build in. (All the coded needed to run is below.)


The technical requirements:

1) Store tree data in the database so that it can be
extracted as a tree structure. For test purposes,
I'm mimicking this table structure in the code
with a Vector of HashMaps (where each HashMap represents
one row from the java.sql.resultSet).

The tree data is returned from the resultSet as follows:

ID PARENT_ID DESC
---------------------------------------
10 null Node A
100 10 Leaf A1
101 10 Leaf A2
102 10 Leaf A3

20 null Node B

30 null Node C
300 30 Leaf C
301 30 Leaf C1



2) Using the above resultSet format, draw the tree contents to web
browser (NOT using applets or swing, just as a string of HTML).

The tree structure string will look as follows, supporting 'n'
levels deep:


Node A
Leaf A1
Leaf A2
Node A1
Leaf A1a
Leaf A3

Node B

Node C
Leaf C1
Leaf C2






Below is the mostly-working (?) code. I believe the tree is populated
correctly using recursion, but it could very well be screwed up. It's
difficult to tell because I've been unable to traverse the populated tree
structure and print its contents.

Can someone take a look at this and see if 1) the tree is populated
correctly, and 2) help me to correctly print the formatted tree (as shown
above, nothing fancy).

Any design improvements are also welcome! I believe some or all of the
member variables can be eliminated.

The method setNodeList() populates the tree strucure, and printTree() is
then supposed to print the contents of the tree.

Thanks a bunch if you can help out, this is driving me nuts!





BEGIN JSP CONTENT

<%!
ArrayList rootList = new ArrayList();

public Node findNode( Integer nodeID, ArrayList nodeList )
{
for( int j = 0; j < nodeList.size(); j++ )
{
Node node = (Node)nodeList.get(j);
HashMap dataRow = (HashMap)node.getObject();
Integer currID = (Integer)dataRow.get("ID");

if( nodeID.equals(currID) )
{
return node;
}

findNode( nodeID, node.getChildList() );
}

return null; //couldn't find node
}


public void setNode( HashMap dataRow )
{
Node node = new Node(dataRow);
Integer parentID = (Integer)dataRow.get( "PARENT_ID" );

Node parentNode = findNode( parentID, rootList );

if( parentNode != null )
{
parentNode.addChild(node);
}
else
{
rootList.add(node);
}
}

public void setNodeList( Vector dataRowList )
{
for( int j = 0; j < dataRowList.size(); j++ )
{
HashMap dataRow = (HashMap)dataRowList.elementAt(j);
setNode( dataRow );
}
}


void printTree( Node node, int indentation )
{
for( int i=0; i<3*indentation; i++ )
System.out.print(" ");

ArrayList childNodeList = node.getChildList();
for( int j = 0; j < childNodeList.size(); j++ )
{
Node tempNode = (Node)childNodeList.get(j);

HashMap dataRow = (HashMap)tempNode.getObject();
String desc = (String)dataRow.get("DESC");

System.out.println( desc );

preorderDisplay( tempNode, ++indentation );
}
}





/*
* Sample java.sql.resultSet format:
*
* ID PARENT_ID DESC
* ---------------------------------------
* 10 null Node A
* 100 10 Leaf A1
* 101 10 Leaf A2
* 102 10 Leaf A3
*
* 20 null Node B
*
* 30 null Node C
* 300 30 Leaf C1
* 301 30 Leaf C2
*
*/
private Vector getTestDataRowList()
{
HashMap row1=getRow(new Integer(10), new Integer(-1), "Node A");
HashMap row2=getRow(new Integer(100), new Integer(10), "Leaf A1");
HashMap row3=getRow(new Integer(101), new Integer(10), "Leaf A2");
HashMap row4=getRow(new Integer(102), new Integer(10), "Leaf A3");

HashMap row5=getRow(new Integer(20), new Integer(-1), "Node B");

HashMap row6=getRow(new Integer(30), new Integer(-1), "Node C");
HashMap row7=getRow(new Integer(300), new Integer(30), "Leaf C1");
HashMap row8=getRow(new Integer(301), new Integer(30), "Leaf C2");

Vector dataRowList = new Vector();

dataRowList.add(row1);
dataRowList.add(row2);
dataRowList.add(row3);
dataRowList.add(row4);
dataRowList.add(row5);
dataRowList.add(row6);
dataRowList.add(row7);
dataRowList.add(row8);

return dataRowList;
}
private HashMap getRow( Integer id, Integer parID, String desc )
{
HashMap dataRow = new HashMap();
dataRow.put( "ID", id );
dataRow.put( "PARENT_ID", parID );
dataRow.put( "DESC", desc );
return dataRow;
}

%>




<PRE>
<%

System.out.println( "\n\n\n" );

Vector dataRowList = getTestDataRowList();

setNodeList( dataRowList );

for( int j = 0; j < rootList.size(); j++ )
{
Node node = (Node)rootList.get(j);
printTree( node, 0 );
}


System.out.println( "\n\n\n" );

%>
TEST
</PRE>



<%!

private class Node
{
private Object obj = null;
private ArrayList childList = new ArrayList();

public Node( Object obj )
{
this.obj = obj;
}

public Object getObject()
{
return this.obj;
}

public void addChild( Node node )
{
this.childList.add(node);
}
public ArrayList getChildList()
{
return this.childList;
}
}

%>

END JSP CONTENT

 

[Barry White]

Hi Steve,

have you looked at the javax.swing.tree package. I know it's not a swing
application but the tree model framework is already in place, no need to
reinvent the wheel.

DefaultTreeModel
DefaultMutableTreeNode

Build up the tree from the database resultset. This might be worth
looking at.

From a general design point of view you could make better use of the
Collections framework:

YOUR CODE:

public Node findNode( Integer nodeID, ArrayList nodeList )
{
for( int j = 0; j < nodeList.size(); j++ )
{
Node node = (Node)nodeList.get(j);
HashMap dataRow = (HashMap)node.getObject();
Integer currID = (Integer)dataRow.get("ID");

if( nodeID.equals(currID) )
{
return node;
}

findNode( nodeID, node.getChildList() );
}

return null; //couldn't find node
}

SUGGESTION:

public Node findNode( Integer nodeID, Collection nodeList )
{
Iterator iter = nodeList.iterator();
while (iter.hasNext())
{
Node node = (Node)iter.next();
Map dataRow = (Map)node.getObject();
Integer currID = (Integer)dataRow.get("ID");

if( nodeID.equals(currID) )
{
return node;
}

findNode( nodeID, node.getChildList() );
}

return null; //couldn't find node
}


This allows you to change the implementation (ArrayList -> LinkedList,
HashMap -> TreeMap) without having to change the rest of your code.

Good Luck,
Barry

 

[Steve Johnson]

Hi Steve,

have you looked at the javax.swing.tree package. I know it's not a
swing application but the tree model framework is already in place, no
need to reinvent the wheel.

DefaultTreeModel
DefaultMutableTreeNode

Yes, I have looked into those APIs, but still couldn't figure out how to
use them to any advantage with a recursive algorithm. If you have an
example of using those APIs for my scenario, that would be great.

From a general design point of view you could make better use of the
Collections framework:
[snip]

SUGGESTION:

public Node findNode( Integer nodeID, Collection nodeList )
{
Iterator iter = nodeList.iterator();
while (iter.hasNext())
{
Node node = (Node)iter.next();
Map dataRow = (Map)node.getObject();
Integer currID = (Integer)dataRow.get("ID");

if( nodeID.equals(currID) )
{
return node;
}

findNode( nodeID, node.getChildList() );
}

return null; //couldn't find node
}

Thanks, this sounds like a good idea.


The primary obstacle is still populating and printing that tree, and I'm
completely stuck.

 

[Barry White]

Hi again,

perhaps have your node extend DefaultMutableTreeNode() and build up a
DefaultTreeModel from the nodes. You could use a HashMap to map ID's to
nodes so you can find a parent node when you need to add a new child.

Look at:
http://java.sun.com/docs/books/tutorial/uiswing/components/tree.html#data

You coult test your code with a Swing JTree too

Barry

Hi Steve,

have you looked at the javax.swing.tree package. I know it's not a
swing application but the tree model framework is already in place, no
need to reinvent the wheel.

DefaultTreeModel
DefaultMutableTreeNode

Yes, I have looked into those APIs, but still couldn't figure out how to
use them to any advantage with a recursive algorithm. If you have an
example of using those APIs for my scenario, that would be great.

From a general design point of view you could make better use of the
Collections framework:

[snip]


SUGGESTION:

public Node findNode( Integer nodeID, Collection nodeList )
{
Iterator iter = nodeList.iterator();
while (iter.hasNext())
{
Node node = (Node)iter.next();
Map dataRow = (Map)node.getObject();
Integer currID = (Integer)dataRow.get("ID");

if( nodeID.equals(currID) )
{
return node;
}

findNode( nodeID, node.getChildList() );
}

return null; //couldn't find node
}

Thanks, this sounds like a good idea.


The primary obstacle is still populating and printing that tree, and I'm
completely stuck.