Java tree data-structure?

436

185

Is there a good available (standard Java) data structure to represent a tree in Java?

Specifically I need to represent the following:

  • The tree at any node can have an arbitrary number of children
  • Each node (after the root) is just a String (whose children are also Strings)
  • I need to be able to get all the children (some sort of list or array of Strings) given an input string representing a given node

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

ikl

Posted 2010-08-19T13:53:13.363

Reputation: 2 189

Question was closed 2018-08-09T19:39:31.990

2

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 https://github.com/diffplug/durian/

– Ned Twigg – 2015-05-14T18:39:59.550

You may use this API: https://sourceforge.net/p/treeds4j

– Mohamed Ennahdi El Idrissi – 2018-07-20T09:57:43.623

Answers

272

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.

jjnguy

Posted 2010-08-19T13:53:13.363

Reputation: 106 008

19I 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. – jvdbogae – 2012-10-09T07:43:25.127

1

to save 40 minutes use more completed sample here

– Grzegorz Dev – 2013-07-05T13:33:49.407

6You may want a parent field too if you want to get the path from a child node. – Ultimate Gobblement – 2010-08-19T13:57:51.533

1True, if you wanna be able to go up the tree you need a parent ref. – jjnguy – 2010-08-19T14:01:28.897

277Strictly speaking the Tree class is not necessary, because every Node can in itself be seen as a tree. – Joachim Sauer – 2010-08-19T14:02:05.193

32@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. – jjnguy – 2010-08-19T14:03:48.503

21@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. – Joachim Sauer – 2010-08-19T14:05:00.413

@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. – jjnguy – 2010-08-19T14:10:51.870

2@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. – Joachim Sauer – 2010-08-19T14:34:32.880

3@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. – jjnguy – 2010-08-19T15:04:46.267

2@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. – El Marce – 2014-09-04T09:29:35.730

6@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. – Joachim Sauer – 2014-09-04T12:08:40.993

74@Joa A four-years-older me agrees with you completely. Nix the tree class. – jjnguy – 2014-09-05T13:19:56.180

2Separate 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? – Barney – 2014-12-17T15:47:07.440

3@Barney 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. – scottyseus – 2016-01-04T19:49:14.677

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))]. – Barney – 2016-01-14T08:28:08.303

2@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) – Amit Gold – 2016-05-07T12:11:25.613

102

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

Grzegorz Dev

Posted 2010-08-19T13:53:13.363

Reputation: 2 112

1Just 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. – d4v1dv00 – 2015-04-07T15:03:40.363

as of 2016, the link contains no source files or downloads – Sharon Ben Asher – 2017-01-03T11:59:16.003

1In 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. – HopeKing – 2017-10-07T08:08:16.690

I would use a Set for the children. – DPM – 2018-06-17T18:03:47.983

95

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'.

Gareth Davis

Posted 2010-08-19T13:53:13.363

Reputation: 23 599

128I 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. – jasop – 2012-07-26T05:50:02.497

43I think bad coding practice is a little harsh. – Gareth Davis – 2012-07-26T08:07:10.557

46javax.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. – lbalazscs – 2012-08-21T12:38:37.607

4Yeah 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. – Ultimate Gobblement – 2010-08-19T14:54:17.507

3Good way to cope with that is to create a couple of static methods newModel() and newNode() and then static import them. – Gareth Davis – 2010-08-23T11:04:06.497

@jasop I know this is very late to comment. But I agree to your point using libraries can be a bad practise for beginners. – Lokesh – 2017-05-17T14:22:30.340

1

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 http://www.oracle.com/technetwork/java/embedded/resources/tech/compact-profiles-overview-2157132.html). 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...

– Tom Seidel – 2017-11-01T15:37:17.197

@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. – Gareth Davis – 2017-11-03T11:59:31.687

1"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... – Fran Marzoa – 2018-10-18T08:26:28.713

@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 :( – Gareth Davis – 2018-10-19T11:03:28.263

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. – Fran Marzoa – 2018-10-19T12:35:02.740

40

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;
  }
}

