Comment implémenter une structure de données arborescente en Java ?

Question

Existe-t-il une classe standard de la bibliothèque Java pour représenter un arbre en Java ?

Plus précisément, je dois représenter les éléments suivants :

• Le sous-arbre de n'importe quel nœud peut avoir un nombre arbitraire d'enfants.
• Chaque noeud (après la racine) et ses enfants auront une valeur de chaîne de caractères
• J'ai besoin d'obtenir tous les enfants (une sorte de liste ou de tableau de chaînes) d'un nœud donné et sa valeur de chaîne (c'est-à-dire une méthode qui prend un nœud en entrée et renvoie toutes les valeurs de chaîne des nœuds enfants en sortie).

Existe-t-il une structure disponible pour cela ou dois-je créer la mienne (si tel est le cas, des suggestions de mise en œuvre seraient les bienvenues).

Answer 1

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 structure arborescente 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 devez ajouter, ce sont des méthodes pour ajouter à, enlever de, traverser, et des constructeurs. Le site Node est l'élément de base de la Tree .

Answer 2

Encore une autre structure arborescente :

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

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

• itérateur
• recherche
• Java/C#

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

Answer 3

Il existe en fait une très bonne structure arborescente implémentée dans le JDK.

Jetez un coup d'œil à javax.swing.tree , Modèle d'arbre y TreeNode . Ils sont conçus pour être utilisés avec le JTreePanel mais il s'agit, en fait, d'une assez bonne implémentation de l'arbre et rien ne vous empêche de l'utiliser sans 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 répertoire de l'utilisateur. Profils compacts .

Answer 4

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

Answer 5

I a écrit une petite bibliothèque qui gère les arbres génériques. C'est beaucoup plus léger que les trucs de swing. J'ai aussi une projet maven pour cela.