Write a tree class in Java where each level has a unique object type

Question

I need to write a tree class in Java where each level has a unique object type. The way it is written below does not take advantage of generics and causes alot of duplicate code. Is there a way to write this with Generics ?

 public class NodeB {
   private String nodeValue;
   //private List<NodeB> childNodes;
   // constructors
   // getters/setters
}

public class NodeA {
   private String value;
   private List<NodeB> childNodes;
   // constructors
   // getters/setters
}

public class Tree {
   private String value;
   private List<NodeA> childNodes;
   // constructors
   // tree methods
}

Right now it doesn't look like generics or templates would apply. Maybe if you gave us some more information? The only thing you could do here is implement an interface or inherit from an abstract base class — Falmarri
– Falmarri, Commented Jan 5, 2011 at 0:53
Out of curiosity, why do you need to do this? Is this a homework problem? — templatetypedef
– templatetypedef, Commented Jan 5, 2011 at 0:53
Is this tree limited to the NodeB level (two levels) by design or do you expect NodeC, NodeD... to occur ? — Costi Ciudatu
– Costi Ciudatu, Commented Jan 5, 2011 at 1:01
Falmarri - Yes inheriting from an abstract class is something i did try and it does help on multiple fronts specially when traversing the tree. — user479576
– user479576, Commented Jan 5, 2011 at 1:05
Does the uniqueness need to be enforced at compile time? Can it be done at runtime instead? — Stewart Murrie
– Stewart Murrie, Commented Jan 5, 2011 at 1:06

Petro Semeniuk · Accepted Answer · 2011-01-06 02:55:34Z

