Tree Implementierung in Java (root, Eltern und Kinder)

Question

Ich muss eine Baumstruktur ähnlich wie das angehängte Bild in Java erstellen. Ich habe einige Fragen zu diesem Thema gefunden, aber ich habe keine überzeugende und gut erklärte Antwort gefunden. Das Anwendungsgeschäft besteht in Essen super Kategorien (Hauptgerichte, Desserts und andere). Jede dieser Kategorien kann übergeordnete Elemente oder untergeordnete Elemente usw. haben.

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

Beispiel:

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

Der Prozess des Zusammenbauens Baumknoten ist ähnlich dem Prozess des Zusammensetzens Listen. Wir haben einen Konstruktor für Baumknoten, der die Instanzvariablen initialisiert.

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

Wir verteilen die untergeordneten Knoten zuerst:

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

Wir können den übergeordneten Knoten erstellen und es den Kindern zur gleichen Zeit Link:

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

Answer 3

Dieser Baum ist kein binary tree, Sie benötigen also ein Array der Child-Elemente wie List.

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

Dann erstellen Sie die Instanzen.

Answer 4

In der akzeptierten Antwort

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

sollte

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

sonst die Eltern das Kind nicht Liste in seinen Kindern haben

Answer 5

Accepted answer löst eine java.lang.StackOverflowError beim Aufruf der setParent oder addChild Methoden.

Hier ist eine etwas einfachere Implementierung ohne diese Fehler:

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

Einige Beispiele:

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

Hier ist meine Implementierung für Ihre Anforderung in Java. In der TreeNode-Klasse verwendete ich generisches Array, um die Baumdaten zu speichern. wir können auch arraylist oder dynamisches Array verwenden, um den Baumwert zu speichern.

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

Und die Client-Klasse für die obige Implementierung.

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