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

User · Answer

No answer mentions over-simplified but working code  so here it is   public class TreeNodeArray lt T gt        public T value      public final  java util List lt TreeNodeArray lt T gt  gt  kids    new java util ArrayList lt TreeNodeArray lt T gt  gt

User · Answer

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

User · Answer

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 lt Node gt  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 lt char  Node gt  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 lt String gt  list Node node  String find       return list node  find  new ArrayList lt String gt     false        static private ArrayList lt String gt  list       Node node       String find       ArrayList lt String gt  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

User · Answer

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

User · Answer

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

User · Answer

public abstract class Node     List lt Node gt  children     public List lt Node gt  getChidren         if  children    null          children   new ArrayList lt  gt               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

User · Answer

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

User · Answer

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

User · Answer

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 lt K  V gt        private final Map root   new HashMap lt  gt          public NestedMap lt K  V gt  put K key            Object nested   root get key            if  nested    null      nested instanceof NestedMap   root put key  nested   new NestedMap lt  gt              return  NestedMap lt K  V gt   nested             public Map Entry lt K V  gt  put K key  V value            root put key  value            return  Map Entry lt K  V gt   root entrySet   stream   filter e - gt    Map Entry  e  getKey   equals key   findFirst   get               public NestedMap lt K  V gt  get K key            return  NestedMap lt K  V gt   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 lt String  Integer gt  test   new NestedMap lt  gt             test put  a   put  b   put  c   12           Map Entry lt String  Integer gt  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

User · Answer

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

User · Answer

Here    public class Tree lt T gt        private Node lt T gt  root       public Tree T rootData            root   new Node lt T gt             root data   rootData          root children   new ArrayList lt Node lt T gt  gt                public static class Node lt T gt            private T data          private Node lt T gt  parent          private List lt Node lt T gt  gt  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

User · Answer

Yet another tree structure   public class TreeNode lt T gt  implements Iterable lt TreeNode lt T gt  gt         T data      TreeNode lt T gt  parent      List lt TreeNode lt T gt  gt  children       public TreeNode T data            this data   data          this children   new LinkedList lt TreeNode lt T gt  gt                public TreeNode lt T gt  addChild T child            TreeNode lt T gt  childNode   new TreeNode lt T gt  child           childNode parent   this          this children add childNode           return childNode                other features          Sample usage   TreeNode lt String gt  root   new TreeNode lt String gt   root          TreeNode lt String gt  node0   root addChild  node0        TreeNode lt String gt  node1   root addChild  node1        TreeNode lt String gt  node2   root addChild  node2                  TreeNode lt String gt  node20   node2 addChild null           TreeNode lt String gt  node21   node2 addChild  node21                          TreeNode lt String gt  node210   node20 addChild  node210                        BONUS See fully-fledged tree with    iterator searching Java C    https   github com gt4dev yet-another-tree-structure

User · Answer

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  lt T gt         private TreeNode lt T gt  root        public BinaryTreeWithoutRecursion             root   null              public void insert T data           root  insert root  data               public TreeNode lt T gt   insert TreeNode lt T gt  node  T data             TreeNode lt T gt  newNode   new TreeNode lt  gt             newNode data   data          newNode right   newNode left   null           if node  null               node   newNode              return node                    Queue lt TreeNode lt T gt  gt  queue   new Queue lt TreeNode lt T gt  gt             queue enque node           while  queue isEmpty                  TreeNode lt T gt  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 lt T gt  root           if root  null                inOrderPrint root left               System out println root data               inOrderPrint root right                         public void postOrderPrint TreeNode lt T gt  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 lt T gt  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  lt Integer gt  ls   new BinaryTreeWithoutRecursion  lt  gt             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

User · Answer

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

