Advanced: Populating, Printing Tree Structure

Discussion in 'Java' started by Steve Johnson, Feb 21, 2004.

  1. 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
    Steve Johnson, Feb 21, 2004
    #1
    1. Advertising

  2. Steve Johnson

    Barry White Guest

    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 wrote:
    > 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, Feb 21, 2004
    #2
    1. Advertising

  3. Barry White wrote:
    >
    > 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.
    Steve Johnson, Feb 21, 2004
    #3
  4. Steve Johnson

    Barry White Guest

    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


    Steve Johnson wrote:
    > Barry White wrote:
    >
    >>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, Feb 22, 2004
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    6
    Views:
    6,178
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,110
  3. sharan
    Replies:
    4
    Views:
    689
    CBFalconer
    Oct 30, 2007
  4. sharan
    Replies:
    2
    Views:
    830
    SM Ryan
    Oct 31, 2007
  5. Michele Simionato
    Replies:
    1
    Views:
    595
    Lacrima
    Mar 27, 2010
Loading...

Share This Page