How to implement a tree data-structure in Java?

Question

Is there any standard Java library class to represent a tree in Java?

Specifically I need to represent the following:

• The sub-tree at any node can have an arbitrary number of children
• Each node (after the root) and it's children will have string value
• I need to get all the children (some sort of list or array of Strings) of a given node and it's string value(i.e. a method that will take a node as input and return all the string values of the children node as output)

Is there any available structure for this or do I need to create my own (if so implementation suggestions would be great).

Archery

If you're using Java 8, and would like to traverse your nodes with streams, filtering, etc; then you might want to take a look at Durian github.com/diffplug/durian – Anamorphosis

Answer 1

Here:

public class Tree<T> {
    private Node<T> root;

    public Tree(T rootData) {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }

    public static class Node<T> {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }
}

That is a basic tree structure that can be used for String or any other object. It is fairly easy to implement simple trees to do what you need.

All you need to add are methods for add to, removing from, traversing, and constructors. The Node is the basic building block of the Tree.

Extrovert

You may want a parent field too if you want to get the path from a child node. – Springtime

True, if you wanna be able to go up the tree you need a parent ref. – Extrovert

Strictly speaking the Tree class is not necessary, because every Node can in itself be seen as a tree. – Vicariate

@Joa, I like having a structure to contain the root. You can add methods to the tree class that make more sense to call on a tree rather than a single node. – Extrovert

@Justin: for example? That's an honest question: I can't think of a single method that makes sense on the whole tree that doesn't make sense on a sub-tree. – Vicariate

@Joachim, I guess I like to abstract out the representation of the tree. You could swap out the node structure with an array based representation. That is why I don't like exposing a node. – Extrovert

@Justin: if you don't expose the nodes, how do you write a method that says "add that node as a child to this other node"? That argument only makes sense when you're implementing some ADT and use a tree internall (as done in TreeSet, for example). But I understood the question to be about an actual tree ADT. – Vicariate

@Joa, well, I usually use a tree in some internal code. SO, that is why I wrote this one the way I did. Force of habit. And, I think it is good practice. I don't feel like you lose anything by having the outer tree structure. And, it can be easier to understand if you have a concrete tree that you are working with, instead of just nodes. – Extrovert

I agree with @Joa that the Tree class is not necessary. I prefer to leave the recursive nature of trees explicit in code by not adding a separate Tree class and consistently using the Node class. Instead I name a variable 'tree' or 'root' if it needs to be clear that you are dealing with the root Node of a tree. – Donohue

to save 40 minutes use more completed sample here – Catnap

@Joa "Strictly speaking the Tree class is not necessary" in which sense? Semantically speaking (and for the data structure point of view) your comment is not correct. A root node is just one of the many implementation of the Tree concept. For example, one should not have a class Dog and say cat = new Dog() just because a dog does (for what we care) the same things as cats. – Feinleib

@ElMarce: the reason I say it's not strictly necessary is that it doesn't add any operations that you can't also take on any given sub-tree (a.k.a "a Node"). If you chose to have a Tree class (and that is of course a perfectly valid choice) then all you're doing is to restrict what can be viewed as a Tree. If I don't differentiate between a Tree and a Node, then I have the ability to trivially view every sub-tree as a tree in its own right. That might not be what your specific domain asks for, so you might still want to have a Tree class. – Vicariate

@Joa A four-years-older me agrees with you completely. Nix the tree class. – Extrovert

Separate classes (interfaces) for me. Tree has isEmpty() and size(), TreeNode has childCount(), descendentCount() and toTree(). I find this to be a clearer description of the actual objects, and also provides more flexibility when writing implementations other than the common linked version. Not sure how you would represent an empty tree if you only had a single node class? – Autoerotic

@Autoerotic that is also an interesting implementation...but even those Tree class methods can be implemented in the TreeNode class in a manner of speaking. How is size() different from childCount()? As for isEmpty(), if the root TreeNode is null then it is empty, so the isEmpty() method could probably be replaced by a null check. – Bonkers

Sure @scott-scooter-weidenkopf, you can do it either way. But, for example, to flatten a tree I find array = new Object[tree.size()] much more readable than array = new Object[(node == null ? 0 : (node.descendentCount() + 1))]. – Autoerotic

@JoachimSauer If you want it to be an AVL tree, a Node class is needed, since rotating the tree can change the root. (Just an example) – Fortuitous

@AmitGold I don't think that holds. – Ketose

Field 'root' could be final. Using the final keyword makes code less error-prone. It may also be helpful for compiler optimisations. – Impresa

Answer 2

Yet another tree structure:

public class TreeNode<T> implements Iterable<TreeNode<T>> {

    T data;
    TreeNode<T> parent;
    List<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<T>(child);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }

    // other features ...

}

Sample usage:

TreeNode<String> root = new TreeNode<String>("root");
{
    TreeNode<String> node0 = root.addChild("node0");
    TreeNode<String> node1 = root.addChild("node1");
    TreeNode<String> node2 = root.addChild("node2");
    {
        TreeNode<String> node20 = node2.addChild(null);
        TreeNode<String> node21 = node2.addChild("node21");
        {
            TreeNode<String> node210 = node20.addChild("node210");
        }
    }
}

BONUS
See fully-fledged tree with:

• iterator
• searching
• Java/C#

https://github.com/gt4dev/yet-another-tree-structure

Catnap

Just found your library extremely useful. Thank you. But I would like to know how to implement dynamically populating the tree structure based on reference relationship between parent and child. Example given is I have one member1 sponsor another member2, and member2 sponsor member 3 and so and so for. Already have the table records relationship but just unsure i can populate them into a tree using your library. – Noel