User · Answer

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  lt N extends Serializable gt  extends Serializable       List lt N gt  getRoots         N getParent  N node       List lt N gt  getChildren  N node       Mutable tree structure  allows to add and remove nodes    public interface MutableTree  lt N extends Serializable gt  extends Tree lt N gt        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 lt File gt          Override     public List lt File gt  getRoots             return Arrays stream File listRoots    collect Collectors toList                 Override     public File getParent File node            return node getParentFile                Override     public List lt File gt  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 lt N extends Serializable gt  implements MutableTree lt N gt         public static void main String   args             MutableTree lt String gt  tree   new MappedTreeStructure lt  gt             tree add  A    B            tree add  A    C            tree add  C    D            tree add  E    A            System out println tree              private final Map lt N  N gt  nodeParent   new HashMap lt  gt         private final LinkedHashSet lt N gt  nodeList   new LinkedHashSet lt  gt          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 lt N gt  getRoots             return getChildren null               Override     public N getParent N node            checkNotNull node   node            return nodeParent get node               Override     public List lt N gt  getChildren N node            List lt N gt  children   new LinkedList lt  gt             for  N n   nodeList                N parent   nodeParent get n               if  node    null  amp  amp  parent    null                    children add n                 else if  node    null  amp  amp  parent    null  amp  amp  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

User · Answer

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

User · Answer

I wrote a small  TreeMap  class based on  HashMap  that supports adding paths   import java util HashMap  import java util LinkedList   public class TreeMap lt T gt  extends LinkedHashMap lt T  TreeMap lt T gt  gt         public void put T   path            LinkedList lt T gt  list   new LinkedList lt  gt             for  T key   path                list add key                     return put list              public void put LinkedList lt T gt  path            if  path isEmpty                  return                    T key   path removeFirst            TreeMap lt T gt  val   get key           if  val    null                val   new TreeMap lt  gt                 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 lt String gt  root   new TreeMap lt  gt     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

User · Answer

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 lt String gt  treeSet   new TreeSet lt String gt     Iterator lt String gt  it    treeSet Iterator    while it hasNext             You can check  Java Doc and some other

User · Answer

public class Tree       private List lt Tree gt  leaves   new LinkedList lt Tree gt         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

User · Answer

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

User · Answer

What about this   import java util ArrayList  import java util Collection  import java util HashMap            author ycoppel google com  Yohann Coppel            param  lt T gt               Object s type in the tree     public class Tree lt T gt       private T head     private ArrayList lt Tree lt T gt  gt  leafs   new ArrayList lt Tree lt T gt  gt        private Tree lt T gt  parent   null     private HashMap lt T  Tree lt T gt  gt  locate   new HashMap lt T  Tree lt T gt  gt        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 lt T gt  addLeaf T leaf        Tree lt T gt  t   new Tree lt T gt  leaf       leafs add t       t parent   this      t locate   this locate      locate put leaf  t       return t         public Tree lt T gt  setAsParent T parentRoot        Tree lt T gt  t   new Tree lt T gt  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 lt T gt  getTree T element        return locate get element          public Tree lt T gt  getParent         return parent         public Collection lt T gt  getSuccessors T root        Collection lt T gt  successors   new ArrayList lt T gt         Tree lt T gt  tree   getTree root       if  null    tree          for  Tree lt T gt  leaf   tree leafs            successors add leaf head                     return successors         public Collection lt Tree lt T gt  gt  getSubTrees         return leafs         public static  lt T gt  Collection lt T gt  getSuccessors T of  Collection lt Tree lt T gt  gt  in        for  Tree lt T gt  tree   in          if  tree locate containsKey of             return tree getSuccessors of                     return new ArrayList lt T gt             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  lt  increment    i          inc   inc                  s   inc   head      for  Tree lt T gt  child   leafs          s      n    child printTree increment   indent             return s

User · Answer

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

User · Answer

For example     import java util ArrayList  import java util List                 author X2        param  lt T gt      public class HisTree lt T gt         private Node lt T gt  root       public HisTree T rootData                 root   new Node lt T gt             root setData rootData           root setChildren new ArrayList lt Node lt T gt  gt                class Node lt T gt          private T data      private Node lt T gt  parent      private List lt Node lt T gt  gt  children       public T getData             return data            public void setData T data            this data   data            public Node lt T gt  getParent             return parent            public void setParent Node lt T gt  parent            this parent   parent            public List lt Node lt T gt  gt  getChildren             return children            public void setChildren List lt Node lt T gt  gt  children            this children   children

User · Answer

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

[java] How to implement a tree data-structure in Java?

Examples related to java

Examples related to data-structures

Examples related to tree