MountainX

Posted 2010-08-19T13:53:13.363

Reputation: 3 148

3How would DFS be implemented on a tree created using this class object? – leba-lev – 2012-03-07T21:05:06.330

2How would removing a leaf be implemented using this class? – ghedas – 2012-08-05T05:33:06.837

1What would the head field be used for? – Acour83 – 2014-09-03T02:25:41.077

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. – Disasterkid – 2018-08-13T08:59:22.927

22

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.

Vivin Paliath

Posted 2010-08-19T13:53:13.363

Reputation: 71 859

3I 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! – jasop – 2012-07-26T05:48:43.840

16

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.

PaulJWilliams

Posted 2010-08-19T13:53:13.363

Reputation: 16 257

12

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 {
    public List<N> getRoots ();
    public N getParent (N node);
    public List<N> getChildren (N node);
}

public interface MutableTree <N extends Serializable> extends Tree<N> {
    public boolean add (N parent, N node);
    public 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 MappedTreeStructure<N extends Serializable> implements MutableTree<N> {

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<String>();
        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<N, N>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>();

    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<N>();
        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);
        }
    }
}

Peter Walser

Posted 2010-08-19T13:53:13.363

Reputation: 10 242

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? – saNiks – 2016-04-29T15:54:38.303

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! – Peter Walser – 2016-04-29T16:39:02.380

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! – saNiks – 2016-04-30T19:51:48.893

Just remove those useless public modifiers from your interfaces. – Hamedz – 2016-07-29T19:06:43.753

how can i generate a json array out of this – Pawan Pandey – 2016-08-08T10:11:12.507

9

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

Raja Nagendra Kumar

Posted 2010-08-19T13:53:13.363

Reputation: 451

4excellent Idea, We could use in memory XML schema using dom4j + jaxen xpath to search nodes. – Ben Rhouma Zied – 2014-05-30T21:42:18.360

9

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>>();
}

peenut

Posted 2010-08-19T13:53:13.363

Reputation: 2 322

6

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.

Yifan Peng

Posted 2010-08-19T13:53:13.363

Reputation: 77

http://blog.pengyifan.com/yet-another-java-tree-structure/ – MagGGG – 2018-10-31T20:52:48.437

6

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?

Mark

Posted 2010-08-19T13:53:13.363

Reputation: 999

5

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
[]

dlamblin

Posted 2010-08-19T13:53:13.363

Reputation: 26 400

4

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.

Olathe

Posted 2010-08-19T13:53:13.363

Reputation: 1 702

1Quite ugly. And doesn't work, if your data objects may be arrays respectively lists. – user686249 – 2015-06-12T16:40:39.357

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. – Olathe – 2016-05-09T08:55:48.410

4

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;
  ...
}

bretter

Posted 2010-08-19T13:53:13.363

Reputation: 175

2

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;
    }
}

ron

Posted 2010-08-19T13:53:13.363

Reputation: 8 008

2

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.

mevdschee

Posted 2010-08-19T13:53:13.363

Reputation: 755

1

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();

    }

}

Amit Mathur

Posted 2010-08-19T13:53:13.363

Reputation: 11

"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). – PhiLho – 2014-08-07T22:30:25.550

1

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);             
    }

}

Shivam Verma

Posted 2010-08-19T13:53:13.363

Reputation: 422

5That's a binary tree, it fails at the first requirement of the OP... – PhiLho – 2014-08-07T22:26:41.423

1

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}

aman rastogi

Posted 2010-08-19T13:53:13.363

Reputation: 76

1

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"));
    }
}

KIC

Posted 2010-08-19T13:53:13.363

Reputation: 2 723

1

    // 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);
  }
}

Tony Narloch

Posted 2010-08-19T13:53:13.363

Reputation: 11

1

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!

RutledgePaulV

Posted 2010-08-19T13:53:13.363

Reputation: 1 653

1

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 .

Oguz

Posted 2010-08-19T13:53:13.363

Reputation: 983

1

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.

David

Posted 2010-08-19T13:53:13.363

Reputation: 1 529