Implémentation d'arbre générique en Java

Question

Quelqu'un est-il au courant d'un générique de l'arbre (les nœuds peuvent avoir plusieurs enfants) mise en œuvre pour Java? Il doit venir d'un puits, d'une source de confiance et doit être entièrement testé.

Il ne semble pas approprié de mise en œuvre moi-même. Presque me rappelle de mes années d'université, lorsque nous étions censés écrire toutes nos collections de nous-mêmes.

EDIT: Trouvé ce projet sur java.net pourrait être intéressant de regarder dans.

Answer 1

Ça vient:

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

Je suis digne de confiance, mais je n'ai pas testé la mise en œuvre.

Answer 2

Il n'y a pas de classe Tree dans les bibliothèques Collections. Cependant, il y en a un dans les cadres Swing. DefaultTreeModel

Je l'ai utilisé dans le passé et cela fonctionne bien. Il ajoute des classes supplémentaires dans votre application, ce qui peut ou non être souhaitable.

Vous pouvez également simuler un arbre à l'aide d'une autre collection et y stocker des collections. Par exemple. Liste des listes.

Answer 3

L'Utilisation De Goyave

Goyave 15.0 présente une bonne API pour l'arbre transversal de sorte que vous n'avez pas besoin de re-mettre en œuvre pour la gazillionth temps dans votre base de code.

À savoir, TreeTraverser et certains des implémentations spécialisées, comme BinaryTreeTraverser.

Un très bienvenue plus pour éviter de re-mise en œuvre de quelque chose de si simple et avec bonus:

• avec la paix de l'esprit (la stabilité, de la pris en charge de la bibliothèque, etc...),
• un bon design,
• plusieurs traversée modes intégré.

Pendant que Vous Y êtes...

Notez que la Goyave fournit également maintenant de nouvelles méthodes pour son Files classe utilitaire qui font usage de l' TreeTraverser, par exemple, Files.fileTreeTraverser() qui vous donne un TreeTraverser<File> pour votre système de fichiers de la traversée des besoins.

Answer 4

Il est assez difficile de faire un vrai générique de l'arbre de la mise en œuvre en Java, vraiment séparé de l'arbre des opérations et des propriétés de la implémentations sous-jacentes, c'est à dire de le remplacer par un RedBlackTreeNode et de remplacer une couple de méthode pour obtenir un RedBlackTree mise en œuvre, tout en conservant tous les génériques des opérations qu'un BinaryTree interface contient.

Aussi, un idéal, une abstraction serait en mesure de remplacer le faible niveau de représentation en arborescence, par exemple implicite de l'arbre binaire de la structure stockées dans un tableau pour un Segment ou un Nœud d'interface de base à gauche et à droite de l'enfant pointeurs, ou de plusieurs enfants de pointeurs, ou de les augmenter tout de ce qui précède avec les parents des pointeurs, ou d'enfiler les nœuds feuilles, etc, etc, etc.

J'ai essayer de le résoudre moi-même, mais a terminé avec un peu plus compliquée interface qui applique encore la sécurité de type. Voici le squelette de l'idée qui définit un résumé BinaryTree classe avec un non-trivial de fonctionnement (Euler Tour) qui fonctionne même si le nœud sous-jacent de classe ou de classe de l'arbre est changé. Il probable pourrait être améliorée par l'introduction de l'idée de curseurs pour la navigation et les positions au sein de la structure de l'arbre:

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 5

Ah, j'allais poster un plug sans vergogne à ma solution et vu que quelqu'un a déjà posté un lien vers elle. Ouais, j'ai eu le même problème et j'ai pratiquement terminé l'écriture de mon propre Générique de l'Arbre. J'ai des tests pour les noeuds de l'arbre, et l'arbre lui-même.

J'ai mis en place le nœud comme un objet ayant un champ de données et une liste de nœuds (qui sont les enfants de ce nœud).

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