Java Tree Implementation

Question

I wrote a simple tree data type in Java consisting of nodes which are themselves trees, and where each tree has its own list of children (not a binary tree). I plan on eventually using it in a minimax algorithm where I keep track of future game states in a board game by holding different board states in nodes and holding moves that lead to each state as edges in the tree. Here's my code so far — any suggestions (whether it be conceptual or performance related, or other features I should add) are appreciated:

public class Tree<V, E> {
 private V data;
 //here the edgeVal is the edge leading from the node's parent to the node itself,
 //not from the node to any of its children
 private E edgeVal;
 private Tree<V, E> parent;
 private ArrayList<Tree<V, E>> children;
 public Tree(V data, Tree<V, E> parent, E edgeVal) {
 this.data = data;
 this.edgeVal = edgeVal;
 this.parent = parent;
 this.children = new ArrayList<Tree<V, E>>();
 }
 public void addChild(V childData, E edgeVal) {
 Tree<V, E> child = new Tree<V, E>(childData, this, edgeVal);
 this.children.add(child);
 }
 public Tree<V, E> getParent() {
 return this.parent;
 }
 public ArrayList<Tree<V, E>> getChildren() {
 return this.children;
 }
 public V getData() {
 return this.data;
 }
 public E getEdgeVal() {
 return this.edgeVal;
 }
 public boolean isRoot() {
 return this.parent == null;
 }
 public boolean isLeaf() {
 return this.children.size() == 0;
 }
 public String toString() {
 //assuming type of data has a nicely defined toString() method
 return this.data.toString();
 }
}

• CiaPan: I'm not an expert in game modelling, but I wonder if it is correct to assume the data structure is a tree. In some games a sequence of moves can lead to the same position. That leads to an infinite loop in a game and an infinite tree in strategy, which may be truncated by game rules (in chess, the same position for a third time ends the game) or may be not (I suppose, not all checkers variants do have such terminating rule).
• Nick: True if I were doing chess or checkers (I was a bit misleading when I said "board game") -- I'm actually using it for a game of Tron, where moving back to a space that you or your opponent has occupied makes you lose, so don't think I can hit an infinite loop.

Answer 1

Welcome to Code Review!

1. isLeaf compares the Size of children, a solution that is better readable is to use isEmpty() instead of compare the size of children.
2. The tree avoid a serialization that others may support, add the serializable-interface to keep serialization support.

3. edgeVal and data have no setter and to add final would help to avoid sideeffects whenever the code changes.

4. To have a ArrayList as a list of children has the problem that

   • The ArrayList can contain null
   • The ArrayList can contain one element twice (i do not think its a case you like to have)

   You better use some kind of set, a LinkedHashSet in example.

5. You can use getChildren() to have read-write-access to the children, if you do oscar.getChildren().add(oscar); your loop is perfect but not a Tree. Use the unmodifyable-functions of the class Collections to return a readonly-collection.

6. The class is named Tree that can contains a list of Tree. Even if a Tree can be a parasite to other Trees i propose to name the Class TreeNode.

7. toString should describe the node, not the data inside.

8. Am i the only one who write javadoc?