Records to Tree

Question

Hi Guys,

A little advise please.

I am trying to create a tree out of following rows of data:

TOP     Level1     NotLeaf
Level1     Data1      leaf
TOP        Level11    NotLeaf
Level11    Level2     NotLeaf
Level11    Data4      leaf
Level2     Data2      leaf
Level2     Data3      leaf

The last column shows whether a node is a leaf or not. The tree, therefore, would look like:

Top
|
|- Level1,   Level11
     |          |
     |          |
   Data1     Level2, Data4
                |
                |
              Data2, Data3

I am storing each row of the data in a bean and I then put the bean in a list.

public class Data {

    private String parent;
    private String name;
    private int isLeaf;

    public Data(String parent, String name, int isLeaf){
 this.parent = parent;
 this.name = name;
 this.isLeaf= isLeaf;

            //add to the list
    }

   //Getters

   public List<Data> getDataList(){
      return dataList;
  }
}

Now for the tree, I wrote a Node class as below:

public class Node {

    private final String nodeName;
    private final List<Node> children;

    public Node(String nodeName) {
        this.nodeName = nodeName;
        this.children = new ArrayList<Node>(10);
    }

    public String getNodeName() {
     return nodeName;
    }

    public List<Node> getChildren() {
     return Collections.unmodifiableList(children);
    }

    public void addChild(Node child) {
     children.add(child);
    }
}

But I can't seem to figure out how to insert the data into the Node and get the relationship as shown in the tree above.

Perhaps lack of sleep is hiding the obvious but any advise would be most helpful.

Thanks

Answer 1

I wouldnt separate the Data from the Node. Instead, have the Node be a composite and maintain the parent info. The test for isLeaf could return true if children is empty. A 'Top' node would have a null parent.

Answer 2

Lack of sleep myself, so I'm not going to code, but roughly -

• You don't need a column saying if something is a leaf node or not. If it has children, it's a leaf, otherwise it's not.

• Create a start node labelled "ROOT".

• Your node class is fine. Create a HashMap<String,Node> . Each line, as you've written it, contains a PARENT-CHILD relationship. You iterate through your lines, at each line, you do this

• If the map already contains a Node named parent, get it. Otherwise create it and add to the map. Same for child. Add the child node to the parent node. When you create the node, if the node is listed in the PARENT column, you add that to the ROOT node. If it's listed in the child column, you delete it from the root node.

After you've parsed all your lines, the only children of the root will be nodes that have appeared in the PARENT column and not the CHILD column. Anything that appeared in the CHILD column and not the PARENT column will be a leaf node. Anything that appeared in the parent column will not be a leaf, unless the child listing was null.

Also, I'd avoid the labels "TOP" and "LEVEL1" which imply a fixed position in the tree, and us the labels PARENT and CHILD. That way you just have a list of relationships that can exist at any arbitray point in the tree.