Header image

Generic (n-ary) Tree in Java

Posted on by vivin

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
Structure of a Generic Tree Node

The code for a Generic Tree Node looks like this:

GenericTreeNode.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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;
    }
}
Pages: 1 2 3
Category: Java, Programming and Development

55 thoughts on “Generic (n-ary) Tree in Java”

  1. Pingback: Answer: Java tree data-structure? #answer #programming #computers | IT Info

Leave a Reply

Your email address will not be published. Required fields are marked *

All original content on these pages is fingerprinted and certified by Digiprove