Java tree data-structure?

Question

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 (who's children are also strings)
• I need to be able to get all the children (some sort of list / 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). Thanks

Answer 1

Not as far as I can tell, but try this.

Answer 2

Here:

public class Tree {
    private Node root;

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

    private class Node {
        private String data;
        private Node parent;
        private List<Node> children;
    }
}

That is a basic tree structure that contains Strings. 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.

Answer 3

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

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

Answer 4

Here is a binary tree that you might want to adapt.

No one else mentioned using generics, so I will.

Answer 5

public class Tree {
    private List<Tree> Children = 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.

Answer 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?

Answer 7

What about this? (BTW, no matter what I seem to try, I cannot paste code that the site's code formatter will process properly. Sorry about that.)

/*

* Copyright 2007 Google Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */

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

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

private T head;

private ArrayList> leafs = new ArrayList>();

private Tree parent = null;

private HashMap> locate = new HashMap>();

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 addLeaf(T leaf) { Tree t = new Tree(leaf); leafs.add(t); t.parent = this; t.locate = this.locate; locate.put(leaf, t); return t; }

public Tree setAsParent(T parentRoot) { Tree t = new Tree(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 getTree(T element) { return locate.get(element); }

public Tree getParent() { return parent; }

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

public Collection> getSubTrees() { return leafs; }

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

@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 child : leafs) { s += "\n" + child.printTree(increment + indent); } return s; } }