Generic (n-ary) Tree in Java

This project is available on github. Please download from there to make sure you have the latest version.

Last week I was solving a problem at work that required the use of a Generic (n-ary) Tree. An n-ary tree is a tree where node can have between 0 and n children. There is a special case of n-ary trees where each node can have at most n nodes (k-ary tree). This implementation focuses on the most general case, where any node can have between 0 and n children. Java doesn't have a Tree or Tree Node data structure. I couldn't find any third-party implementations either (like in commons-lang). So I decided to write my own.

First, we need to define the node of our tree. Our node has two attributes. One is the data, and another is a List which can contain references to the children of that node:

The code for a Generic Tree Node looks like this:

GenericTreeNode.java
[sourcecode lang="java"]
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class GenericTreeNode {

public T data;
public List> children;

public GenericTreeNode() {
super();
children = new ArrayList>();
}

public GenericTreeNode(T data) {
this();
setData(data);
}

public List> getChildren() {
return this.children;
}

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

public boolean hasChildren() {
return (getNumberOfChildren() > 0);
}

public void setChildren(List> children) {
this.children = children;
}

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

public void addChildAt(int index, GenericTreeNode child) throws IndexOutOfBoundsException {
children.add(index, child);
}

public void removeChildren() {
this.children = new ArrayList>();
}

public void removeChildAt(int index) throws IndexOutOfBoundsException {
children.remove(index);
}

public GenericTreeNode getChildAt(int index) throws IndexOutOfBoundsException {
return children.get(index);
}

public T getData() {
return this.data;
}

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

public String toString() {
return getData().toString();
}

public boolean equals(GenericTreeNode node) {
return node.getData().equals(getData());
}

public int hashCode() {
return getData().hashCode();
}

public String toStringVerbose() {
String stringRepresentation = getData().toString() + ":[";

for (GenericTreeNode node : getChildren()) {
stringRepresentation += node.getData().toString() + ", ";
}

//Pattern.DOTALL causes ^ and $ to match. Otherwise it won't. It's retarded.
Pattern pattern = Pattern.compile(", $", Pattern.DOTALL);
Matcher matcher = pattern.matcher(stringRepresentation);

stringRepresentation = matcher.replaceFirst("");
stringRepresentation += "]";

return stringRepresentation;
}
}
[/sourcecode]