2
\$\begingroup\$

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();
   }
}
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – CiaPan Mar 2 '16 at 7:59
  • \$\begingroup\$ 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. \$\endgroup\$ – Nick Mar 2 '16 at 8:12
1
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.