Tree implementation in Java (root, parents and chi

问题:

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.

回答1:

import java.util.ArrayList;
import java.util.List;

public class Node<T> {
    private List<Node<T>> children = new ArrayList<Node<T>>();
    private Node<T> parent = null;
    private T data = null;

    public Node(T data) {
        this.data = data;
    }

    public Node(T data, Node<T> parent) {
        this.data = data;
        this.parent = parent;
    }

    public List<Node<T>> getChildren() {
        return children;
    }

    public void setParent(Node<T> parent) {
        parent.addChild(this);
        this.parent = parent;
    }

    public void addChild(T data) {
        Node<T> child = new Node<T>(data);
        child.setParent(this);
        this.children.add(child);
    }

    public void addChild(Node<T> 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<String> parentNode = new Node<String>("Parent"); 
Node<String> childNode1 = new Node<String>("Child 1", parentNode);
Node<String> childNode2 = new Node<String>("Child 2");     

childNode2.setParent(parentNode); 

Node<String> grandchildNode = new Node<String>("Grandchild of parentNode. Child of childNode1", childNode1); 
List<Node<String>> childrenNodes = parentNode.getChildren();

回答2:

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());
}

回答3:

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

回答4:

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           

回答5:

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.

回答6:

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": [] } ] }

回答7:

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