as of 2016, the link contains no source files or downloads – Heathenize

In my view, this answer three years after the above higher rated answer, is the cleaner one. However, I would replace the LinkedList with an ArrayList for this.children. – Dear

I would use a Set for the children. – Quincuncial

I could be wrong but it appears that with this implementation, you must call hasNext() before each call to next() to get valid results. This isn't part of the Iterator spec. – Plage

How can i remove child? – Parallelepiped

Answer 3

There is actually a pretty good tree structure implemented in the JDK.

Have a look at javax.swing.tree, TreeModel, and TreeNode. They are designed to be used with the JTreePanel but they are, in fact, a pretty good tree implementation and there is nothing stopping you from using it with out a swing interface.

Note that as of Java 9 you may wish not to use these classes as they will not be present in the 'Compact profiles'.

Relict

Yeah I used them in the past, and they will do everything you want from a tree. The only downside I can think of is the length of the names of their respective implementing classes: DefaultTreeModel and DefaultMutableTreeNode. Verbose, but not that its all that important I guess. – Springtime

Good way to cope with that is to create a couple of static methods newModel() and newNode() and then static import them. – Relict

I would avoid using Swing libraries on non-Swing-related functions. This is bad coding practice. You never know how Swing implements their trees, what their dependencies are and how this could change in the future. Swing is not a utility library but a UI library. – Leslielesly

I think bad coding practice is a little harsh. – Relict

javax.swing.tree.TreeModel is a public interface (exactly like java.util.List) and it will not have incompatible changes. An added advantage is that you could easily debug/visualize your tree while developing. – Agustinaah

@Leslielesly I know this is very late to comment. But I agree to your point using libraries can be a bad practise for beginners. – Floreated

You should avoid using these classes, since in the future your code may has to run on a compact profile. On these profiles the classes from the swing-package are not available. (see oracle.com/technetwork/java/embedded/resources/tech/…). I already had to refactor code that had no ui at all but uses TreeModel and TreeNode. This is a risk that should be avoided... – Passe

@TomSeidel seems like a reasonable point, have updated the answer so that people will actually see, I suspect that information in comments doesn't really get much attention. – Relict

"there is nothing stopping you from using it with out a swing interface" Until you realize your Android APK is bloated with libraries you only need one or two classes from and account for 50% of the total size... – Cannell

@FranMarzoa all the more reason to use something shipping in the JDK :) .. of course i haven't clue if Android ships swing in the runtime :( – Relict

Nope, actually it won't even work on Android... I think it's OK to use third party libraries in some cases, but having to add Swing only for this is not reasonable, even if it is a desktop project. – Cannell

Answer 4

What about this?

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
  * @author [email protected] (Yohann Coppel)
  * 
  * @param <T>
  *          Object's type in the tree.
*/
public class Tree<T> {

  private T head;

  private ArrayList<Tree<T>> leafs = new ArrayList<Tree<T>>();

  private Tree<T> parent = null;

  private HashMap<T, Tree<T>> locate = new HashMap<T, Tree<T>>();

  public Tree(T head) {
    this.head = head;
    locate.put(head, this);
  }

  public void addLeaf(T root, T leaf) {
    if (locate.containsKey(root)) {
      locate.get(root).addLeaf(leaf);
    } else {
      addLeaf(root).addLeaf(leaf);
    }
  }

  public Tree<T> addLeaf(T leaf) {
    Tree<T> t = new Tree<T>(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }

  public Tree<T> setAsParent(T parentRoot) {
    Tree<T> t = new Tree<T>(parentRoot);
    t.leafs.add(this);
    this.parent = t;
    t.locate = this.locate;
    t.locate.put(head, this);
    t.locate.put(parentRoot, t);
    return t;
  }

  public T getHead() {
    return head;
  }

  public Tree<T> getTree(T element) {
    return locate.get(element);
  }

  public Tree<T> getParent() {
    return parent;
  }

  public Collection<T> getSuccessors(T root) {
    Collection<T> successors = new ArrayList<T>();
    Tree<T> tree = getTree(root);
    if (null != tree) {
      for (Tree<T> leaf : tree.leafs) {
        successors.add(leaf.head);
      }
    }
    return successors;
  }

  public Collection<Tree<T>> getSubTrees() {
    return leafs;
  }

  public static <T> Collection<T> getSuccessors(T of, Collection<Tree<T>> in) {
    for (Tree<T> tree : in) {
      if (tree.locate.containsKey(of)) {
        return tree.getSuccessors(of);
      }
    }
    return new ArrayList<T>();
  }

  @Override
  public String toString() {
    return printTree(0);
  }

  private static final int indent = 2;

  private String printTree(int increment) {
    String s = "";
    String inc = "";
    for (int i = 0; i < increment; ++i) {
      inc = inc + " ";
    }
    s = inc + head;
    for (Tree<T> child : leafs) {
      s += "\n" + child.printTree(increment + indent);
    }
    return s;
  }
}

Gummite

How would DFS be implemented on a tree created using this class object? – Lead

How would removing a leaf be implemented using this class? – Efflorescent

What would the head field be used for? – Refulgent

It would have been great if this class had some documentation. I don't quite understand what methods like setAsParent or getHead do and this is the time when I really could get some help on tree data structures. Even the original source of the document has no comments. – Hereinafter

Answer 5

I wrote a little library that handles generic trees. It's much more lightweight than the swing stuff. I also have a maven project for it.

Nonpayment

I am using it now, works brilliantly. Had to change the source significantly for my own customizations, but it was a great starting point. Thanks Vivin! – Leslielesly

Answer 6

public class Tree {
    private List<Tree> leaves = new LinkedList<Tree>();
    private Tree parent = null;
    private String data;

