Question Structure de données d'arborescence Java?


Existe-t-il une bonne structure de données (Java standard) disponible pour représenter un arbre en Java?

Plus précisément, je dois représenter ce qui suit:

  • L'arbre à n'importe quel nœud peut avoir un nombre arbitraire d'enfants
  • Chaque nœud (après la racine) est juste une chaîne (dont les enfants sont aussi des chaînes)
  • Je dois être capable d'obtenir tous les enfants (une sorte de liste ou un tableau de chaînes de caractères) donné une chaîne d'entrée représentant un noeud donné

Y a-t-il une structure disponible pour cela ou dois-je créer le mien (si c'est le cas, les suggestions de mise en œuvre seraient excellentes).


419
2017-08-19 13:53


origine


Réponses:


Ici:

public class Tree<T> {
    private Node<T> root;

    public Tree(T rootData) {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }

    public static class Node<T> {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }
}

C'est une arborescence de base qui peut être utilisée pour String ou tout autre objet. Il est assez facile d'implémenter des arbres simples pour faire ce dont vous avez besoin.

Tout ce que vous avez besoin d'ajouter, ce sont des méthodes pour ajouter, supprimer, traverser et construire. le Node est l'élément de base de la Tree.


264
2017-08-19 13:56



Encore une autre structure d'arbre:

public class TreeNode<T> implements Iterable<TreeNode<T>> {

    T data;
    TreeNode<T> parent;
    List<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<T>(child);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }

    // other features ...

}

Exemple d'utilisation:

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

PRIME
Voir l'arbre à part entière avec:

  • itérateur
  • recherche
  • Java / C #

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


98
2017-07-05 13:30



Il y a en fait une très bonne arborescence implémentée dans le JDK.

Jettes un coup d'oeil à javax.swing.tree, TreeModel, et TreeNode. Ils sont conçus pour être utilisés avec le JTreePanel mais ils sont, en fait, une très bonne implémentation d'arbre et rien ne vous empêche de l'utiliser sans une interface swing.

Notez qu'à partir de Java 9, vous souhaiterez peut-être ne pas utiliser ces classes car elles ne seront pas présentes dans le «Profils compacts».


95
2017-08-19 14:06



Et ça?

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
  * @author ycoppel@google.com (Yohann Coppel)
  * 
  * @param <T>
  *          Object's type in the tree.
*/
public class Tree<T> {

  private T head;

  private ArrayList<Tree<T>> leafs = new ArrayList<Tree<T>>();

  private Tree<T> parent = null;

  private HashMap<T, Tree<T>> locate = new HashMap<T, Tree<T>>();

  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<T> addLeaf(T leaf) {
    Tree<T> t = new Tree<T>(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }

  public Tree<T> setAsParent(T parentRoot) {
    Tree<T> t = new Tree<T>(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<T> getTree(T element) {
    return locate.get(element);
  }

  public Tree<T> getParent() {
    return parent;
  }

  public Collection<T> getSuccessors(T root) {
    Collection<T> successors = new ArrayList<T>();
    Tree<T> tree = getTree(root);
    if (null != tree) {
      for (Tree<T> leaf : tree.leafs) {
        successors.add(leaf.head);
      }
    }
    return successors;
  }

  public Collection<Tree<T>> getSubTrees() {
    return leafs;
  }

  public static <T> Collection<T> getSuccessors(T of, Collection<Tree<T>> in) {
    for (Tree<T> tree : in) {
      if (tree.locate.containsKey(of)) {
        return tree.getSuccessors(of);
      }
    }
    return new ArrayList<T>();
  }

  @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<T> child : leafs) {
      s += "\n" + child.printTree(increment + indent);
    }
    return s;
  }
}

38
2017-10-29 18:20



je a écrit une petite bibliothèque qui gère les arbres génériques. C'est beaucoup plus léger que le swing. J'ai aussi un projet maven pour ça.


22
2018-02-09 19:50



public class Tree {
    private List<Tree> leaves = new LinkedList<Tree>();
    private Tree parent = null;
    private String data;

    public Tree(String data, Tree parent) {
        this.data = data;
        this.parent = parent;
    }
}

Vous pouvez évidemment ajouter des méthodes utilitaires pour ajouter / supprimer des enfants.


15
2017-08-19 14:22



Vous devriez commencer par définir ce qu'est un arbre (pour le domaine), il est préférable de définir le interface premier. Toutes les structures d’arbres ne sont pas modifiables, ajouter et retirer Les nœuds devraient être une fonctionnalité optionnelle, nous faisons donc une interface supplémentaire pour cela.

Il n'est pas nécessaire de créer des objets de noeud qui contiennent les valeurs, en fait, je vois cela comme un défaut majeur de conception et de surcharge dans la plupart des implémentations d'arbres. Si vous regardez Swing, le TreeModel est libre de classes de noeud (uniquement DefaultTreeModel fait usage de TreeNode), car ils ne sont pas vraiment nécessaires.

public interface Tree <N extends Serializable> extends Serializable {
    public List<N> getRoots ();
    public N getParent (N node);
    public List<N> getChildren (N node);
}

public interface MutableTree <N extends Serializable> extends Tree<N> {
    public boolean add (N parent, N node);
    public boolean remove (N node, boolean cascade);
}

Étant donné ces interfaces, le code qui utilise des arbres ne doit pas trop se soucier de la façon dont l’arborescence est implémentée. Cela vous permet d'utiliser implémentations génériques aussi bien que spécialisé ceux, où vous réalisez l'arbre en déléguant des fonctions à une autre API.
Exemple: arborescence de fichiers.

public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> {

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<String>();
        tree.add("A", "B");
        tree.add("A", "C");
        tree.add("C", "D");
        tree.add("E", "A");
        System.out.println(tree);
    }

    private final Map<N, N> nodeParent = new HashMap<N, N>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>();

    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<N> getRoots() {
        return getChildren(null);
    }

    @Override
    public N getParent(N node) {
        checkNotNull(node, "node");
        return nodeParent.get(node);
    }

    @Override
    public List<N> getChildren(N node) {
        List<N> children = new LinkedList<N>();
        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);
        }
    }
}

12
2017-08-26 08:14