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
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class GenericTreeNode<T> {
public T data;
public List<GenericTreeNode<T>> children;
public GenericTreeNode() {
super();
children = new ArrayList<GenericTreeNode<T>>();
}
public GenericTreeNode(T data) {
this();
setData(data);
}
public List<GenericTreeNode<T>> getChildren() {
return this.children;
}
public int getNumberOfChildren() {
return getChildren().size();
}
public boolean hasChildren() {
return (getNumberOfChildren() > 0);
}
public void setChildren(List<GenericTreeNode<T>> children) {
this.children = children;
}
public void addChild(GenericTreeNode<T> child) {
children.add(child);
}
public void addChildAt(int index, GenericTreeNode<T> child) throws IndexOutOfBoundsException {
children.add(index, child);
}
public void removeChildren() {
this.children = new ArrayList<GenericTreeNode<T>>();
}
public void removeChildAt(int index) throws IndexOutOfBoundsException {
children.remove(index);
}
public GenericTreeNode<T> 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<T> node) {
return node.getData().equals(getData());
}
public int hashCode() {
return getData().hashCode();
}
public String toStringVerbose() {
String stringRepresentation = getData().toString() + ":[";
for (GenericTreeNode<T> 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;
}
}
So what was the problem at work that necessitated this solution?
@SteveO
I was trying to represent data that had parent-child relationships an arbitrary number of levels deep.
I believe it’s a rough implementation of your idea.
Which one do you prefer? Using Pattern, Matcher etc over –
return (this.children.size()>0? str.substring(0, str.lenth()-2) : str ) + “]”;
@Lobo
I actually prefer the regex because it’s more obvious what I’m doing. When using a substring, it’s not immediately obvious (without comments) what you’re doing. I also gravitate towards to regexes due to the fact that I’ve written a lot of Perl code. Regexes aren’t as elegant in Java though.
Are you releasing this code as a project somewhere? It’d be nice to be able to simply include it as a library.
@Guus
Good point – I’ll try to jar it up sometime and release it as a library!
@vivin
Actually, I couldn’t wait and made a little Maven project out of it myself. I’ll be happy to send it to you, if you’d like me to.
There appears to be a small omission in the code: you’re not overriding Object.equals(Object obj) even though you intent to. Instead, you have GenericTreeNode.equals(GenericTreeNode obj).
Poke me via mail (I included it in the header of this comment) and I’ll send you a project archive.
@Guus
Ah, good point. Thanks for catching that! I’ll send you an email – thanks for taking the time to make a project. I do have a google code account – I should probably move this into that!
Hey,
Many companies have tons of Active Directory Groups, and there are group of groups, and it could be very tricky to assess how many group of groups there are.
I am trying to use your code in order to build a n-ary tree from these groups.
For each group stored in Active Directory there are :
– the members of this group it could “users” but also groups
– the groups that this group below to
I was wondering how to use your n-ary tree to build the n-ary trees in order to have a list of the trees and how deep they are. Any ideas ?
Many thanks, Oliver
I am using your code in order to build a tree from
I think the best way to go about it would be to create a Group object that maintains a list of Users. Then, your generic tree would be genericized by Group, meaning that the data element of each node is a Group object. This way you don’t need to represent Users as individual nodes. They can be wrapped up inside the Group object.
When you build up your tree, you first build up Group objects and add users to them. You then use the Group object to create a GenericTreeNode.
For over 4 hours, i was googling and trying different n-ary tree implementations. Yours was the best implementation!! you saved a lot of time.
Thanks
Vivin,Please send the enture source code as a zip file to [email protected]
Hi Deepak. You can download the project zip from this page: http://vivin.net/2010/03/02/maven-project-for-generic-n-ary-tree-in-java/
Thanks
Was just about to post the same!
@Guus I have a project on Github for a Tree collections library. I haven’t worked on it in a few months; I need to write some tests for it and also add a few more trees in there. You can take a look at it:
http://github.com/vivin/tree
You appear to forgot to include the pom.xml file.
@Guus
In the zip? Or for the project on github? Yeah that doesn’t have a pom (yet). It’s just up there while I’m working on it 🙂
Hey @Guus,
Can you write a main method so that i can go ahead and implement the tree structure in java,I have a homework assignment given for implementing a Tree structure,Do you think your implementation will serve purpose,Can you write a Public static main method such that Tree operations ,creation of parent and child relationship are possible and created and finnaly displayed
@Deepak
You shouldn’t be asking others to do your homework for you. How will you learn anything then? If your homework asks you implement a tree, then you should do it yourself. Please do — you will learn more that way.
Thanks for the great implementation. I modified my local version to include one change:
I didnt like the fact that an external class can get hold of the children list and modify them without calling the classes addChild() like methods.
For instance;
GenericTreeNode tree = new GenericTreeNode();
List<GenericTreeNode> kids = new ArrayList<GenericTreeNode>();
kids.add(new GenericTreeNode(“bob”));
tree.setChildren(kids);
tree.getNumberOfChildren(); // returns 1
kids.add(new GenericTreeNode(“fred”));
tree.getNumberOfChildren(); // returns 2 even though addChild was not called!
So I redefined the following methods;
public void setChildren(List<GenericTreeNode> children) {
this.children = new ArrayList<GenericTreeNode>().addAll(children);
}
public List<GenericTreeNode> getChildren() {
return new ArrayList<GenericTreeNode>(this.children);
}
Thanks again…..
Bow
—–
@bow
That’s a good modification and follows the best practice to make the class as immutable as possible. It must have slipped my mind 🙂 I will modify the original to ensure that it makes defensive copies.
G’day mate,
Thanks for the library. I was halfway through making a similar class for a path planning library we are building at the university. I reckon I could use yours now. Though I have had to rename the package hierarchy for your classes, I have preserved your copyright statement and licence as well as have a put a link to this page in the source code. Our library is yet under development and once it’s tested, it’d be put into the public domain. I’ll post a link to it later here at your page.
Cheers,
Abhi
School of CS&IT, RMIT University
@Abhi
Thanks! I don’t know if you checked it out, but Guus made a maven project for this library so you should be able to integrate it without having to change the package structure (depends on whether your library is mavenized or not, though).
Hi,
I need to recursively build a tree with an arbitrary number of children per node.
It turns out that I cannot get the parent of a GenericTreeNode. Is there any way to move from leaf to root in your implementation?
Thanks
@jens
It’s funny you say that because I needed that very same functionality just yesterday! My current implementation does not offer that functionality, however it should be trivial to add. You just need a private property in GenericTreeNode
and in the addChild method, set the parent of the new child node to this.
Hi Vivin,
Your Tree implementation was really useful for us in our compilers project for maintaining the relationship between various scopes in a program. Though we needed only a very small subset of Tree operations, your implementation provided a very good view into how to build an n-ary Tree in Java.
And like you said in your above post, I also needed the parent pointer in every node to traverse back from a node all the way upto the root.
Also, in line#69 in GenericTree.java, there is a redundant \i=0\ assignment. I guess you could remove that.
Thanks a lot
@Akshay glad to be able to help 🙂
hi
class GenericTreeNode.java line 68, put there keyword @Override and see if it compile.
Here are two additional routines to allow searching for data.
public List<GenericTreeNode> locateOccurances(T data) {
List< GenericTreeNode > occurances = new ArrayList<GenericTreeNode>();
if (root != null) {
occurances.addAll( locateOccurances(root, data) );
}
return occurances;
}
public List<GenericTreeNode> locateOccurances(GenericTreeNode node, T data) {
List< GenericTreeNode > occurances = new ArrayList<GenericTreeNode>();
if (node.data == data) {
occurances.add(node);
}
for (GenericTreeNode child:node.children) {
occurances.addAll( locateOccurances(child, data) );
}
return occurances;
}
Hi,
Probably I`m missing the point but what is the real purpose of build* methods? I mean, except for testing, why I would use a List<GenericTreeNode> ? BTW, I don’t think that “build” is the correct name. Can you “build a generic tree” ?
My $,02.
Cheers,
–FM
@Fernando: The purpose of the “build” methods is to return a representation of the tree as a list in either preorder, or postorder form. The “buildWithDepth” returns a representation of the tree with the depths of the node as well, which is useful if you’re trying to provide a graphical representation of the tree.
In hindsight, I believe it would have been better to implement an iterator!
@John Vorwald: Thanks!
Thanks, vivin.
It was helpful. Implementation was easy and understandable much faster.
Is this the latest implementation on this website. I believe this is exactly what im looking for in my project. Just to be clear this is a tree that can have any number of root nodes? also the T data that could also be anything? e.g. a simple string or a whole list of properties per say?
main question though is that this can be more than just a binary tree? for example a quaternary tree where each node can lead to 4 options
Could you possibly send me a method that iterates over the whole tree?
@Devonte: Yes, it’s genericized and so T can be anything.
This is a generic tree and so any node can have any number of nodes. It could be a binary or a quaternary tree, although not strictly so because no constraints are enforced on the number of children a node can have.
Could you please help me in solving this.
http://www.careercup.com/question?id=13876713
Mr. Vivin,
Please help me. Can you help me?
http://stackoverflow.com/questions/12910719/how-to-populating-modified-preorder-tree-traversal-data-into-java-tree-object
Hi Vivin, Can you structure be used even if I have nodes that are of different types? I have at least 5 different type of nodes one at each level. Please confirm!
@JM: Do you mean the generic type parameter? You can only add nodes that contain data of the type that you specify, when you create the node or the tree. However, you can get around this if all of those objects implement the same interface. But you have to make sure that it makes sense for all of them to use the same interface.
Thanks Vivin, that totally makes sense.
However I noticed another issue while converting the tree (with several nodes) into JSON object for representing the tree on UI. Because every GenericTreeNode is having references to child and parent and every parent is intern having child and parent, it is going a infinite recursion while converting the tree into JSON object (Jackson JSON). I used annotations from http://wiki.fasterxml.com/JacksonFeatureBiDirReferences to avoid bidirectional references. But the problem is after converting the Tree into JSON this way, I loosing references to all parents. Any ideas to get rid of this problem? Thanks in advance!
Hey JM, did you figure out your JSON issue?
Btw, are you displaying this Tree in a UI? What technology/library are you using?
Thanks!
@JM: JSON is simply a notation and so it’s not functional. This is why it’s impossible to create self-referential constructs in JSON. The only way you can do it in an abstract manner, such as using an id to refer to a parent.
Thanks! Great library. I’ve added the following method:
public List getDataOfChildren() {
List result = new ArrayList();
for (GenericTreeNode child:this.children) {
result.add(child.data);
}
return result;
}