    public Tree(String data, Tree parent) {
        this.data = data;
        this.parent = parent;
    }
}

Obviously you can add utility methods to add/remove children.

Edgar

This suggests that the parent of a tree is a tree. I believe you were trying to create a Tree Node class. – Garlinda

@MadhurBhargava such a "Node" also represents a subtree hence a Tree. Though to have a separate top-level Tree class, and a separate Node class has two advantages: a redundant int size; can be kept in Tree, And with the above one has to write something like tree = tree.sortedAdd(data) for tree manipulations. – Therewith

Answer 7

You should start by defining what a tree is (for the domain), this is best done by defining the interface first. Not all trees structures are modifyable, being able to add and remove nodes should be an optional feature, so we make an extra interface for that.

There's no need to create node objects which hold the values, in fact I see this as a major design flaw and overhead in most tree implementations. If you look at Swing, the TreeModel is free of node classes (only DefaultTreeModel makes use of TreeNode), as they are not really needed.

public interface Tree <N extends Serializable> extends Serializable {
    List<N> getRoots ();
    N getParent (N node);
    List<N> getChildren (N node);
}

Mutable tree structure (allows to add and remove nodes):

public interface MutableTree <N extends Serializable> extends Tree<N> {
    boolean add (N parent, N node);
    boolean remove (N node, boolean cascade);
}

Given these interfaces, code that uses trees doesn't have to care much about how the tree is implemented. This allows you to use generic implementations as well as specialized ones, where you realize the tree by delegating functions to another API.

Example: file tree structure

public class FileTree implements Tree<File> {

    @Override
    public List<File> getRoots() {
        return Arrays.stream(File.listRoots()).collect(Collectors.toList());
    }

    @Override
    public File getParent(File node) {
        return node.getParentFile();
    }

    @Override
    public List<File> getChildren(File node) {
        if (node.isDirectory()) {
            File[] children = node.listFiles();
            if (children != null) {
                return Arrays.stream(children).collect(Collectors.toList());
            }
        }
        return Collections.emptyList();
    }
}

Example: generic tree structure (based on parent/child relations):

public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> {

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<>();
        tree.add("A", "B");
        tree.add("A", "C");
        tree.add("C", "D");
        tree.add("E", "A");
        System.out.println(tree);
    }

    private final Map<N, N> nodeParent = new HashMap<>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<>();

    private void checkNotNull(N node, String parameterName) {
        if (node == null)
            throw new IllegalArgumentException(parameterName + " must not be null");
    }

    @Override
    public boolean add(N parent, N node) {
        checkNotNull(parent, "parent");
        checkNotNull(node, "node");

        // check for cycles
        N current = parent;
        do {
            if (node.equals(current)) {
                throw new IllegalArgumentException(" node must not be the same or an ancestor of the parent");
            }
        } while ((current = getParent(current)) != null);

        boolean added = nodeList.add(node);
        nodeList.add(parent);
        nodeParent.put(node, parent);
        return added;
    }

    @Override
    public boolean remove(N node, boolean cascade) {
        checkNotNull(node, "node");

        if (!nodeList.contains(node)) {
            return false;
        }
        if (cascade) {
            for (N child : getChildren(node)) {
                remove(child, true);
            }
        } else {
            for (N child : getChildren(node)) {
                nodeParent.remove(child);
            }
        }
        nodeList.remove(node);
        return true;
    }

    @Override
    public List<N> getRoots() {
        return getChildren(null);
    }

    @Override
    public N getParent(N node) {
        checkNotNull(node, "node");
        return nodeParent.get(node);
    }

    @Override
    public List<N> getChildren(N node) {
        List<N> children = new LinkedList<>();
        for (N n : nodeList) {
            N parent = nodeParent.get(n);
            if (node == null && parent == null) {
                children.add(n);
            } else if (node != null && parent != null && parent.equals(node)) {
                children.add(n);
            }
        }
        return children;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        dumpNodeStructure(builder, null, "- ");
        return builder.toString();
    }

    private void dumpNodeStructure(StringBuilder builder, N node, String prefix) {
        if (node != null) {
            builder.append(prefix);
            builder.append(node.toString());
            builder.append('\n');
            prefix = "  " + prefix;
        }
        for (N child : getChildren(node)) {
            dumpNodeStructure(builder, child, prefix);
        }
    }
}

Italy

I'm facing an issue when I follow this structure when I do tree.add("A", "B"); tree.add("A", "C"); tree.add("C", "D"); tree.add("E", "A"); E is a parent of A How do we go about doing this? – Salyer

Hi saNicks, there was a bug in the code above which caused the last relation not to be added. It's fixed now, and I also added non-null checks and (more important): cyclic checks which prevents violating the tree structure (adding a code or one of its ancestors as a child to itself). Thanks for the hint! – Italy

I fixed the bug if anyone is looking for a fix for that bug what you have to do is see if add method returns false and if it's false just create a temp new LinkedHashSet<N> and clone the tree's nodelist into it then u can clear the tree, add the parent node which did not get added in the previous step and then addAll of the tempNode back to the parent tree... Thanks for the structure though! – Salyer

Just remove those useless public modifiers from your interfaces. – Macedoine

how can i generate a json array out of this – Nerynesbit

how can I build a self-balanced binary tree with this interface? – Norenenorfleet

@PawanPandey even if the keywords are optional. In my point of view it's important to write them. compression over redundancy :D – Medora

Why a LinkedHashSet is needed? Is it not enough to use a HashSet? – Vagary

