Yet another Java tree structure

By | September 21, 2013

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.

Contribution

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

TreeNode

A TreeNode may have at most one parent and 0 or more children. It provides operations for examining and modifying a node’s parent and children and also operations for examining the tree that the node is a part of. A node’s tree is the set of all nodes that can be reached by starting at the node and following all the possible links to parents and children. A node with no parent is the root of its tree; a node with no children is a leaf. A tree may consist of many subtrees, each node acting as the root for its own subtree.

A TreeNode provides iterator for efficiently traversing a tree or subtree in various orders or for following the path between two nodes. A TreeNode may also hold a reference to a user object, the use of which is left to the user. Asking a TreeNode for its string representation with toString() returns the string representation of its user object.

This is not a thread safe class. If you intend to use a TreeNode (or a tree of TreeNodes) in more than one thread, you need to do your own synchronizing. A good convention to adopt is synchronizing on the root node of a tree.

Most source code is copied from DefaultMutableTreeNode by Rob Davis, and modified for general purposes.

Print TreeNode

This project provides two formats to print out a tree structure. One is a human readable format (TreeString), like

└ a
  ├ b
  ├ c
  │ ├ e
  │ └ f
  └ d

The other is Penn Treebank format (PtbString), like

(a b (c (e f) d)

The following code snippet shows how to print a TreeNode.

System.out.println(PtbString.toString(treeNode));
System.out.println(TreeString.toString(treeNode));

Other utils

coming soon…

Some frequently used utils will be provided, such as lowest common ancestor, tregrep, etc.

7 thoughts on “Yet another Java tree structure

  1. evensonic

    Thanks for the post. I’d like to look at the project’s API, but I don’t see any link or the name of the project 🙂

    Reply
  2. Combot

    >Totally free. You can use it anywhere.
    You say this, but you are using the GPLv3 so this mostly excludes commercial usage, would you consider BSD or Apache as well?

    Reply
  3. Yu Liu

    I don’t think there’s much generality on tree/tree-like structures. In many cases TREE is just used to represent the image of computation such as tree-reduction, but not used as a data structure. In other many cases, when we need a tree as a data structure, the computation is usually very special that only one (or a few) priory/innate operation is important.
    General implementations usually lose efficiency in such cases, like kd-tree, binary search tree, some hierarchical structures etc. In general, when we need a tree data structure, only a special tree is necessary.

    Reply
  4. Pingback: How to return an subclass with generics | Guru

Leave a Reply

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