This is simplistic implementation, but enough to give general idea:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class GenericNode {

    public static abstract class AbstractNode<V, N> {
        private V value;
        private List<N> children;

        public AbstractNode(V value, N... children) {
            this.value = value;
            this.children = children != null ? Arrays.asList(children)
                    : Collections.<N> emptyList();
        }

        public V getValue() {
            return value;
        }

        public List<N> getChildren() {
            return children;
        }

        public int getNumberOfChildren() {
            return children.size();
        }

        @Override
        public String toString() {
            return value.toString() + "->" + children.toString();
        }
    }

    // leaf node type, ignore type of children
    public static class NodeB extends AbstractNode<String, Object> {

        public NodeB(String value, Object... nodes) {
            super(value, nodes);
        }
    }

    // example of typical node in the mid of tree
    public static class NodeA extends AbstractNode<String, NodeB> {
        public NodeA(String value, NodeB... nodes) {
            super(value, nodes);
        }
    }

    // top level node type
    public static class Tree extends AbstractNode<String, NodeA> {
        public Tree(String value, NodeA... nodes) {
            super(value, nodes);
        }
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static <V, N extends AbstractNode> int getNodeCount(
            AbstractNode<V, N> node) {
        int nodeCount = node.getChildren().size();
        for (N child : node.getChildren()) {
            nodeCount += getNodeCount(child);
        }
        return nodeCount;
    }

    public static void main(String[] args) {
        NodeB nodeB1 = new NodeB("Leaf node 1");
        NodeB nodeB2 = new NodeB("Leaf node 2");
        NodeA nodeA = new NodeA("Node with children", nodeB1, nodeB2);
        NodeA emptyNodeA = new NodeA("Empty node");
        Tree tree = new Tree("Tree", nodeA, emptyNodeA);
        System.out.println(tree);
        System.out.println(1 + getNodeCount(tree));
    }
}

You could make N and V types implement specific interfaces so it will be possible to call some common operations on values and/or children.

EDIT: updated implementation with recursive method for node count retrieval

Dimitris Andreou · Accepted Answer · 2011-01-05 09:44:58Z

2

All you need is a Pair<A, B>. Example of trees:

Pair<A, Pair<B, C>>
Pair<Pair<A, B>, Pair<C, D>>
Pair<Pair<Pair<A, B>, Pair<C, D>>, Pair<Pair<E, F>, Pair<G, H>>

ps: don't do this. :)

answered Jan 5, 2011 at 9:44

Dimitris Andreou

8,9062 gold badges35 silver badges36 bronze badges

Comments

Bill K · Accepted Answer · 2011-01-05 18:15:48Z

This is an ideal spot for everything inheriting from "Node", but even that is unnecessary.\

What you probably want is a single generic "Node" object that contains references to your different classes (use composition before inheritance).

At that point, each of your different classes probably has something that can be done to them (otherwise why are they all in the same data structure?) Have them implement a common interface with this common functionality. The node class can delegate to this interface, or some other class can extract the class by this interface and act on it.

This would be better than trying to force something to also BE a node--do one simple thing and do it well.

--edit--

I can't really add an example that is relevant to you because you didn't post anything about your scenario.

But let's say that you have these different classes A, B * C. First of all are they related AT ALL aside from all being children of Object? Let's say they all implement interface "Iface". (If not, you can just replace Iface with "Object", but this really implies a bad design.)

Anyway, your "Node" object is just one object--

public class Node {
    private List<node> children; 
    private Iface myObject;
    ... setters, getters, tree implementation, tree navigation, related garbage...
}

Now this is enough to create your tree. One thing that you might be able to do to make things smoother, have "Node implements Iface" and delegate any calls to it's object. For instance, if Iface contains an eat(Food foodtype) method, your node could implement Iface and have a method:

public void eat(Food foodtype) {
    myObject.eat(foodtype);
}

This would make the "Node" class act as though it was the class it contained.

By the way--another relatively good idea at this point would be to make myObject "private final" and ensure it is not null in the constructor. That way you would always know it was set and none of your delegated members would have to do null checks.

jzd · Accepted Answer · 2011-01-05 03:21:15Z

0

I don't think generics are going to help you much in this case. Instead of having a different class for each level in the tree. What about one node class that has children and store a different class on each level. That should help eliminate a lot of the duplication.

answered Jan 5, 2011 at 3:21

jzd

23.6k9 gold badges58 silver badges76 bronze badges

2 Comments

user479576 Over a year ago

Thank you for your reply. That said how are you going to represent the hierarchy in one class ?

jzd Over a year ago

Like I mentioned just use a single Node class. It would be verry similar to your NodeA or Tree classes but would store an object type other than a String.

shelman · Accepted Answer · 2011-01-05 09:39:31Z

0

I'm fairly new to Java, so this might have issues I'm not aware of, but it seems to work on a simple level at least.

Define your main Node class - this one will be the root of the tree.

public class NodeA {

private String _value;
private ArrayList<NodeA> _children;
private int _depth;

public NodeA (String value, int depth) {
    _value = value;
    _children = new ArrayList<NodeA>();
    _depth = depth;
}

//probably want getters for _children and _value here

//this makes a new child, with its type depending on the depth of the tree it will
//be placed at.  NodeB and NodeC will both inherit from NodeA
public void add(String value) {
    switch (_depth) {
        case 0:
            _children.add(new NodeB(value, _depth+1));
            break;
        case 1:
            _children.add(new NodeC(value, _depth+1));
            break;
    }
}

The add() method is going to create a new child for the node using the specified value. If you initialize the root of the tree as a NodeA with depth 0, you can add children to nodes and the tree should end up populated so that the next level contains all NodeB's, and the next all NodeC's. The code for NodeB and NodeC is super simple and could be replicated to create an arbitrary amount of Node levels (here is that code).

public class NodeB extends NodeA {

public NodeB(String value, int depth) {
    super(value, depth);
}
//nothing else needed!

The code for NodeC is identical, except for the obvious replacements of B's with C's.

Hope this helps / is the kind of answer you wanted!

answered Jan 5, 2011 at 9:39

shelman

2 Comments

Petro Semeniuk Over a year ago

The only issue is that you'll need to update base class (NodeA) each time when you want to add one more node type(ie NodeX, NodeZ).

shelman Over a year ago

Good point. It would probably be a better idea to have add (which should also be renamed to addchild) overridden in each subclass instead of using the switch statement. That would make _depth unnecessary as well.

Collectives™ on Stack Overflow

Write a tree class in Java where each level has a unique object type

5 Answers 5

Comments

Comments

1 Comment

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

1 Comment

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related