@Vagary the LinkedHashSet retains the insertion order of the keys, so the nodes are ordered when traversing the tree. – Italy

what if you need to introduce two or more elements that are equals()? – Barmecidal

Answer 8

No answer mentions over-simplified but working code, so here it is:

public class TreeNodeArray<T> {
    public T value;
    public final  java.util.List<TreeNodeArray<T>> kids =  new java.util.ArrayList<TreeNodeArray<T>>();
}

Chevalier

Answer 9

If you're doing whiteboard coding, an interview, or even just planning to use a tree, the verbosity of these is all a little much.

It should further be said that the reason a tree is not in there like, say, a Pair (about which the same could be said), is because you should be encapsulating your data in the class using it, and the simplest implementation looks like:

/***
/* Within the class that's using a binary tree for any reason. You could 
/* generalize with generics IFF the parent class needs different value types.
 */
private class Node {
  public String value;
  public Node[] nodes; // Or an Iterable<Node> nodes;
}

That's really it for an arbitrary width tree.

If you wanted a binary tree it's often easier to use with named fields:

private class Node { // Using package visibility is an option
  String value;
  Node left;
  Node right;
}

Or if you wanted a trie:

private class Node {
  String value;
  Map<char, Node> nodes;
}

Now you said you want

to be able to get all the children (some sort of list or array of Strings) given an input string representing a given node

That sounds like your homework.
But since I'm reasonably sure any deadline has now passed…

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class kidsOfMatchTheseDays {
 static private class Node {
   String value;
   Node[] nodes;
 }

 // Pre-order; you didn't specify.
 static public List<String> list(Node node, String find) {
   return list(node, find, new ArrayList<String>(), false);
 }

 static private ArrayList<String> list(
     Node node,
     String find,
     ArrayList<String> list,
     boolean add) {
   if (node == null) {
     return list;
   }
   if (node.value.equals(find)) {
     add = true;
   }
   if (add) {
     list.add(node.value);
   }
   if (node.nodes != null) {
     for (Node child: node.nodes) {
       list(child, find, list, add);
     }
   }
   return list;
 }

 public static final void main(String... args) {
   // Usually never have to do setup like this, so excuse the style
   // And it could be cleaner by adding a constructor like:
   //     Node(String val, Node... children) {
   //         value = val;
   //         nodes = children;
   //     }
   Node tree = new Node();
   tree.value = "root";
   Node[] n = {new Node(), new Node()};
   tree.nodes = n;
   tree.nodes[0].value = "leftish";
   tree.nodes[1].value = "rightish-leafy";
   Node[] nn = {new Node()};
   tree.nodes[0].nodes = nn;
   tree.nodes[0].nodes[0].value = "off-leftish-leaf";
   // Enough setup
   System.out.println(Arrays.toString(list(tree, args[0]).toArray()));
 }
}

This gets you use like:

$ java kidsOfMatchTheseDays leftish
[leftish, off-leftish-leaf]
$ java kidsOfMatchTheseDays root
[root, leftish, off-leftish-leaf, rightish-leafy]
$ java kidsOfMatchTheseDays rightish-leafy
[rightish-leafy]
$ java kidsOfMatchTheseDays a
[]

Parasitism

Answer 10

You can use any XML API of Java as Document and Node..as XML is a tree structure with Strings

Troche

excellent Idea, We could use in memory XML schema using dom4j + jaxen xpath to search nodes. – Gilcrest

Answer 11

Along the same lines as Gareth's answer, check out DefaultMutableTreeNode. It's not generic, but otherwise seems to fit the bill. Even though it's in the javax.swing package, it doesn't depend on any AWT or Swing classes. In fact, the source code actually has the comment // ISSUE: this class depends on nothing in AWT -- move to java.util?

Pique

Lol, how did you even came across this class? – Cabretta

Answer 12

There are a couple of tree data structures in Java, such as DefaultMutableTreeNode in JDK Swing, Tree in Stanford parser package, and other toy codes. But none of these are sufficient yet small enough for general purpose.

Java-tree project attempts to provide another general-purpose tree data structure in Java. The difference between this and others are

• Totally free. You can use it anywhere (except in your homework :P)
• Small but general enough. I put everything of the data structure in one class file, so it would be easy to copy/paste.
• Not just a toys. I am aware of dozens of Java tree codes that can only handle binary trees or limited operations. This TreeNode is much more than that. It provides different ways of visiting nodes, such as preorder, postorder, breadthfirst, leaves, path to root, etc. Moreover, iterators are provided too for the sufficiency.
• More utils will be added. I am willing to add more operations to make this project comprehensive, especially if you send a request through github.

Mien

blog.pengyifan.com/yet-another-java-tree-structure – Unhallowed

Answer 13

Since the question asks for an available data structure, a tree can be constructed from lists or arrays:

Object[] tree = new Object[2];
tree[0] = "Hello";
{
  Object[] subtree = new Object[2];
  subtree[0] = "Goodbye";
  subtree[1] = "";
  tree[1] = subtree;
}

instanceof can be used to determine whether an element is a subtree or a terminal node.

Jackshaft

Quite ugly. And doesn't work, if your data objects may be arrays respectively lists. – Dutcher

I agree that it's ugly. The Objects would either be the leaf objects (for example, Strings) or branches (represented by arrays). And it does work: that code will compile, and it creates a small tree of Strings. – Jackshaft

Answer 14

public abstract class Node {
  List<Node> children;

  public List<Node> getChidren() {
    if (children == null) {
      children = new ArrayList<>();
    }
    return chidren;
  }
}

As simple as it gets and very easy to use. To use it, extend it:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}

Parhelion

Answer 15

