Tree implementation in Java root parents and children

Question

I need to create a tree structure similar as the attached image in Java  I ve found some questions related to this one but I haven t found a convincing and well explained response  The application business consists in food super categories  main courses  desserts and other   Each of these categories can have parent items or children items and so on

User · Answer

This tree is not a binary tree  so you need an array of the children elements  like List   public Node Object data  List lt Node gt  children        this data   data      this children   children      Then create the instances

User · Answer

Accepted answer throws a java lang StackOverflowError when calling the setParent or addChild methods   Here s a slightly simpler implementation without those bugs   public class MyTreeNode lt T gt       private T data   null      private List lt MyTreeNode gt  children   new ArrayList lt  gt         private MyTreeNode parent   null       public MyTreeNode T data            this data   data             public void addChild MyTreeNode child            child setParent this           this children add child              public void addChild T data            MyTreeNode lt T gt  newChild   new MyTreeNode lt  gt  data           this addChild newChild              public void addChildren List lt MyTreeNode gt  children            for MyTreeNode t   children                t setParent this                     this children addAll children              public List lt MyTreeNode gt  getChildren             return children             public T getData             return data             public void setData T data            this data   data             private void setParent MyTreeNode parent            this parent   parent             public MyTreeNode getParent             return parent            Some examples   MyTreeNode lt String gt  root   new MyTreeNode lt  gt   Root     MyTreeNode lt String gt  child1   new MyTreeNode lt  gt   Child1    child1 addChild  Grandchild1    child1 addChild  Grandchild2     MyTreeNode lt String gt  child2   new MyTreeNode lt  gt   Child2    child2 addChild  Grandchild3     root addChild child1   root addChild child2   root addChild  Child3     root addChildren Arrays asList          new MyTreeNode lt  gt   Child4            new MyTreeNode lt  gt   Child5            new MyTreeNode lt  gt   Child6        for MyTreeNode node   root getChildren          System out println node getData

User · Answer

Here is my implementation in java for your requirement  In the treeNode class i used generic array to store the tree data  we can also use arraylist or dynamic array to store the tree value   public class TreeNode lt T gt       private T value   null     private TreeNode   childrens   new TreeNode 100      private int childCount   0       TreeNode T value            this value   value             public TreeNode addChild T value            TreeNode newChild   new TreeNode value  this           childrens childCount      newChild          return newChild             static void traverse TreeNode obj            if  obj    null                for  int i   0  i  lt  obj childCount  i                      System out println obj childrens i  value                   traverse obj childrens i                                    return             void printTree TreeNode obj            System out println obj value           traverse obj             And the client class for the above implementation   public class Client       public static void main String   args            TreeNode menu   new TreeNode  Menu            TreeNode item   menu addChild  Starter                item   item addChild  Veg                    item addChild  Paneer Tikka                    item addChild  Malai Paneer Tikka                item   item addChild  Non-veg                    item addChild  Chicken Tikka                    item addChild  Malai Chicken Tikka            item   menu addChild  Main Course                item   item addChild  Veg                    item addChild  Mili Juli Sabzi                    item addChild  Aloo Shimla Mirch                item   item addChild  Non-veg                    item addChild  Chicken Do Pyaaza                    item addChild  Chicken Chettinad            item   menu addChild  Desserts                    item   item addChild  Cakes                            item addChild  Black Forest                            item addChild  Black Current                    item   item addChild  Ice Creams                            item addChild  chocolate                            item addChild  Vanilla            menu printTree menu             OUTPUT  Menu                                                                      Starter                                                                  Veg                                                                 Paneer Tikka                                                         Malai Paneer Tikka                                                     Non-veg                                                               Chicken Tikka                                                       Malai Chicken Tikka                                                  Main Course                                                       Veg                                                              Mili Juli Sabzi                                                    Aloo Shimla Mirch                                                   Non-veg                                                                Chicken Do Pyaaza                                                    Chicken Chettinad                                                     Desserts                                                          Cakes                                                             Black Forest                                                      Black Current                                                    Ice Creams                                                       chocolate                                                        Vanilla

User · Answer

import java util ArrayList  import java util List   public class Node lt T gt        private List lt Node lt T gt  gt  children   new ArrayList lt Node lt T gt  gt         private Node lt T gt  parent   null      private T data   null       public Node T data            this data   data             public Node T data  Node lt T gt  parent            this data   data          this parent   parent             public List lt Node lt T gt  gt  getChildren             return children             public void setParent Node lt T gt  parent            parent addChild this           this parent   parent             public void addChild T data            Node lt T gt  child   new Node lt T gt  data           child setParent this           this children add child              public void addChild Node lt T gt  child            child setParent this           this children add child              public T getData             return this data             public void setData T data            this data   data             public boolean isRoot             return  this parent    null              public boolean isLeaf             return this children size    0             public void removeParent             this parent   null            Example   import java util List   Node lt String gt  parentNode   new Node lt String gt   Parent     Node lt String gt  childNode1   new Node lt String gt   Child 1   parentNode   Node lt String gt  childNode2   new Node lt String gt   Child 2          childNode2 setParent parentNode     Node lt String gt  grandchildNode   new Node lt String gt   Grandchild of parentNode  Child of childNode1   childNode1    List lt Node lt String gt  gt  childrenNodes   parentNode getChildren

User · Answer

