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:
Structure of a Generic Tree 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;
}
}
Popularity: 51% [?]
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 deepakl_2000@yahoo.com
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
I will modify the original to ensure that it makes defensive copies.
That’s a good modification and follows the best practice to make the class as immutable as possible. It must have slipped my mind
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
[...] Guus was kind enough to make a maven project for the Generic Tree. He also fixed an error in my equals method for the GenericTreeNode (I intended to do Object.equals(Object obj) but was doing GenericTreeNode.equals(GenericTreeNode obj). Since it’s a maven project, you can easily create a jar out of it and add it as a dependency to your project. You can download the project here. Thanks Guus! AKPC_IDS += "1405,";Popularity: unranked [?] Related PostsGeneric (n-ary) Tree in JavaCherryBlossomIntroducing CherryBlossomif-else in bAdkOdebAdkOde: An Esoteric LanguageJSTL, instanceof, and hasPropertyDuct-tape programmers are not heroesPerformance testing using The GrinderRunning the JavaFX 1.1 SDK on LinuxRunning the JavaFX 1.0 SDK on Linux Categories: Java, Programming and Development Tags: data structures, generic trees, java, k-ary trees, n-ary trees, programming, software engineering, trees (data structure) Comments (3) Trackbacks (0) Leave a comment Trackback [...]
Pingback by Maven project for Generic (n-ary) Tree in Java | Rough Book | May 25, 2011
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.