In the past I have just used a nested map for this. This is what I use today, it is very simple but it fits my needs. Maybe this will help another one.

import com.fasterxml.jackson.annotation.JsonValue;
import com.fasterxml.jackson.databind.ObjectMapper;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created by kic on 16.07.15.
 */
public class NestedMap<K, V> {
    private final Map root = new HashMap<>();

    public NestedMap<K, V> put(K key) {
        Object nested = root.get(key);

        if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>());
        return (NestedMap<K, V>) nested;
    }

    public Map.Entry<K,V > put(K key, V value) {
        root.put(key, value);

        return (Map.Entry<K, V>) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get();
    }

    public NestedMap<K, V> get(K key) {
        return (NestedMap<K, V>) root.get(key);
    }

    public V getValue(K key) {
        return (V) root.get(key);
    }

    @JsonValue
    public Map getRoot() {
        return root;
    }

    public static void main(String[] args) throws Exception {
        NestedMap<String, Integer> test = new NestedMap<>();
        test.put("a").put("b").put("c", 12);
        Map.Entry<String, Integer> foo = test.put("a").put("b").put("d", 12);
        test.put("b", 14);
        ObjectMapper mapper = new ObjectMapper();
        System.out.println(mapper.writeValueAsString(test));

        foo.setValue(99);
        System.out.println(mapper.writeValueAsString(test));

        System.out.println(test.get("a").get("b").getValue("d"));
    }
}

Gore

Answer 16

I wrote a small "TreeMap" class based on "HashMap" that supports adding paths:

import java.util.HashMap;
import java.util.LinkedList;

public class TreeMap<T> extends LinkedHashMap<T, TreeMap<T>> {

    public void put(T[] path) {
        LinkedList<T> list = new LinkedList<>();
        for (T key : path) {
            list.add(key);
        }
        return put(list);
    }

    public void put(LinkedList<T> path) {
        if (path.isEmpty()) {
            return;
        }
        T key = path.removeFirst();
        TreeMap<T> val = get(key);
        if (val == null) {
            val = new TreeMap<>();
            put(key, val);
        }
        val.put(path);
    }

}

It can be use to store a Tree of things of type "T" (generic), but does not (yet) support storing extra data in it's nodes. If you have a file like this:

root, child 1
root, child 1, child 1a
root, child 1, child 1b
root, child 2
root, child 3, child 3a

Then you can make it a tree by executing:

TreeMap<String> root = new TreeMap<>();
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
  root.put(scanner.nextLine().split(", "));
}

And you will get a nice tree. It should be easy to adapt to your needs.

Preexist

Answer 17

For example :

import java.util.ArrayList;
import java.util.List;



/**
 * 
 * @author X2
 *
 * @param <T>
 */
public class HisTree<T> 
{
    private Node<T> root;

    public HisTree(T rootData) 
    {
        root = new Node<T>();
        root.setData(rootData);
        root.setChildren(new ArrayList<Node<T>>());
    }

}

class Node<T> 
{

    private T data;
    private Node<T> parent;
    private List<Node<T>> children;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getParent() {
        return parent;
    }
    public void setParent(Node<T> parent) {
        this.parent = parent;
    }
    public List<Node<T>> getChildren() {
        return children;
    }
    public void setChildren(List<Node<T>> children) {
        this.children = children;
    }
}

Afterbody

Answer 18

I wrote a tree library that plays nicely with Java8 and that has no other dependencies. It also provides a loose interpretation of some ideas from functional programming and lets you map/filter/prune/search the entire tree or subtrees.

https://github.com/RutledgePaulV/prune

The implementation doesn't do anything special with indexing and I didn't stray away from recursion, so it's possible that with large trees performance will degrade and you could blow the stack. But if all you need is a straightforward tree of small to moderate depth, I think it works well enough. It provides a sane (value based) definition of equality and it also has a toString implementation that lets you visualize the tree!

Scevo

Answer 19

You can use the HashTree class included in Apache JMeter that is part of the Jakarta Project.

HashTree class is included in the package org.apache.jorphan.collections. Although this package is not released outside the JMeter project, you can get it easily:

1) Download the JMeter sources.

2) Create a new package.

3) Copy on it /src/jorphan/org/apache/jorphan/collections/ . All files except Data.java

4) Copy also /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree is ready to use.

Fagin

Answer 20

There is no specific data structure in Java which suits to your requirements. Your requirements are quite specific and for that you need to design your own data structure. Looking at your requirements anyone can say that you need some kind of n-ary tree with some specific functionality. You can design your data structure in following way:

1. Structure of the node of the tree would be like content in the node and list of children like: class Node { String value; List children;}
2. You need to retrieve the children of a given string, so you can have 2 methods 1: Node searchNode(String str), will return the node that has the same value as given input (use BFS for searching) 2: List getChildren(String str): this method will internally call the searchNode to get the node having same string and then it will create the list of all string values of children and return.
3. You will also be required to insert a string in tree. You will have to write one method say void insert(String parent, String value): this will again search the node having value equal to parent and then you can create a Node with given value and add to the list of children to the found parent.

