Implementacja drzewa w Javie (root, rodzice i dzieci)

Question

Potrzebuję utworzyć strukturę drzewa podobną do dołączonego obrazu w Javie. Znalazłem kilka pytań związanych z tym, ale nie znalazłem przekonującej i dobrze wyjaśnionej odpowiedzi. Aplikacja składa się z suplementów diety (dania główne, desery i inne). Każda z tych kategorii może zawierać elementy nadrzędne lub elementy podrzędne i tak dalej.

Answer 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() { 
     if(this.children.size() == 0) 
      return true; 
     else 
      return false; 
    } 

    public void removeParent() { 
     this.parent = null; 
    } 
} 

Przykład:

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

Answer 2

Proces montażu węzłów drzewa jest podobny do procesu montażu list. Mamy konstruktor dla węzłów drzewa, który inicjuje zmienne instancji.

public Tree (Object cargo, Tree left, Tree right) { 
    this.cargo = cargo; 
    this.left = left; 
    this.right = right; 
} 

Mamy przeznaczyć węzły potomne pierwszy:

Tree left = new Tree (new Integer(2), null, null); 
Tree right = new Tree (new Integer(3), null, null); 

Możemy utworzyć węzeł nadrzędny i połączyć go z dziećmi w tym samym czasie:

Tree tree = new Tree (new Integer(1), left, right); 

Answer 3

To drzewo nie jest drzewo binarne, więc potrzebujesz tablicy elementów podrzędnych, takich jak List.

public Node(Object data, List<Node> children) { 
    this.data = data; 
    this.children = children; 
} 

Następnie utwórz instancje.

Answer 4

w przyjętym odpowiedź

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

powinny być

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

inaczej rodzic nie posiada dziecko na liście dzieci

Answer 5

Accepted answer rzuca java.lang.StackOverflowError podczas wywoływania metod setParent lub addChild.

Oto nieco prostsze wdrożenie bez tych błędów:

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); 
     newChild.setParent(this); 
     children.add(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; 
    } 
} 

Kilka przykładów:

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

Answer 6

Oto moja implementacja w Java dla Państwa wymagań. W klasie treeNode użyłem ogólnej tablicy do przechowywania danych drzewa. możemy również użyć tablicy arraylist lub dynamicznej tablicy do zapisania wartości drzewa.

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

I klasa klienta dla powyższej implementacji.

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

WYJŚCIE

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