Estructura de datos del árbol de Java?

¿Hay una buena estructura de datos disponible (Java estándar) para representar un árbol en Java?

Específicamente, necesito representar lo siguiente:

  • El árbol en cualquier nodo puede tener un número arbitrario de niños
  • Cada nodo (después de la raíz) es solo una Cadena (cuyos hijos también son Cadenas)
  • Necesito poder obtener todos los niños (algún tipo de lista o conjunto de cadenas) con una cadena de entrada que representa un nodo dado

¿Hay una estructura disponible para esto o tengo que crear la mía (si es así, las sugerencias de implementación serían geniales)?

Aquí:

public class Tree { private Node root; public Tree(T rootData) { root = new Node(); root.data = rootData; root.children = new ArrayList>(); } public static class Node { private T data; private Node parent; private List> children; } } 

Esa es una estructura de árbol básica que se puede usar para String u otro objeto. Es bastante fácil implementar árboles simples para hacer lo que necesita.

Todo lo que necesita agregar son métodos para agregar, eliminar, atravesar y construir. El Node es el bloque de construcción básico del Tree .

Sin embargo, otra estructura de árbol:

 public class TreeNode implements Iterable> { T data; TreeNode parent; List> children; public TreeNode(T data) { this.data = data; this.children = new LinkedList>(); } public TreeNode addChild(T child) { TreeNode childNode = new TreeNode(child); childNode.parent = this; this.children.add(childNode); return childNode; } // other features ... } 

Uso de muestra:

 TreeNode root = new TreeNode("root"); { TreeNode node0 = root.addChild("node0"); TreeNode node1 = root.addChild("node1"); TreeNode node2 = root.addChild("node2"); { TreeNode node20 = node2.addChild(null); TreeNode node21 = node2.addChild("node21"); { TreeNode node210 = node20.addChild("node210"); } } } 

PRIMA
Ver árboles en toda regla con:

  • iterador
  • buscando
  • Java / C #

https://github.com/gt4dev/yet-another-tree-structure

En realidad, hay una buena estructura de árbol implementada en el JDK.

Eche un vistazo a javax.swing.tree , TreeModel y TreeNode . Están diseñados para ser utilizados con el JTreePanel pero, de hecho, son una buena implementación de árbol y no hay nada que te JTreePanel usarlo sin una interfaz de swing.

Tenga en cuenta que a partir de Java 9 es posible que no desee utilizar estas clases, ya que no estarán presentes en los ‘Perfiles compactos’ .

¿Qué hay de esto?

 import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; /** * @author ycoppel@google.com (Yohann Coppel) * * @param  * Object's type in the tree. */ public class Tree { private T head; private ArrayList> leafs = new ArrayList>(); private Tree parent = null; private HashMap> locate = new HashMap>(); public Tree(T head) { this.head = head; locate.put(head, this); } public void addLeaf(T root, T leaf) { if (locate.containsKey(root)) { locate.get(root).addLeaf(leaf); } else { addLeaf(root).addLeaf(leaf); } } public Tree addLeaf(T leaf) { Tree t = new Tree(leaf); leafs.add(t); t.parent = this; t.locate = this.locate; locate.put(leaf, t); return t; } public Tree setAsParent(T parentRoot) { Tree t = new Tree(parentRoot); t.leafs.add(this); this.parent = t; t.locate = this.locate; t.locate.put(head, this); t.locate.put(parentRoot, t); return t; } public T getHead() { return head; } public Tree getTree(T element) { return locate.get(element); } public Tree getParent() { return parent; } public Collection getSuccessors(T root) { Collection successors = new ArrayList(); Tree tree = getTree(root); if (null != tree) { for (Tree leaf : tree.leafs) { successors.add(leaf.head); } } return successors; } public Collection> getSubTrees() { return leafs; } public static  Collection getSuccessors(T of, Collection> in) { for (Tree tree : in) { if (tree.locate.containsKey(of)) { return tree.getSuccessors(of); } } return new ArrayList(); } @Override public String toString() { return printTree(0); } private static final int indent = 2; private String printTree(int increment) { String s = ""; String inc = ""; for (int i = 0; i < increment; ++i) { inc = inc + " "; } s = inc + head; for (Tree child : leafs) { s += "\n" + child.printTree(increment + indent); } return s; } } 

Escribí una pequeña biblioteca que maneja árboles generics. Es mucho más ligero que las cosas de swing. También tengo un proyecto de maven para eso.

 public class Tree { private List leaves = new LinkedList(); private Tree parent = null; private String data; public Tree(String data, Tree parent) { this.data = data; this.parent = parent; } } 

Obviamente, puede agregar métodos de utilidad para agregar / eliminar elementos secundarios.

Deberías comenzar por definir qué es un árbol (para el dominio), esto se hace mejor definiendo primero la interfaz . No todas las estructuras de árboles son modificables, la posibilidad de agregar y eliminar nodos debe ser una característica opcional, por lo que hacemos una interfaz adicional para eso.

No es necesario crear objetos de nodo que contengan los valores ; de hecho, veo esto como un defecto de diseño importante y sobrecarga en la mayoría de las implementaciones de árbol. Si miras a Swing, TreeModel está libre de clases de nodos (solo DefaultTreeModel hace uso de TreeNode ), ya que no son realmente necesarios.

 public interface Tree  extends Serializable { public List getRoots (); public N getParent (N node); public List getChildren (N node); } public interface MutableTree  extends Tree { public boolean add (N parent, N node); public boolean remove (N node, boolean cascade); } 

Dadas estas interfaces, al código que usa árboles no le tiene que importar mucho cómo se implementa el árbol. Esto le permite usar implementaciones genéricas y especializadas , donde se realiza el árbol al delegar funciones a otra API.
Ejemplo: Estructura del árbol de archivos.

 public class MappedTreeStructure implements MutableTree { public static void main(String[] args) { MutableTree tree = new MappedTreeStructure(); tree.add("A", "B"); tree.add("A", "C"); tree.add("C", "D"); tree.add("E", "A"); System.out.println(tree); } private final Map nodeParent = new HashMap(); private final LinkedHashSet nodeList = new LinkedHashSet(); private void checkNotNull(N node, String parameterName) { if (node == null) throw new IllegalArgumentException(parameterName + " must not be null"); } @Override public boolean add(N parent, N node) { checkNotNull(parent, "parent"); checkNotNull(node, "node"); // check for cycles N current = parent; do { if (node.equals(current)) { throw new IllegalArgumentException(" node must not be the same or an ancestor of the parent"); } } while ((current = getParent(current)) != null); boolean added = nodeList.add(node); nodeList.add(parent); nodeParent.put(node, parent); return added; } @Override public boolean remove(N node, boolean cascade) { checkNotNull(node, "node"); if (!nodeList.contains(node)) { return false; } if (cascade) { for (N child : getChildren(node)) { remove(child, true); } } else { for (N child : getChildren(node)) { nodeParent.remove(child); } } nodeList.remove(node); return true; } @Override public List getRoots() { return getChildren(null); } @Override public N getParent(N node) { checkNotNull(node, "node"); return nodeParent.get(node); } @Override public List getChildren(N node) { List children = new LinkedList(); for (N n : nodeList) { N parent = nodeParent.get(n); if (node == null && parent == null) { children.add(n); } else if (node != null && parent != null && parent.equals(node)) { children.add(n); } } return children; } @Override public String toString() { StringBuilder builder = new StringBuilder(); dumpNodeStructure(builder, null, "- "); return builder.toString(); } private void dumpNodeStructure(StringBuilder builder, N node, String prefix) { if (node != null) { builder.append(prefix); builder.append(node.toString()); builder.append('\n'); prefix = " " + prefix; } for (N child : getChildren(node)) { dumpNodeStructure(builder, child, prefix); } } } 

Ninguna respuesta menciona código simplificado pero que funcione, así que aquí está:

 public class TreeNodeArray { public T value; public final java.util.List> kids = new java.util.ArrayList>(); } 

Puede usar cualquier API XML de Java como Documento y Nodo, ya que XML es una estructura de árbol con cadenas.

Hay un par de estructuras de datos de árbol en Java, como DefaultMutableTreeNode en JDK Swing, Tree en el paquete de analizador de Stanford y otros códigos de juguete. Pero ninguno de estos es suficiente pero lo suficientemente pequeño para un propósito general.

El proyecto Java-tree intenta proporcionar otra estructura de datos de árbol de propósito general en Java. La diferencia entre esto y otros es

  • Totalmente libre. Puedes usarlo en cualquier lugar (excepto en tu tarea: P)
  • Pequeño pero lo suficientemente general. Puse todo lo de la estructura de datos en un archivo de clase, por lo que sería fácil de copiar / pegar.
  • No solo juguetes. Conozco docenas de códigos de árbol de Java que solo pueden manejar árboles binarios u operaciones limitadas. Este TreeNode es mucho más que eso. Proporciona diferentes formas de visitar nodos, como preorder, postorder, breadthfirst, leaves, path to root, etc. Además, se proporcionan iteradores también para la suficiencia.
  • Se agregarán más utils. Estoy dispuesto a agregar más operaciones para que este proyecto sea completo, especialmente si envía una solicitud a través de github.

En la misma línea que la respuesta de Gareth, echa un vistazo a DefaultMutableTreeNode . No es genérico, pero de lo contrario parece ajustarse a la factura. Aunque está en el paquete javax.swing, no depende de ninguna clase AWT o Swing. De hecho, el código fuente en realidad tiene el comentario // ISSUE: this class depends on nothing in AWT -- move to java.util?

Si está haciendo una encoding de pizarra, una entrevista, o simplemente planea usar un árbol, la verbosidad de estos es demasiado.

Se debe decir además que la razón por la cual un árbol no está allí como, por ejemplo, un Pair (sobre lo cual podría decirse lo mismo), se debe a que debes encapsular tus datos en la clase utilizándolo, y la implementación más simple parece :

 /*** /* Within the class that's using a binary tree for any reason. You could /* generalize with generics IFF the parent class needs different value types. */ private class Node { public String value; public Node[] nodes; // Or an Iterable nodes; } 

Eso es realmente para un árbol de ancho arbitrario.

Si quería un árbol binario, a menudo es más fácil de usar con campos con nombre:

 private class Node { // Using package visibility is an option String value; Node left; Node right; } 

O si querías un trie:

 private class Node { String value; Map nodes; } 

Ahora dijiste que querías

para poder obtener todos los niños (algún tipo de lista o conjunto de cadenas) con una cadena de entrada que representa un nodo determinado

Eso suena como tu tarea.
Pero dado que estoy razonablemente seguro de que cualquier fecha límite ya pasó …

 import java.util.Arrays; import java.util.ArrayList; import java.util.List; public class kidsOfMatchTheseDays { static private class Node { String value; Node[] nodes; } // Pre-order; you didn't specify. static public List list(Node node, String find) { return list(node, find, new ArrayList(), false); } static private ArrayList list( Node node, String find, ArrayList list, boolean add) { if (node == null) { return list; } if (node.value.equals(find)) { add = true; } if (add) { list.add(node.value); } if (node.nodes != null) { for (Node child: node.nodes) { list(child, find, list, add); } } return list; } public static final void main(String... args) { // Usually never have to do setup like this, so excuse the style // And it could be cleaner by adding a constructor like: // Node(String val, Node... children) { // value = val; // nodes = children; // } Node tree = new Node(); tree.value = "root"; Node[] n = {new Node(), new Node()}; tree.nodes = n; tree.nodes[0].value = "leftish"; tree.nodes[1].value = "rightish-leafy"; Node[] nn = {new Node()}; tree.nodes[0].nodes = nn; tree.nodes[0].nodes[0].value = "off-leftish-leaf"; // Enough setup System.out.println(Arrays.toString(list(tree, args[0]).toArray())); } } 

Esto te hace usar como:

 $ java kidsOfMatchTheseDays leftish [leftish, off-leftish-leaf] $ java kidsOfMatchTheseDays root [root, leftish, off-leftish-leaf, rightish-leafy] $ java kidsOfMatchTheseDays rightish-leafy [rightish-leafy] $ java kidsOfMatchTheseDays a [] 

Como la pregunta requiere una estructura de datos disponible, se puede construir un árbol a partir de listas o matrices:

 Object[] tree = new Object[2]; tree[0] = "Hello"; { Object[] subtree = new Object[2]; subtree[0] = "Goodbye"; subtree[1] = ""; tree[1] = subtree; } 

instanceof se puede usar para determinar si un elemento es un subárbol o un nodo terminal.

 public abstract class Node { List children; public List getChidren() { if (children == null) { children = new ArrayList<>(); } return chidren; } } 

Tan simple como se pone y muy fácil de usar. Para usarlo, extiéndalo:

 public class MenuItem extends Node { String label; String href; ... } 

Por ejemplo :

 import java.util.ArrayList; import java.util.List; /** * * @author X2 * * @param  */ public class HisTree { private Node root; public HisTree(T rootData) { root = new Node(); root.setData(rootData); root.setChildren(new ArrayList>()); } } class Node { private T data; private Node parent; private List> children; public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } public List> getChildren() { return children; } public void setChildren(List> children) { this.children = children; } } 

Puede usar la clase HashTree incluida en Apache JMeter que es parte del Proyecto de Yakarta.

La clase HashTree está incluida en el paquete org.apache.jorphan.collections. Aunque este paquete no se lanza fuera del proyecto JMeter, puede obtenerlo fácilmente:

1) Descargue las fonts de JMeter .

2) Crea un nuevo paquete.

3) Copiar en él / src / jorphan / org / apache / jorphan / collections /. Todos los archivos excepto Data.java

4) Copie también /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree está listo para usar.

Por favor, compruebe el código a continuación, donde he utilizado las estructuras de datos de Tree, sin utilizar las clases de Colección. El código puede tener errores / mejoras, pero por favor use esto solo para referencia

 package com.datastructure.tree; public class BinaryTreeWithoutRecursion  { private TreeNode root; public BinaryTreeWithoutRecursion (){ root = null; } public void insert(T data){ root =insert(root, data); } public TreeNode insert(TreeNode node, T data ){ TreeNode newNode = new TreeNode<>(); newNode.data = data; newNode.right = newNode.left = null; if(node==null){ node = newNode; return node; } Queue> queue = new Queue>(); queue.enque(node); while(!queue.isEmpty()){ TreeNode temp= queue.deque(); if(temp.left!=null){ queue.enque(temp.left); }else { temp.left = newNode; queue =null; return node; } if(temp.right!=null){ queue.enque(temp.right); }else { temp.right = newNode; queue =null; return node; } } queue=null; return node; } public void inOrderPrint(TreeNode root){ if(root!=null){ inOrderPrint(root.left); System.out.println(root.data); inOrderPrint(root.right); } } public void postOrderPrint(TreeNode root){ if(root!=null){ postOrderPrint(root.left); postOrderPrint(root.right); System.out.println(root.data); } } public void preOrderPrint(){ preOrderPrint(root); } public void inOrderPrint(){ inOrderPrint(root); } public void postOrderPrint(){ inOrderPrint(root); } public void preOrderPrint(TreeNode root){ if(root!=null){ System.out.println(root.data); preOrderPrint(root.left); preOrderPrint(root.right); } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub BinaryTreeWithoutRecursion  ls= new BinaryTreeWithoutRecursion <>(); ls.insert(1); ls.insert(2); ls.insert(3); ls.insert(4); ls.insert(5); ls.insert(6); ls.insert(7); //ls.preOrderPrint(); ls.inOrderPrint(); //ls.postOrderPrint(); } } 

No hay una estructura de datos específica en Java que se adapte a sus necesidades. Sus requisitos son bastante específicos y para eso necesita diseñar su propia estructura de datos. En cuanto a sus requisitos, cualquiera puede decir que necesita algún tipo de árbol n-ario con alguna funcionalidad específica. Puede diseñar su estructura de datos de la siguiente manera:

  1. La estructura del nodo del árbol sería como el contenido en el nodo y la lista de elementos secundarios como: clase Node {String value; Enumerar hijos;}
  2. Necesitas recuperar los elementos secundarios de una cadena dada, para que puedas tener 2 métodos 1: Node searchNode (String str), devolverá el nodo que tiene el mismo valor que la entrada dada (usa BFS para buscar) 2: List getChildren (String) str): este método llamará internamente a searchNode para obtener el nodo que tenga la misma cadena y luego creará la lista de todos los valores de cadena de elementos secundarios y devolverá.
  3. También se le pedirá que inserte una cadena en el árbol. Deberá escribir un método, por ejemplo, inserto void (String parent, String value): esto buscará nuevamente el nodo que tenga un valor igual a parent y luego podrá crear un nodo con un valor dado y agregarlo a la lista de hijos del padre encontrado .

Yo sugeriría, usted escribe la estructura del nodo en una clase como Class Node {String value; Enumere los niños;} y todos los demás métodos como search, insert y getChildren en otra clase NodeUtils para que también pueda pasar la raíz del árbol para realizar operaciones en un árbol específico como: clase NodeUtils {public Node search search (Node root, String value) {// realizar BFS y devolver el nodo}

En el pasado acabo de utilizar un mapa nested para esto. Esto es lo que uso hoy, es muy simple pero se ajusta a mis necesidades. Quizás esto ayude a otro.

 import com.fasterxml.jackson.annotation.JsonValue; import com.fasterxml.jackson.databind.ObjectMapper; import java.util.HashMap; import java.util.Map; import java.util.TreeMap; /** * Created by kic on 16.07.15. */ public class NestedMap { private final Map root = new HashMap<>(); public NestedMap put(K key) { Object nested = root.get(key); if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>()); return (NestedMap) nested; } public Map.Entry put(K key, V value) { root.put(key, value); return (Map.Entry) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get(); } public NestedMap get(K key) { return (NestedMap) root.get(key); } public V getValue(K key) { return (V) root.get(key); } @JsonValue public Map getRoot() { return root; } public static void main(String[] args) throws Exception { NestedMap test = new NestedMap<>(); test.put("a").put("b").put("c", 12); Map.Entry foo = test.put("a").put("b").put("d", 12); test.put("b", 14); ObjectMapper mapper = new ObjectMapper(); System.out.println(mapper.writeValueAsString(test)); foo.setValue(99); System.out.println(mapper.writeValueAsString(test)); System.out.println(test.get("a").get("b").getValue("d")); } } 
  // TestTree.java // A simple test to see how we can build a tree and populate it // import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.tree.*; public class TestTree extends JFrame { JTree tree; DefaultTreeModel treeModel; public TestTree( ) { super("Tree Test Example"); setSize(400, 300); setDefaultCloseOperation(EXIT_ON_CLOSE); } public void init( ) { // Build up a bunch of TreeNodes. We use DefaultMutableTreeNode because the // DefaultTreeModel can use it to build a complete tree. DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root"); DefaultMutableTreeNode subroot = new DefaultMutableTreeNode("SubRoot"); DefaultMutableTreeNode leaf1 = new DefaultMutableTreeNode("Leaf 1"); DefaultMutableTreeNode leaf2 = new DefaultMutableTreeNode("Leaf 2"); // Build our tree model starting at the root node, and then make a JTree out // of it. treeModel = new DefaultTreeModel(root); tree = new JTree(treeModel); // Build the tree up from the nodes we created. treeModel.insertNodeInto(subroot, root, 0); // Or, more succinctly: subroot.add(leaf1); root.add(leaf2); // Display it. getContentPane( ).add(tree, BorderLayout.CENTER); } public static void main(String args[]) { TestTree tt = new TestTree( ); tt.init( ); tt.setVisible(true); } } 

Escribí una biblioteca de árbol que funciona muy bien con Java8 y que no tiene otras dependencias. También proporciona una interpretación libre de algunas ideas de la progtwigción funcional y le permite mapear / filtrar / podar / buscar todo el árbol o subárboles.

https://github.com/RutledgePaulV/prune

La implementación no hace nada especial con la indexación y no me alejé de la recursión, por lo que es posible que con grandes árboles el rendimiento se deteriore y puedas volar la stack. Pero si todo lo que necesitas es un árbol sencillo de profundidad pequeña a moderada, creo que funciona bastante bien. Proporciona una sana definición de igualdad (basada en el valor) y también tiene una implementación toString que le permite visualizar el árbol.

Puede usar la clase TreeSet en java.util. *. Está funcionando como árbol de búsqueda binario, por lo que ya está ordenado. La clase TreeSet implementa las interfaces Iterable, Collection y Set. Puede recorrer el árbol con un iterador como un conjunto.

 TreeSet treeSet = new TreeSet(); Iterator it = treeSet.Iterator(); while(it.hasNext()){ ... } 

Puede verificar, Java Doc y algunos otros .

Árbol personalizado implemento de Tree sin usar el marco Collection. Contiene diferentes operaciones fundamentales necesarias en la implementación de Árbol.

 class Node { int data; Node left; Node right; public Node(int ddata, Node left, Node right) { this.data = ddata; this.left = null; this.right = null; } public void displayNode(Node n) { System.out.print(n.data + " "); } } class BinaryTree { Node root; public BinaryTree() { this.root = null; } public void insertLeft(int parent, int leftvalue ) { Node n = find(root, parent); Node leftchild = new Node(leftvalue, null, null); n.left = leftchild; } public void insertRight(int parent, int rightvalue) { Node n = find(root, parent); Node rightchild = new Node(rightvalue, null, null); n.right = rightchild; } public void insertRoot(int data) { root = new Node(data, null, null); } public Node getRoot() { return root; } public Node find(Node n, int key) { Node result = null; if (n == null) return null; if (n.data == key) return n; if (n.left != null) result = find(n.left, key); if (result == null) result = find(n.right, key); return result; } public int getheight(Node root){ if (root == null) return 0; return Math.max(getheight(root.left), getheight(root.right)) + 1; } public void printTree(Node n) { if (n == null) return; printTree(n.left); n.displayNode(n); printTree(n.right); } } 

Escribí una pequeña clase “TreeMap” basada en “HashMap” que admite agregar rutas:

 import java.util.HashMap; import java.util.LinkedList; public class TreeMap extends LinkedHashMap> { public void put(T[] path) { LinkedList list = new LinkedList<>(); for (T key : path) { list.add(key); } return put(list); } public void put(LinkedList path) { if (path.isEmpty()) { return; } T key = path.removeFirst(); TreeMap val = get(key); if (val == null) { val = new TreeMap<>(); put(key, val); } val.put(path); } } 

Se puede usar para almacenar un Árbol de cosas de tipo “T” (genérico), pero no (todavía) admite el almacenamiento de datos adicionales en sus nodos. Si tienes un archivo como este:

 root, child 1 root, child 1, child 1a root, child 1, child 1b root, child 2 root, child 3, child 3a 

Entonces puedes convertirlo en un árbol ejecutando:

 TreeMap root = new TreeMap<>(); Scanner scanner = new Scanner(new File("input.txt")); while (scanner.hasNextLine()) { root.put(scanner.nextLine().split(", ")); } 

Y obtendrás un buen árbol. Debe ser fácil de adaptar a sus necesidades.