I would suggest, you write structure of the node in one class like Class Node { String value; List children;} and all other methods like search, insert and getChildren in another NodeUtils class so that you can also pass the root of tree to perform operation on specific tree like: class NodeUtils{ public static Node search(Node root, String value){// perform BFS and return Node}

Woodpecker

Answer 21

    // TestTree.java
// A simple test to see how we can build a tree and populate it
//
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;

public class TestTree extends JFrame {

  JTree tree;
  DefaultTreeModel treeModel;

  public TestTree( ) {
    super("Tree Test Example");
    setSize(400, 300);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  }

  public void init( ) {
    // Build up a bunch of TreeNodes. We use DefaultMutableTreeNode because the
    // DefaultTreeModel can use it to build a complete tree.
    DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root");
    DefaultMutableTreeNode subroot = new DefaultMutableTreeNode("SubRoot");
    DefaultMutableTreeNode leaf1 = new DefaultMutableTreeNode("Leaf 1");
    DefaultMutableTreeNode leaf2 = new DefaultMutableTreeNode("Leaf 2");

    // Build our tree model starting at the root node, and then make a JTree out
    // of it.
    treeModel = new DefaultTreeModel(root);
    tree = new JTree(treeModel);

    // Build the tree up from the nodes we created.
    treeModel.insertNodeInto(subroot, root, 0);
    // Or, more succinctly:
    subroot.add(leaf1);
    root.add(leaf2);

    // Display it.
    getContentPane( ).add(tree, BorderLayout.CENTER);
  }

  public static void main(String args[]) {
    TestTree tt = new TestTree( );
    tt.init( );
    tt.setVisible(true);
  }
}

Arne

Please do not just dump code - explain what it does, and especially why it differs (is better) than all the other answers. – Capitulum

Answer 22

Please check the below code, where I have used Tree data structures, without using Collection classes. The code may have bugs/improvements but please use this just for reference

package com.datastructure.tree;

public class BinaryTreeWithoutRecursion <T> {

    private TreeNode<T> root;


    public BinaryTreeWithoutRecursion (){
        root = null;
    }


    public void insert(T data){
        root =insert(root, data);

    }

    public TreeNode<T>  insert(TreeNode<T> node, T data ){

        TreeNode<T> newNode = new TreeNode<>();
        newNode.data = data;
        newNode.right = newNode.left = null;

        if(node==null){
            node = newNode;
            return node;
        }
        Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
        queue.enque(node);
        while(!queue.isEmpty()){

            TreeNode<T> temp= queue.deque();
            if(temp.left!=null){
                queue.enque(temp.left);
            }else
            {
                temp.left = newNode;

                queue =null;
                return node;
            }
            if(temp.right!=null){
                queue.enque(temp.right);
            }else
            {
                temp.right = newNode;
                queue =null;
                return node;
            }
        }
        queue=null;
        return node; 


    }

    public void inOrderPrint(TreeNode<T> root){
        if(root!=null){

            inOrderPrint(root.left);
            System.out.println(root.data);
            inOrderPrint(root.right);
        }

    }

    public void postOrderPrint(TreeNode<T> root){
        if(root!=null){

            postOrderPrint(root.left);

            postOrderPrint(root.right);
            System.out.println(root.data);
        }

    }

    public void preOrderPrint(){
        preOrderPrint(root);
    }


    public void inOrderPrint(){
        inOrderPrint(root);
    }

    public void postOrderPrint(){
        inOrderPrint(root);
    }


    public void preOrderPrint(TreeNode<T> root){
        if(root!=null){
            System.out.println(root.data);
            preOrderPrint(root.left);
            preOrderPrint(root.right);
        }

    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTreeWithoutRecursion <Integer> ls=  new BinaryTreeWithoutRecursion <>();
        ls.insert(1);
        ls.insert(2);
        ls.insert(3);
        ls.insert(4);
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        //ls.preOrderPrint();
        ls.inOrderPrint();
        //ls.postOrderPrint();

    }

}

Strickland

"without using Collection classes" Ah? So where the Queue class comes from? And as said above, it is a binary tree, failing at first requirement (any number of children nodes). – Earthly

Answer 23

You can use TreeSet class in java.util.*. It is working like Binary search tree, so it is already sorted. TreeSet class implements Iterable, Collection and Set interfaces. You can traverse through the tree with iterator like a set.

TreeSet<String> treeSet = new TreeSet<String>();
Iterator<String> it  = treeSet.Iterator();
while(it.hasNext()){
...
}

You can check, Java Doc and some other .

Clynes

Answer 24

I had a realproblem with all these aproaches.

I was using the "MappedTreeStructure" implementation. Thats implementation reoganizes the Tree very well and does not contain Nodes "replica".

But does not provides a hierarchical aproches.

See those Output with problem!

MutableTree<String> tree = new MappedTreeStructure<>();

        tree.add("0", "1");
        tree.add("0", "2");
        tree.add("0", "3");
        tree.add("0", "4");
        tree.add("0", "5");

        tree.add("2", "3");
        tree.add("2", "5");

        tree.add("1", "2");
        tree.add("1", "3");
        tree.add("1", "5");

        System.out.println(
                tree.toString()
        );

Which output: (wrong)

-  0
  -  1
    -  2
    -  3
    -  5
  -  4

And this: (correct)

tree = new MappedTreeStructure<>();

        tree.add("0", "1");
        tree.add("0", "2");
        tree.add("0", "3");
        tree.add("0", "4");
        tree.add("0", "5");

        tree.add("1", "2");
        tree.add("1", "3");
        tree.add("1", "5");

        tree.add("2", "3");
        tree.add("2", "5");

        System.out.println(
                tree.toString()
        );

Correct Output:

-  0
  -  1
    -  2
      -  3
      -  5
  -  4

So! I created another implementation for apreciation. PLEASE give some advices and Feedback!

package util;

import java.util.HashMap;
import java.util.Map;

public class Node<N extends Comparable<N>> {

    public final Map<N, Node<N>> parents = new HashMap<>();
    public final N value;
    public final Map<N, Node<N>> children = new HashMap<>();

    public Node(N value) {
        this.value = value;
    }
}

package util;

import java.util.*;
import java.util.stream.Collectors;

public class HierarchyTree<N extends Comparable<N>> {

    protected final Map<N, Node<N>> nodeList = new HashMap<>();

    public static <T extends Comparable<T>> Node<T> state(Map<T, Node<T>> nodeList, T node) {
        Node<T> tmp = nodeList.getOrDefault(node, new Node<>(node));
        nodeList.putIfAbsent(node, tmp);
        return tmp;
    }

    public static <T extends Comparable<T>> Node<T> state(Map<T, Node<T>> nodeList, Node<T> node) {
        Node<T> tmp = nodeList.getOrDefault(node.value, node);
        nodeList.putIfAbsent(node.value, tmp);
        return tmp;
    }

    public Node<N> state(N child) {
        return state(nodeList, child);
    }

    public Node<N> stateChild(N parent, N child) {
        Node<N> pai = state(parent);
        Node<N> filho = state(child);
        state(pai.children, filho);
        state(filho.parents, pai);
        return filho;
    }

    public List<Node<N>> addChildren(List<N> children) {
        List<Node<N>> retorno = new LinkedList<>();
        for (N child : children) {
            retorno.add(state(child));
        }
        return retorno;
    }

    public List<Node<N>> addChildren(N parent, List<N> children) {
        List<Node<N>> retorno = new LinkedList<>();
        for (N child : children) {
            retorno.add(stateChild(parent, child));
        }
        return retorno;
    }

    public List<Node<N>> addChildren(N parent, N... children) {
        return addChildren(parent, Arrays.asList(children));
    }

    public List<Node<N>> getRoots() {
        return nodeList.values().stream().filter(value -> value.parents.size() == 0).collect(Collectors.toList());
    }

    @Override
    public String toString() {
        return deepPrint("- ");
    }

    public String deepPrint(String prefix) {
        StringBuilder builder = new StringBuilder();
        deepPrint(builder, prefix, "", getRoots());
        return builder.toString();
    }

    protected void deepPrint(StringBuilder builder, String prefix, String sep, List<Node<N>> node) {
        for (Node<N> item : node) {
            builder.append(sep).append(item.value).append("\n");
            deepPrint(builder, prefix, sep + prefix, new ArrayList<>(item.children.values()));
        }
    }

    public SortedMap<Long, Set<N>> tree() {
        SortedMap<Long, Set<N>> tree = new TreeMap<>();
        tree(0L, tree, getRoots());
        return tree;
    }

    protected void tree(Long i, SortedMap<Long, Set<N>> tree, List<Node<N>> roots) {
        for (Node<N> node : roots) {
            Set<N> tmp = tree.getOrDefault(i, new HashSet<>());
            tree.putIfAbsent(i, tmp);
            tmp.add(node.value);
            tree(i + 1L, tree, new ArrayList<>(node.children.values()));
        }
    }

    public void prune() {
        Set<N> nodes = new HashSet<>();
        SortedMap<Long, Set<N>> tree = tree();
        List<Long> treeInverse = tree.keySet().stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList());
        for (Long treeItem : treeInverse) {
            for (N n : tree.get(treeItem)) {
                Map<N, Node<N>> children = nodeList.get(n).children;
                for (N node : nodes) {
                    children.remove(node);
                }
                nodes.addAll(children.keySet());
            }
        }
    }

    public static void main(String[] args) {
        HierarchyTree<Integer> tree = new HierarchyTree<>();
        tree.addChildren(Arrays.asList(1, 2, 3, 4, 5));
        tree.addChildren(1, Arrays.asList(2, 3, 5));
        tree.addChildren(2, Arrays.asList(3, 5));
        tree.prune();
        System.out.println(tree);

        tree = new HierarchyTree<>();
        tree.addChildren(Arrays.asList(1, 2, 3, 4, 5));
        tree.addChildren(2, Arrays.asList(3, 5));
        tree.addChildren(1, Arrays.asList(2, 3, 5));
        tree.prune();
        System.out.println(tree);
    }
}

Which output always correct:

1
- 2
- - 3
- - 5
4

1
- 2
- - 3
- - 5
4

Burford

Answer 25

import java.util.Collection;
import java.util.LinkedList;
import java.util.function.BiConsumer;
import java.util.function.Function;

/**
 * @author changjin wei(魏昌进)
 * @since 2021/7/15
 */
public class TreeUtils {

    private TreeUtils() {
    }

    /**
     * @param collection this is a collection of elements
     * @param getId this is a getId Function
     * @param getParentId this is a getParentId Function
     * @param setNode this is a setNode BiConsumer
     * @param <E> the type of elements in this collection
     * @param <R> the type of the result of the function
     *
     * @return Collection
     */
    public static <E, R> Collection<E> tree(Collection<E> collection, Function<E, R> getId, Function<E, R> getParentId, BiConsumer<E, Collection<E>> setNode) {
        Collection<E> root = new LinkedList<>();
        for (E node : collection) {
            R parentId = getParentId.apply(node);
            R id = getId.apply(node);
            Collection<E> elements = new LinkedList<>();
            boolean isParent = true;
            for (E element : collection) {
                if (id.equals(getParentId.apply(element))) {
                    elements.add(element);
                }
                if (isParent && getId.apply(element).equals(parentId)) {
                    isParent = false;
                }
            }
            if (isParent) {
                root.add(node);
            }
            setNode.accept(node, elements);
        }
        return root;
    }
}

Priestcraft

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Dibb

Answer 26

Simple example:

public class ArbrePlaner {

public static void main(String[] args) {
    ArbrePlaner ll = new ArbrePlaner();
    
    ll.add(1,"A");
    ll.add(2,"B");
    ll.add(1,"C");
    ll.add(3,"D");
    ll.add(1,"Z");
    
    for(int i = 0; i < ll.size; i++){
    //  System.out.println(ll.isIdExist(i));
        System.out.println("-----------------");
        System.out.println(ll.getIdAt(i)+" :");
        linkedList lst = ll.getListDataById(ll.getIdAt(i));
        for(int j = 0; j < lst.size; j++){
            System.out.println(lst.getElementAt(j));
        }
    }
    
    
    
    
}

private int size;
private Noeud root;

public Noeud add(long Id, Object data){
    if(isIdExist(Id)){
        Noeud nd = getNoeudId(Id);
        nd.add(data);
        return nd;
    }else{
        Noeud nd = new Noeud(Id, data, this.root);
        this.root = nd;
        this.size++;
        return nd;
    }
}
 
 public Object getDataById(long Id, int x){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId() == Id){
                return thisNode.getLl().getElementAt(x);
            }
            thisNode = thisNode.getNextNoeud();
        }
        return null;
    }
 
 public long getIdAt(int x){
        if(size >= x){
            Noeud nd = this.root;
            for(int i = 0; i<x; i++)try {nd = nd.getNextNoeud();} catch (Exception e) {return -1;}
            return nd.getId();
        }
            return -1;
    }
 
 public linkedList getListDataById(long Id){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId() == Id){
                return thisNode.getLl();
            }
            thisNode = thisNode.getNextNoeud();
        }
        return null;
    }
 
