How to create a tree-type object in java?

Question

I've always wondered what is the best practice to create objects which have lists within lists within lists etc. Let's say I have this sort of object :

    root = new CarrierTreeNode(null, 
            new CarrierTreeNode[] {
                new CarrierTreeNode(new CarrierTreeItem("item1"), new CarrierTreeNode[] {
                    new CarrierTreeNode(new CarrierTreeItem("item1.1"))
                }),
                new CarrierTreeNode(new CarrierTreeItem("item2"), new CarrierTreeNode[] {
                    new CarrierTreeNode(new CarrierTreeItem("item2.1"))
            })
    });

and I want to generate this dynamically and also access and modify the lists/arrays within it dynamically. Is there a design pattern for this? Thank you.

To make it more clear, the constructor used here is like this : node (item, node[])

Answer 1

You might want to have a look at the composite pattern. In short, this is used when Object A holds a collection of Object A.

This pattern / data structure allows easy recursive behavior.

There are many sources, so if this doesn't suffice, simple go to google for more information, but here's a start: https://en.wikipedia.org/wiki/Composite_pattern

As for the creation part, I'd typically use a factory or builder in that case, but the exact implementation vary. Say you had a 2d array if items, and you wanted to create these nodes according to this array.

public class NodeBuilder{
    public CarrierTreeNode build(String[][] items){
        CarrierTreeNode node = new CarrierTreeNode(null);
        for(int i = 1; i < items.length; i++){
           CarrierTreeNode nextNode = new CarrierTreeNode(new CarrierTreeItem(items[i][0]));
           node.addNextNode(nextNode);
           for(int j = 1; j < items[i].length; j++)
               nextNode.addNextNode(new CarrierTreeItem(items[i][j]));
        }
        return node;
    }
}

This would obviously only work for a structure of 3 layers. A recursive approach is preferable. You could create a system where build calls build n times, to create the depth you want. The problem is in acquiring the data, for that to work, the data must already be in the right structure, but just as strings. If your strings are dynamically generated, so that the builder could figure out the data, it would be possible to make it work.

Answer 2

I propose this design hoping it will help you :

• TreeElement iterface : the generic tree element type.
• Item class that implements the TreeElement iterface :so it can be a key for a tree node or a value of a tree node.
• Node class that implements also the TreeElement interface so it can be a base node or a value of a key.

This is the implementation :

interface TreeElement {

    enum ElementType {
        NODE, ITEM
    };

    public TreeElement getElement(Item item);

    public Node addElement(Item item, TreeElement element);

    public ElementType getType();

}

class Item implements TreeElement {

    String name;

    public Item(String name) {
        super();
        this.name = name;
    }

    @Override
    public TreeElement getElement(Item item) {
        return null;
    }

    @Override
    public ElementType getType() {
        return ElementType.ITEM;
    }

    @Override
    public Node addElement(Item item, TreeElement element) {
        return null;
    }

    @Override
    public String toString() {
        return "Item [" + name + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Item other = (Item) obj;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

}

class Node implements TreeElement {

    Map<Item, TreeElement> map;

    {
        map = new HashMap<>();
    }

    @Override
    public TreeElement getElement(Item item) {
        return map.get(item);
    }

    @Override
    public ElementType getType() {
        return ElementType.NODE;
    }

    public Node addElement(Item item, TreeElement element) {
        this.map.put(item, element);
        return this;
    }

    @Override
    public String toString() {
        return "Node " + map + " ";
    }

}

Test the code :

Node node = new Node();
Item item = new Item("Item 1");
node.addElement(item, new Node().addElement(new Item("Level 1"), new Item("Item 1")));

System.out.println(node);
//Print : Node {Item [Item 1]=Node {Item [Level 1]=Item [Item 1]} } 

TreeElement element = node.getElement(item);

if (element.getType().equals(ElementType.NODE)) {
    element.addElement(new Item("Level 2"), new Node().addElement(new Item("Item 2.1"), new Item("Item 2.2")));
}

System.out.println(node);
//Print : Node {Item [Item 1]=Node {Item [Level 1]=Item [Item 1], Item [Level 2]=Node {Item [Item 2.1]=Item [Item 2.2]} } } 

Important : equals() and hashcode() are critical for the behavior of the example especially equals(). They are used in the Map collections to determine if a collection contains a given element.

Answer 3

Most simple tree node implementation must contain one field for store data and list of own children.

public class Node<T> {

    private T data;
    private List<Node> list = new LinkedList<>();

    public Node(){}

    public Node(T data){
        this.data = data;
    }

    public List<Node> getChildList() {
        return list;
    }

    public void setData(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }
}

This class is ready to build simple tree structure:

Node<String> root = new Node<String>("Stark");
root.getChildList().add(new Node<String>("Benjen"));

Node<String> eddard = new Node<String>("Eddard");
root.getChildList().add(eddard);
eddard.getChildList().add(new Node<String>("Arya"));

This implementation is simplest but of cause not the best. Classically tree node provides information about parent and sibling nodes, methods for internal recursive search , control of cycle references and many other things (wiki describes it very detailed).