Mise en œuvre de l'arbre en Java (racine, parents et enfants)
je dois créer une structure arborescente similaire à L'image ci-jointe en Java. J'ai trouvé quelques questions liées à celle-ci, mais je n'ai pas trouvé de réponse convaincante et bien expliquée. Le secteur d'application se compose de super catégories de produits alimentaires (Plats Principaux, desserts et autres). Chacune de ces catégories peuvent avoir des éléments parents ou les enfants et ainsi de suite.
tree Structure" src="/images/content/19330731/958047bb36369ef53ca044a20ca21fec.gif">
6 réponses
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;
}
}
exemple:
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();
Accepted answer lance un java.lang.StackOverflowError en appelant les méthodes setParent ou addChild .
Voici une implémentation un peu plus simple sans ces 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);
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;
}
}
quelques exemples:
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());
}
dans la réponse acceptée
public Node(T data, Node<T> parent) {
this.data = data;
this.parent = parent;
}
devrait être
public Node(T data, Node<T> parent) {
this.data = data;
this.setParent(parent);
}
, sinon, le parent n'a pas l'enfant dans sa liste d'enfants
cet arbre n'est pas un arbre binaire, donc vous avez besoin d'un tableau des éléments enfants, comme la liste.
public Node(Object data, List<Node> children) {
this.data = data;
this.children = children;
}
crée alors les instances.
Voici mon implémentation en java pour vos besoins. Dans la classe treeNode, j'ai utilisé generic array pour stocker les données de l'arbre. nous pouvons également utiliser arraylist ou dynamic array pour stocker la valeur de l'arbre.
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);
}
}
et la classe client pour la mise en œuvre ci-dessus.
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);
}
}
SORTIE
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
le processus d'assemblage des noeuds d'arbre est similaire au processus d'assemblage des listes. Nous avons un constructeur pour les noeuds d'arbre qui initialise les variables d'instance.
public Tree (Object cargo, Tree left, Tree right) {
this.cargo = cargo;
this.left = left;
this.right = right;
}
nous attribuons d'abord les noeuds enfant:
Tree left = new Tree (new Integer(2), null, null);
Tree right = new Tree (new Integer(3), null, null);
nous pouvons créer le noeud parent et le relier aux enfants en même temps:
Tree tree = new Tree (new Integer(1), left, right);