public boolean deleteById(long id){
    Noeud thisNode = this.root;
    Noeud prevNode = null;
    
    while(thisNode != null){
        if(thisNode.getId() == id){
            prevNode.setNextNoeud(thisNode.getNextNoeud());
            this.setSize(this.getSize()-1);
            return true;
        }
        prevNode = thisNode;
        thisNode = thisNode.getNextNoeud();
    }
    return false;
}

 public boolean isIdExist(long Id){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId()== Id){
                return true;
            }
            thisNode = thisNode.getNextNoeud();
        }
        return false;
    }

 public boolean isDataExist(long Id, Object data){
     if(isIdExist(Id)){
         Noeud thisNode = this.root;
            while(thisNode!=null){
                if(thisNode.getId() == Id){
                    linkedList ll = thisNode.getLl();
                    long x = ll.hashCode();
                    long y = data.hashCode();
                    if(x==y) return true;
                }
                thisNode = thisNode.getNextNoeud();
            }
     }
     return false;
 }
 
 public Noeud getNoeudId(long Id){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId() == Id){
                return thisNode;
            }
            thisNode = thisNode.getNextNoeud();
        }
        return null;
    }

public ArbrePlaner() {
    this.root = root;
}

public ArbrePlaner(Noeud root) {
    this.root = root;
}