In answer      it creates circular dependency This can be avoided by removing parent inside Child nodes      i e   public class MyTreeNode lt T gt              private T data   null      private List lt MyTreeNode gt  children   new ArrayList lt  gt           public MyTreeNode T data            this data   data              public void addChild MyTreeNode child            this children add child              public void addChild T data            MyTreeNode lt T gt  newChild   new MyTreeNode lt  gt  data           children add newChild              public void addChildren List lt MyTreeNode gt  children            this children addAll children              public List lt MyTreeNode gt  getChildren             return children             public T getData             return data             public void setData T data            this data   data              Using the same example specified above the output will be like this           data    Root      children                      data    Child1            children                              data    Grandchild1                children                                            data    Grandchild2                children                                                      data    Child2            children                              data    Grandchild3                children                                                      data    Child3            children                                data    Child4            children                                data    Child5            children                                data    Child6            children

User · Answer

The process of assembling tree nodes is similar to the process of assembling lists  We have a constructor for tree nodes that initializes the instance variables   public Tree  Object cargo  Tree left  Tree right         this cargo   cargo       this left   left       this right   right        We allocate the child nodes first   Tree left   new Tree  new Integer 2   null  null    Tree right   new Tree  new Integer 3   null  null      We can create the parent node and link it to the children at the same time   Tree tree   new Tree  new Integer 1   left  right

User · Answer

Since  Jonathan s answer still consisted of some bugs  I made an improved version  I overwrote the toString   method for debugging purposes  be sure to change it accordingly to your data  import java util ArrayList  import java util List          Provides an easy way to create a parent-- gt child tree while preserving their depth history     Original Author  Jonathan  https   stackoverflow com a 22419453 14720622     public class TreeNode lt T gt        private final List lt TreeNode lt T gt  gt  children      private TreeNode lt T gt  parent      private T data      private int depth       public TreeNode T data               a fresh node  without a parent reference         this children   new ArrayList lt  gt             this parent   null          this data   data          this depth   0     0 is the base level  only the root should be on there             public TreeNode T data  TreeNode lt T gt  parent               new node with a given parent         this children   new ArrayList lt  gt             this data   data          this parent   parent          this depth    parent getDepth     1           parent addChild this              public int getDepth             return this depth             public void setDepth int depth            this depth   depth             public List lt TreeNode lt T gt  gt  getChildren             return children             public void setParent TreeNode lt T gt  parent            this setDepth parent getDepth     1           parent addChild this           this parent   parent             public TreeNode lt T gt  getParent             return this parent             public void addChild T data            TreeNode lt T gt  child   new TreeNode lt  gt  data           this children add child              public void addChild TreeNode lt T gt  child            this children add child              public T getData             return this data             public void setData T data            this data   data             public boolean isRootNode             return  this parent    null              public boolean isLeafNode             return  this children size      0              public void removeParent             this parent   null              Override     public String toString             String out    quot  quot           out     quot Node   quot    this getData   toString      quot    Depth   quot    this depth    quot    Parent   quot     this getParent      null    quot None quot    this parent getData   toString       quot    Children   quot     this getChildren   size      0    quot None quot     quot  quot            for TreeNode lt T gt  child   this getChildren                  out     quot  n t quot    child getData   toString      quot    Parent   quot     child getParent      null    quot None quot    child getParent   getData                       return out           And for the visualization  import model TreeNode          Entrypoint     public class Main       public static void main String   args            TreeNode lt String gt  rootNode   new TreeNode lt  gt   quot Root quot            TreeNode lt String gt  firstNode   new TreeNode lt  gt   quot Child 1  under Root  quot   rootNode           TreeNode lt String gt  secondNode   new TreeNode lt  gt   quot Child 2  under Root  quot   rootNode           TreeNode lt String gt  thirdNode   new TreeNode lt  gt   quot Child 3  under Child 2  quot   secondNode           TreeNode lt String gt  fourthNode   new TreeNode lt  gt   quot Child 4  under Child 3  quot   thirdNode           TreeNode lt String gt  fifthNode   new TreeNode lt  gt   quot Child 5  under Root  but with a later call  quot            fifthNode setParent rootNode            System out println rootNode toString             System out println firstNode toString             System out println secondNode toString             System out println thirdNode toString             System out println fourthNode toString             System out println fifthNode toString             System out println  quot Is rootNode a root node  -  quot    rootNode isRootNode             System out println  quot Is firstNode a root node  -  quot    firstNode isRootNode             System out println  quot Is thirdNode a leaf node  -  quot    thirdNode isLeafNode             System out println  quot Is fifthNode a leaf node  -  quot    fifthNode isLeafNode              Example output  Node  Root   Depth  0   Parent  None   Children       Child 1  under Root    Parent  Root     Child 2  under Root    Parent  Root     Child 5  under Root  but with a later call    Parent  Root Node  Child 1  under Root    Depth  1   Parent  Root   Children  None Node  Child 2  under Root    Depth  1   Parent  Root   Children       Child 3  under Child 2    Parent  Child 2  under Root  Node  Child 3  under Child 2    Depth  2   Parent  Child 2  under Root    Children       Child 4  under Child 3    Parent  Child 3  under Child 2  Node  Child 4  under Child 3    Depth  3   Parent  Child 3  under Child 2    Children  None Node  Child 5  under Root  but with a later call    Depth  1   Parent  Root   Children  None Is rootNode a root node  - true Is firstNode a root node  - false Is thirdNode a leaf node  - false Is fifthNode a leaf node  - true  Some additional informations  Do not use addChildren   and setParent   together  You ll end up having two references as setParent   already updates the children  gt parent relationship

User · Answer

In the accepted answer  public Node T data  Node lt T gt  parent        this data   data      this parent   parent      should be  public Node T data  Node lt T gt  parent        this data   data      this setParent parent       otherwise the parent does not have the child in its children list

[java] Tree implementation in Java (root, parents and children)

Examples related to java

Examples related to tree

Examples related to structure