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.
The answer is
In the accepted answer
public Node(T data, Node<T> parent) {
this.data = data;
this.parent = parent;
}
should be
public Node(T data, Node<T> parent) {
this.data = data;
this.setParent(parent);
}
otherwise the parent does not have the child in its children list
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<T> {
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 < 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
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);
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-->child tree while preserving their depth/history.
* Original Author: Jonathan, https://stackoverflow.com/a/22419453/14720622
*/
public class TreeNode<T> {
private final List<TreeNode<T>> children;
private TreeNode<T> parent;
private T data;
private int depth;
public TreeNode(T data) {
// a fresh node, without a parent reference
this.children = new ArrayList<>();
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<T> parent) {
// new node with a given parent
this.children = new ArrayList<>();
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<TreeNode<T>> getChildren() {
return children;
}
public void setParent(TreeNode<T> parent) {
this.setDepth(parent.getDepth() + 1);
parent.addChild(this);
this.parent = parent;
}
public TreeNode<T> getParent() {
return this.parent;
}
public void addChild(T data) {
TreeNode<T> child = new TreeNode<>(data);
this.children.add(child);
}
public void addChild(TreeNode<T> 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 = "";
out += "Node: " + this.getData().toString() + " | Depth: " + this.depth + " | Parent: " + (this.getParent() == null ? "None" : this.parent.getData().toString()) + " | Children: " + (this.getChildren().size() == 0 ? "None" : "");
for(TreeNode<T> child : this.getChildren()) {
out += "\n\t" + child.getData().toString() + " | Parent: " + (child.getParent() == null ? "None" : child.getParent().getData());
}
return out;
}
}
And for the visualization:
import model.TreeNode;
/**
* Entrypoint
*/
public class Main {
public static void main(String[] args) {
TreeNode<String> rootNode = new TreeNode<>("Root");
TreeNode<String> firstNode = new TreeNode<>("Child 1 (under Root)", rootNode);
TreeNode<String> secondNode = new TreeNode<>("Child 2 (under Root)", rootNode);
TreeNode<String> thirdNode = new TreeNode<>("Child 3 (under Child 2)", secondNode);
TreeNode<String> fourthNode = new TreeNode<>("Child 4 (under Child 3)", thirdNode);
TreeNode<String> fifthNode = new TreeNode<>("Child 5 (under Root, but with a later call)");
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("Is rootNode a root node? - " + rootNode.isRootNode());
System.out.println("Is firstNode a root node? - " + firstNode.isRootNode());
System.out.println("Is thirdNode a leaf node? - " + thirdNode.isLeafNode());
System.out.println("Is fifthNode a leaf node? - " + 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=>parent relationship.
This tree is not a binary tree, so you need an array of the children elements, like List.
public Node(Object data, List<Node> children) {
this.data = data;
this.children = children;
}
Then create the instances.
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<T>{
private T data = null;
private List<MyTreeNode> children = new ArrayList<>();
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<T> newChild = new MyTreeNode<>(data);
this.addChild(newChild);
}
public void addChildren(List<MyTreeNode> children) {
for(MyTreeNode t : children) {
t.setParent(this);
}
this.children.addAll(children);
}
public List<MyTreeNode> 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<String> root = new MyTreeNode<>("Root");
MyTreeNode<String> child1 = new MyTreeNode<>("Child1");
child1.addChild("Grandchild1");
child1.addChild("Grandchild2");
MyTreeNode<String> child2 = new MyTreeNode<>("Child2");
child2.addChild("Grandchild3");
root.addChild(child1);
root.addChild(child2);
root.addChild("Child3");
root.addChildren(Arrays.asList(
new MyTreeNode<>("Child4"),
new MyTreeNode<>("Child5"),
new MyTreeNode<>("Child6")
));
for(MyTreeNode node : root.getChildren()) {
System.out.println(node.getData());
}
In answer ,it creates circular dependency.This can be avoided by removing parent inside Child nodes. i.e,
public class MyTreeNode<T>{
private T data = null;
private List<MyTreeNode> children = new ArrayList<>();
public MyTreeNode(T data) {
this.data = data;
}
public void addChild(MyTreeNode child) {
this.children.add(child);
}
public void addChild(T data) {
MyTreeNode<T> newChild = new MyTreeNode<>(data);
children.add(newChild);
}
public void addChildren(List<MyTreeNode> children) {
this.children.addAll(children);
}
public List<MyTreeNode> 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": [] } ] }
Source: Stackoverflow.com