public ArbrePlaner(int size, Noeud root) {
    this.size = size;
    this.root = root;
}

public int getSize() {
    return size;
}

public void setSize(int size) {
    this.size = size;
}

public Noeud getRoot() {
    return root;
}

public void setRoot(Noeud root) {
    this.root = root;
}

private class Noeud{
    private long id;
    private Noeud nextNoeud;
    private linkedList Ll;
    
    public void add(Object data){
        Ll.add(data);
    }
    
    public Noeud(long id, Object data ,Noeud nextNoeud){
        this.id = id;
        this.nextNoeud = nextNoeud;
        Ll = new linkedList();
        Ll.add(data);
    }
    
    public long getId() {
        return id;
    }
    
    public Noeud(Object data){
        Ll.add(data);
    }
            
    public void setId(long id) {
        this.id = id;
    }
    public Noeud getNextNoeud() {
        return nextNoeud;
    }
    public void setNextNoeud(Noeud nextNoeud) {
        this.nextNoeud = nextNoeud;
    }
    public linkedList getLl() {
        return Ll;
    }
    public void setLl(linkedList ll) {
        Ll = ll;
    }
}
}

Daisy

Answer 27

Custom Tree implement of Tree without using the Collection framework. It contains different fundamental operation needed in Tree implementation.

class Node {

    int data;
    Node left;
    Node right;

    public Node(int ddata, Node left, Node right) {
        this.data = ddata;
        this.left = null;
        this.right = null;      
    }

    public void displayNode(Node n) {
        System.out.print(n.data + " "); 
    }

}

class BinaryTree {

    Node root;

    public BinaryTree() {
        this.root = null;
    }

    public void insertLeft(int parent, int leftvalue ) {
        Node n = find(root, parent);
        Node leftchild = new Node(leftvalue, null, null);
        n.left = leftchild;
    }

    public void insertRight(int parent, int rightvalue) {
        Node n = find(root, parent);
        Node rightchild = new Node(rightvalue, null, null);
        n.right = rightchild;
    }

    public void insertRoot(int data) {
        root = new Node(data, null, null);
    }

    public Node getRoot() {
        return root;
    }

    public Node find(Node n, int key) {     
        Node result = null;

        if (n == null)
            return null;

        if (n.data == key)
            return n;

        if (n.left != null)
            result = find(n.left, key);

        if (result == null)
            result = find(n.right, key);

        return result;
    } 

    public int getheight(Node root){
        if (root == null)
            return 0;

        return Math.max(getheight(root.left), getheight(root.right)) + 1; 
    }

    public void printTree(Node n) {     
        if (n == null)
            return;

        printTree(n.left);
        n.displayNode(n);
        printTree(n.right);             
    }

}

Allyl

That's a binary tree, it fails at the first requirement of the OP... – Earthly