Implementación de árbol genérico en Java

Question

¿Alguien conoce una implementación de árbol genérico (nodos pueden tener varios hijos) para Java? Debe provenir de una fuente confiable y debe probarse por completo.

Simplemente no parece correcto implementarlo yo mismo. Casi me recuerda mis años universitarios en los que debíamos escribir todas nuestras colecciones.

EDIT: encontrado this project en java.net, podría valer la pena examinar.

Answer 1

aquí viene:

abstract class TreeNode implements Iterable<TreeNode> { 

    private Set<TreeNode> children; 

    public TreeNode() { 
    children = new HashSet<TreeNode>(); 
    } 

    public boolean addChild(TreeNode n) { 
    return children.add(n); 
    } 

    public boolean removeChild(TreeNode n) { 
    return children.remove(n); 
    } 

    public Iterator<TreeNode> iterator() { 
    return children.iterator(); 
    } 
} 

estoy bien confiaba, pero no he probado la aplicación.

Answer 2

No hay una clase Tree en las bibliotecas de Colecciones. Sin embargo, es uno en Swing Frameworks. DefaultTreeModel

He usado esto en el pasado y funciona bien. Sin embargo, atrae clases adicionales a su aplicación que pueden ser deseables o no.

También puede simular un árbol utilizando otra colección y almacenar colecciones en ella. P.ej. Lista de listas

Answer 3

Uso un XML DOM (XML describe una estructura de árbol) y específicamente Open Source XOM (http://www.xom.nu). Esto es liviano, los nodos se pueden subclasificar si es necesario y se usan y prueban mucho. Puede ser más grande de lo que necesita pero tiene la ventaja de que cualquier método de navegación en árbol (ancestros, hermanos, etc.) se gestiona completamente a través de XPath. También puede serializar el árbol y transformarlo mediante métodos XML probados. También hay una fuerte comunidad de usuarios

Answer 4

me encontré con una implementación de un árbol genérico (con pruebas) aquí:

http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/

creo que esto es lo que busca.

Answer 5

Ah, iba a publicar un complemento desvergonzado en mi solución y vi que alguien ya había publicado un enlace. Sí, tuve el mismo problema y básicamente terminé escribiendo mi propio Generic Tree. Tengo pruebas para el nodo del árbol y el árbol en sí.

Implementé el nodo como un objeto que tiene un campo de datos y una lista de nodos (que son los elementos secundarios de ese nodo).

http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/

Answer 6

me encontré con una absolutamente fantástica biblioteca http://jung.sourceforge.net, consulte el Javadoc http://jung.sourceforge.net/doc/api/index.html. Es mucho más que solo una implementación de gráfico. Con él puedes visualizar y gráficos de diseño; Además, tiene un conjunto de algoritmos de gráficos estándar que puede usar de manera inmediata. Vaya, ¡compruébalo! Aunque terminé implementando mi propio gráfico básico (no sabía de JUNG antes), uso esta biblioteca para la visualización. ¡Se ve muy limpio!

Answer 7

Es bastante difícil hacer una verdadera implementación de árbol genérico en Java que realmente separó las operaciones y propiedades de árbol de las implementaciones subyacentes, es decir, intercambiar un RedBlackTreeNode y anular un par de métodos para obtener una implementación RedBlackTree conservando todo el genérico operaciones que contiene una interfaz BinaryTree.

Además, una abstracción ideal podría intercambiar la representación de árbol de bajo nivel, p. una estructura de árbol binario implícita almacenada en una matriz para una interfaz Heap o una base de nodo con punteros secundarios izquierdo y derecho, o múltiples punteros secundarios, o aumentar cualquiera de los anteriores con punteros padres, o enhebrar los nodos hoja, etc., etc. etc.

Intenté y resolví esto por mí mismo, pero terminé con una interfaz bastante complicada que aún aplica seguridad de tipo. Aquí está el esqueleto de la idea que establece una clase BinaryTree abstracta con una operación no trivial (Euler Tour) que funcionará incluso si se cambia la clase de nodo o la clase de árbol subyacente. Podría probable mejorarse introduciendo la idea de cursores para la navegación y posiciones dentro de la estructura de árbol:

public interface Tree<E, P extends Tree.Entry<E, P>> extends Collection<E> 
{ 
    public P getRoot(); 
    public Collection<P> children(P v); 
    public E getValue(P v); 

    public static interface Entry<T, Q extends Entry<T, Q>> { } 
} 

public interface BinaryTree<E, P extends BinaryTree.Entry<E, P>> extends Tree<E, P> 
{ 
    public P leftChild(P v); 
    public P rightChild(P v); 

    public static interface Entry<T, Q extends Entry<T, Q>> extends Tree.Entry<T, Q> 
    { 
     public Q getLeft(); 
     public Q getRight(); 
    } 
} 

public interface TreeTraversalVisitor<E, P extends BinaryTree.Entry<E, P>, R> 
{ 
    public R visitLeft(BinaryTree<E, P> tree, P v, R result); 
    public R visitCenter(BinaryTree<E, P> tree, P v, R result); 
    public R visitRight(BinaryTree<E, P> tree, P v, R result); 
} 

public abstract class AbstractBinaryTree<E, P extends BinaryTree.Entry<E, P>> extends AbstractCollection<E> implements BinaryTree<E, P> 
{ 
    public Collection<P> children(P v) 
    { 
     Collection<P> c = new ArrayList<P>(2); 

     if (hasLeft(v)) 
     c.add(v.getLeft()); 

     if (hasRight(v)) 
     c.add(v.getRight()); 

     return c; 
    } 

    /** 
    * Performs an Euler Tour of the binary tree 
    */ 
    public static <R, E, P extends BinaryTree.Entry<E, P>> 
    R eulerTour(BinaryTree<E, P> tree, P v, TreeTraversalVisitor<E, P, R> visitor, R result) 
    { 
     if (v == null) 
     return result; 

     result = visitor.visitLeft(tree, v, result); 

     if (tree.hasLeft(v)) 
     result = eulerTour(tree, tree.leftChild(v), visitor, result); 

     result = visitor.visitCenter(tree, v, result); 

     if (tree.hasRight(v)) 
     result = eulerTour(tree, tree.rightChild(v), visitor, result); 

     result = visitor.visitRight(tree, v, result); 

     return result; 
    }  
} 

Answer 8

Uso guayaba

Guava15.0 presenta un buen API para el recorrido del árbol por lo que no es necesario volver -implétalo por billón de tiempo en tu código base.

Es decir, TreeTraverser y algunas implementaciones especializadas, como BinaryTreeTraverser.

Un gran satisfacción addition para evitar la re-implementación de algo tan sencillo y con un valor añadido:

• con tranquilidad (estabilidad, biblioteca apoyado, etc ...),
• buen diseño,
• varios modos de recorrido incorporados.

Mientras esté allí ...

en cuenta que la guayaba también proporciona ahora nuevos métodos para su clase de utilidad Files que hacen uso de la TreeTraverser, por ejemplo, Files.fileTreeTraverser() que le da un TreeTraverser<File> para sus necesidades de recorrido del sistema de archivos.