Comment implémenter une arborescence de données en Java? [fermé]

496

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

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

  • Le sous-arbre à n'importe quel nœud peut avoir un nombre arbitraire d'enfants
  • Chaque nœud (après la racine) et ses enfants auront une valeur de chaîne
  • 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 prendra un nœud en entrée et retournera toutes les valeurs de chaîne du nœud enfant en sortie)

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

ikl
la source
3
Si vous utilisez Java 8 et souhaitez traverser vos nœuds avec des flux, du filtrage, etc.; alors vous voudrez peut-être jeter un œil à Durian github.com/diffplug/durian
Ned Twigg
1
Vous pouvez utiliser cette API: sourceforge.net/p/treeds4j
Mohamed Ennahdi El Idrissi

Réponses:

306

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

Il s'agit d'une structure arborescente de base qui peut être utilisée pour Stringou 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 sont des méthodes d'ajout, de suppression, de traversée et de constructeurs. Le Nodeest le bloc de construction de base du Tree.

jjnguy
la source
304
À proprement parler, la Treeclasse n'est pas nécessaire, car chacun Nodepeut en soi être considéré comme un arbre.
Joachim Sauer
34
@Joa, j'aime avoir une structure pour contenir la racine. Vous pouvez ajouter des méthodes à la classe d'arbre qui ont plus de sens d'appeler sur un arbre plutôt que sur un seul nœud.
jjnguy
24
@Justin: par exemple? C'est une question honnête: je ne peux pas penser à une seule méthode qui ait du sens sur tout l'arbre qui n'a pas de sens sur un sous-arbre.
Joachim Sauer
22
Je suis d'accord avec @Joa que la classe Tree n'est pas nécessaire. Je préfère laisser la nature récursive des arbres explicite dans le code en n'ajoutant pas une classe Tree distincte et en utilisant systématiquement la classe Node. Au lieu de cela, je nomme une variable «arbre» ​​ou «racine» s'il doit être clair que vous traitez avec le nœud racine d'un arbre.
jvdbogae
89
@Joa Un moi de quatre ans plus âgé est entièrement d'accord avec vous. Nix la classe d'arbre.
jjnguy
122

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

Grzegorz Dev
la source
2
Je viens de trouver votre bibliothèque extrêmement utile. Je vous remercie. Mais je voudrais savoir comment implémenter dynamiquement le remplissage de la structure arborescente basée sur la relation de référence entre parent et enfant. Exemple donné: j'ai un membre1 parrainer un autre membre2, et membre2 parrainer le membre 3 et ainsi de suite. J'ai déjà la relation des enregistrements de table, mais je ne suis pas sûr de pouvoir les remplir dans un arbre en utilisant votre bibliothèque.
d4v1dv00
1
à partir de 2016, le lien ne contient aucun fichier source ni téléchargement
Sharon Ben Asher
2
À mon avis, cette réponse trois ans après la réponse la mieux notée ci-dessus est la plus propre. Cependant, je remplacerais la LinkedList par une ArrayList pour this.children.
HopeKing
1
J'utiliserais un ensemble pour les enfants.
DPM
Je peux me tromper mais il semble qu'avec cette implémentation, vous devez appeler hasNext()avant chaque appel next()pour obtenir des résultats valides. Cela ne fait pas partie de la Iteratorspécification.
Robert Lewis
97

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

Jetez un œil à javax.swing.tree , TreeModel et TreeNode . Ils sont conçus pour être utilisés avec JTreePanelmais ils sont, en fait, une assez bonne implémentation d'arborescence 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 les «profils compacts» .

Gareth Davis
la source
5
Oui, je les ai utilisés dans le passé, et ils feront tout ce que vous voulez d'un arbre. Le seul inconvénient auquel je peux penser est la longueur des noms de leurs classes d'implémentation respectives: DefaultTreeModel et DefaultMutableTreeNode. Verbose, mais ce n'est pas si important que ça, je suppose.
Ultimate Gobblement
4
Un bon moyen d'y faire face est de créer quelques méthodes statiques newModel () et newNode (), puis de les importer statiquement.
Gareth Davis
140
J'éviterais d'utiliser des bibliothèques Swing sur des fonctions non liées à Swing. Il s'agit d'une mauvaise pratique de codage . Vous ne savez jamais comment Swing implémente leurs arbres, quelles sont leurs dépendances et comment cela pourrait changer à l'avenir. Swing n'est pas une bibliothèque d'utilitaires mais une bibliothèque d'interface utilisateur.
jasop
44
Je pense que les mauvaises pratiques de codage sont un peu dures.
Gareth Davis
51
javax.swing.tree.TreeModel est une interface publique (exactement comme java.util.List) et il n'y aura pas de modifications incompatibles. Un avantage supplémentaire est que vous pouvez facilement déboguer / visualiser votre arborescence pendant le développement.
lbalazscs
45

Et ça?

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

/**
  * @author [email protected] (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;
  }
}
MountainX
la source
5
Comment DFS serait-il implémenté sur une arborescence créée à l'aide de cet objet de classe?
leba-lev
3
Comment la suppression d'une feuille serait-elle implémentée à l'aide de cette classe?
ghedas
2
À quoi servirait le champ principal?
Acour83
2
Cela aurait été formidable si cette classe avait de la documentation. Je ne comprends pas très bien ce que les méthodes aiment setAsParentou getHeadfont et c'est le moment où je pourrais vraiment obtenir de l'aide sur les structures de données arborescentes. Même la source originale du document n'a aucun commentaire.
catastrophekid
23

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

Vivin Paliath
la source
3
Je l'utilise maintenant, fonctionne à merveille. J'ai dû changer la source de manière significative pour mes propres personnalisations, mais c'était un excellent point de départ. Merci Vivin!
jasop
20
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;
    }
}

Évidemment, vous pouvez ajouter des méthodes utilitaires pour ajouter / supprimer des enfants.

PaulJWilliams
la source
1
Cela suggère que le parent d'un arbre est un arbre. Je crois que vous essayez de créer une classe Tree Node.
Madhur Bhargava
16

Vous devez commencer par définir ce qu'est une arborescence (pour le domaine), cela est mieux fait en définissant d'abord l' interface . Toutes les structures d'arbres ne sont pas modifiables, pouvant être ajoutées et supprimées nœuds devrait être une fonctionnalité facultative, 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 de conception majeur et une surcharge dans la plupart des implémentations d'arborescence. Si vous regardez Swing, le TreeModelest exempt de classes de nœuds (ne DefaultTreeModelfait usage que de TreeNode), car elles ne sont pas vraiment nécessaires.

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

Structure arborescente mutable (permet d'ajouter et de supprimer des nœuds):

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

Étant donné ces interfaces, le code qui utilise des arbres n'a pas à se soucier beaucoup de la façon dont l'arbre est implémenté. Cela vous permet d'utiliser des implémentations génériques ainsi que des implémentations spécialisées. , où vous réalisez l'arborescence en déléguant des fonctions à une autre API.

Exemple: arborescence de fichiers

public class FileTree implements Tree<File> {

    @Override
    public List<File> getRoots() {
        return Arrays.stream(File.listRoots()).collect(Collectors.toList());
    }

    @Override
    public File getParent(File node) {
        return node.getParentFile();
    }

    @Override
    public List<File> getChildren(File node) {
        if (node.isDirectory()) {
            File[] children = node.listFiles();
            if (children != null) {
                return Arrays.stream(children).collect(Collectors.toList());
            }
        }
        return Collections.emptyList();
    }
}

Exemple: arborescence générique (basée sur les relations parent / enfant):

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

    public static void main(String[] args) {

        MutableTree<String> 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<N, N> nodeParent = new HashMap<>();
    private final LinkedHashSet<N> 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<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<>();
        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);
        }
    }
}
Peter Walser
la source
1
Je suis confronté à un problème lorsque je suis cette structure lorsque je fais tree.add ("A", "B"); tree.add ("A", "C"); tree.add ("C", "D"); tree.add ("E", "A"); E est un parent de A Comment procédons-nous?
saNiks
1
Salut saNicks, il y avait un bug dans le code ci-dessus qui a empêché l'ajout de la dernière relation. Il est maintenant corrigé, et j'ai également ajouté des vérifications non nulles et (plus important): des vérifications cycliques qui empêchent de violer la structure arborescente (en ajoutant un code ou l'un de ses ancêtres en tant qu'enfant à lui-même). Merci pour l'astuce!
Peter Walser
1
J'ai corrigé le bogue si quelqu'un cherchait un correctif pour ce bogue, ce que vous devez faire est de voir si la méthode add renvoie false et si elle est fausse, créez simplement un nouveau LinkedHashSet <N> temporaire et clonez la liste des nœuds de l'arbre dedans, alors vous pouvez effacer l'arborescence, ajoutez le nœud parent qui n'a pas été ajouté à l'étape précédente, puis ajoutez à nouveau tout le tempNode à l'arbre parent ... Merci pour la structure!
saNiks
2
Supprimez simplement ces modificateurs publics inutiles de vos interfaces.
Hamedz
1
comment puis-je générer un tableau json à partir de cela
Pawan Pandey
12

Aucune réponse ne mentionne un code trop simplifié mais fonctionnel, alors voici:

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

Vous pouvez utiliser n'importe quelle API XML de Java en tant que document et nœud ... car XML est une structure arborescente avec des chaînes

Raja Nagendra Kumar
la source
5
excellente idée, nous pourrions utiliser en mémoire le schéma XML en utilisant dom4j + jaxen xpath pour rechercher des nœuds.
Ben Rhouma Zied
8

Si vous faites du codage sur tableau blanc, une interview ou même que vous prévoyez simplement d'utiliser un arbre, la verbosité de tout cela est un peu trop.

Il faut en outre dire que la raison pour laquelle un arbre n'est pas là comme, disons, un Pair(à propos duquel la même chose pourrait être dite), c'est parce que vous devriez encapsuler vos données dans la classe qui l'utilise, et l'implémentation la plus simple ressemble à:

/***
/* 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<Node> nodes;
}

C'est vraiment tout pour un arbre de largeur arbitraire.

Si vous vouliez un arbre binaire, il est souvent plus facile à utiliser avec des champs nommés:

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

Ou si vous vouliez un trie:

private class Node {
  String value;
  Map<char, Node> nodes;
}

Maintenant tu as dit que tu voulais

pour pouvoir obtenir tous les enfants (une sorte de liste ou de tableau de chaînes) étant donné une chaîne d'entrée représentant un nœud donné

Cela ressemble à vos devoirs.
Mais comme je suis raisonnablement sûr que tout délai est maintenant passé…

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<String> list(Node node, String find) {
   return list(node, find, new ArrayList<String>(), false);
 }

 static private ArrayList<String> list(
     Node node,
     String find,
     ArrayList<String> 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()));
 }
}

Cela vous permet d'utiliser comme:

$ 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
[]
dlamblin
la source
7

Dans le même sens que la réponse de Gareth, consultez DefaultMutableTreeNode . Ce n'est pas générique, mais semble convenir autrement. Même s'il se trouve dans le package javax.swing, il ne dépend d'aucune classe AWT ou Swing. En fait, le code source a en fait le commentaire// ISSUE: this class depends on nothing in AWT -- move to java.util?

marque
la source
Lol, comment as-tu rencontré ce cours?
Pacerier
7

Il existe quelques structures de données d'arbre en Java, telles que DefaultMutableTreeNode dans JDK Swing, Tree dans le package d'analyseur Stanford et d'autres codes de jouets. Mais aucun de ces éléments n'est suffisant mais assez petit pour un usage général.

Le projet d' arbre Java tente de fournir une autre structure de données d'arbre à usage général en Java. La différence entre cela et les autres est

  • Complètement gratuit. Vous pouvez l'utiliser n'importe où (sauf dans vos devoirs: P)
  • Petit mais assez général. J'ai mis tout la structure des données dans un fichier de classe, il serait donc facile de copier / coller.
  • Pas seulement un jouet. Je connais des dizaines de codes d'arbre Java qui ne peuvent gérer que des arbres binaires ou des opérations limitées. Ce TreeNode est bien plus que cela. Il fournit différentes façons de visiter les nœuds, tels que les précommandes, les post-commandes, la largeur, les feuilles, le chemin d'accès à la racine, etc. De plus, les itérateurs sont également fournis pour la suffisance.
  • D'autres utilitaires seront ajoutés. Je suis prêt à ajouter plus d'opérations pour rendre ce projet complet, surtout si vous envoyez une demande via github.
Yifan Peng
la source
5

Comme la question demande une structure de données disponible, un arbre peut être construit à partir de listes ou de tableaux:

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

instanceof peut être utilisé pour déterminer si un élément est un sous-arbre ou un nœud terminal.

Olathe
la source
2
Assez moche. Et cela ne fonctionne pas, si vos objets de données peuvent être des tableaux ou des listes.
user686249
1
Je suis d'accord pour dire que c'est moche. Le Objects serait soit les objets feuilles (par exemple, Strings) soit les branches (représentées par des tableaux). Et cela fonctionne: ce code sera compilé, et il crée un petit arbre de Strings.
Olathe
5
public abstract class Node {
  List<Node> children;

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

Aussi simple que possible et très facile à utiliser. Pour l'utiliser, étendez-le:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}
meilleur
la source
3

Par exemple :

import java.util.ArrayList;
import java.util.List;



/**
 * 
 * @author X2
 *
 * @param <T>
 */
public class HisTree<T> 
{
    private Node<T> root;

    public HisTree(T rootData) 
    {
        root = new Node<T>();
        root.setData(rootData);
        root.setChildren(new ArrayList<Node<T>>());
    }

}

class Node<T> 
{

    private T data;
    private Node<T> parent;
    private List<Node<T>> children;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getParent() {
        return parent;
    }
    public void setParent(Node<T> parent) {
        this.parent = parent;
    }
    public List<Node<T>> getChildren() {
        return children;
    }
    public void setChildren(List<Node<T>> children) {
        this.children = children;
    }
}
JAN
la source
3

Dans le passé, je viens d'utiliser une carte imbriquée pour cela. C'est ce que j'utilise aujourd'hui, c'est très simple mais ça correspond à mes besoins. Peut-être que cela en aidera un autre.

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<K, V> {
    private final Map root = new HashMap<>();

    public NestedMap<K, V> put(K key) {
        Object nested = root.get(key);

        if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>());
        return (NestedMap<K, V>) nested;
    }

    public Map.Entry<K,V > put(K key, V value) {
        root.put(key, value);

        return (Map.Entry<K, V>) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get();
    }

    public NestedMap<K, V> get(K key) {
        return (NestedMap<K, V>) 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<String, Integer> test = new NestedMap<>();
        test.put("a").put("b").put("c", 12);
        Map.Entry<String, Integer> 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"));
    }
}
KIC
la source
3

J'ai écrit une petite classe "TreeMap" basée sur "HashMap" qui supporte l'ajout de chemins:

import java.util.HashMap;
import java.util.LinkedList;

public class TreeMap<T> extends LinkedHashMap<T, TreeMap<T>> {

    public void put(T[] path) {
        LinkedList<T> list = new LinkedList<>();
        for (T key : path) {
            list.add(key);
        }
        return put(list);
    }

    public void put(LinkedList<T> path) {
        if (path.isEmpty()) {
            return;
        }
        T key = path.removeFirst();
        TreeMap<T> val = get(key);
        if (val == null) {
            val = new TreeMap<>();
            put(key, val);
        }
        val.put(path);
    }

}

Il peut être utilisé pour stocker un arbre de choses de type "T" (générique), mais ne prend pas (encore) en charge le stockage de données supplémentaires dans ses nœuds. Si vous avez un fichier comme celui-ci:

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

Ensuite, vous pouvez en faire un arbre en exécutant:

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

Et vous obtiendrez un bel arbre. Il devrait être facile de s'adapter à vos besoins.

mevdschee
la source
2

Vous pouvez utiliser la classe HashTree incluse dans Apache JMeter qui fait partie du projet Jakarta.

La classe HashTree est incluse dans le package org.apache.jorphan.collections. Bien que ce package ne soit pas publié en dehors du projet JMeter, vous pouvez l'obtenir facilement:

1) Téléchargez les sources JMeter .

2) Créez un nouveau package.

3) Copiez dessus / src / jorphan / org / apache / jorphan / collections /. Tous les fichiers sauf Data.java

4) Copiez également /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree est prêt à l'emploi.

David
la source
2

Il n'y a pas de structure de données spécifique en Java qui convient à vos besoins. Vos besoins sont assez spécifiques et pour cela, vous devez concevoir votre propre structure de données. En examinant vos besoins, tout le monde peut dire que vous avez besoin d'une sorte d'arbre n-aire avec des fonctionnalités spécifiques. Vous pouvez concevoir votre structure de données de la manière suivante:

  1. La structure du nœud de l'arbre serait comme le contenu du nœud et la liste des enfants comme: classe Node {valeur de chaîne; Lister les enfants;}
  2. Vous devez récupérer les enfants d'une chaîne donnée, vous pouvez donc avoir 2 méthodes 1: Node searchNode (String str), retournera le nœud qui a la même valeur que l'entrée donnée (utilisez BFS pour la recherche) 2: List getChildren (String str): cette méthode appellera en interne le searchNode pour obtenir le nœud ayant la même chaîne, puis elle créera la liste de toutes les valeurs de chaîne des enfants et retournera.
  3. Vous devrez également insérer une chaîne dans l'arborescence. Vous devrez écrire une méthode, dites void insert (String parent, String value): cela recherchera à nouveau le nœud ayant une valeur égale à parent et ensuite vous pouvez créer un nœud avec une valeur donnée et ajouter à la liste des enfants au parent trouvé .

Je suggère que vous écriviez la structure du nœud dans une classe comme Class Node {String value; Lister les enfants;} et toutes les autres méthodes comme search, insert et getChildren dans une autre classe NodeUtils afin que vous puissiez également passer la racine de l'arborescence pour effectuer des opérations sur une arborescence spécifique comme: class NodeUtils {public static Node search (Node root, String value) {// effectuer BFS et retourner Node}

aman rastogi
la source
2
    // 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);
  }
}
Tony Narloch
la source
3
Veuillez ne pas simplement vider le code - expliquez ce qu'il fait, et surtout pourquoi il diffère (est meilleur) que toutes les autres réponses.
Jan Doggen
2

J'ai écrit une bibliothèque arborescente qui fonctionne bien avec Java8 et qui n'a pas d'autres dépendances. Il fournit également une interprétation lâche de certaines idées de la programmation fonctionnelle et vous permet de mapper / filtrer / tailler / rechercher l'ensemble de l'arborescence ou des sous-arbres.

https://github.com/RutledgePaulV/prune

L'implémentation ne fait rien de spécial avec l'indexation et je ne me suis pas éloigné de la récursivité, il est donc possible qu'avec de grands arbres les performances se dégradent et vous pourriez faire exploser la pile. Mais si tout ce dont vous avez besoin est un arbre simple de faible à moyenne profondeur, je pense que cela fonctionne assez bien. Il fournit une définition saine (basée sur la valeur) de l'égalité et il a également une implémentation toString qui vous permet de visualiser l'arbre!

RutledgePaulV
la source
1

Veuillez vérifier le code ci-dessous, où j'ai utilisé des structures de données Tree, sans utiliser les classes Collection. Le code peut avoir des bugs / améliorations mais veuillez l'utiliser juste pour référence

package com.datastructure.tree;

public class BinaryTreeWithoutRecursion <T> {

    private TreeNode<T> root;


    public BinaryTreeWithoutRecursion (){
        root = null;
    }


    public void insert(T data){
        root =insert(root, data);

    }

    public TreeNode<T>  insert(TreeNode<T> node, T data ){

        TreeNode<T> newNode = new TreeNode<>();
        newNode.data = data;
        newNode.right = newNode.left = null;

        if(node==null){
            node = newNode;
            return node;
        }
        Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
        queue.enque(node);
        while(!queue.isEmpty()){

            TreeNode<T> 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<T> root){
        if(root!=null){

            inOrderPrint(root.left);
            System.out.println(root.data);
            inOrderPrint(root.right);
        }

    }

    public void postOrderPrint(TreeNode<T> 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<T> 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 <Integer> 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();

    }

}
Amit Mathur
la source
2
" sans utiliser les classes Collection " Ah? D'où vient la classe Queue? Et comme dit ci-dessus, c'est un arbre binaire, échouant à la première exigence (n'importe quel nombre de nœuds enfants).
PhiLho
1

Vous pouvez utiliser la classe TreeSet dans java.util. *. Il fonctionne comme un arbre de recherche binaire, il est donc déjà trié. La classe TreeSet implémente les interfaces Iterable, Collection et Set. Vous pouvez parcourir l'arborescence avec l'itérateur comme un ensemble.

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

Vous pouvez vérifier, Java Doc et quelques autres .

Oguz
la source
-1

Implémentation Tree personnalisée de Tree sans utiliser le cadre Collection. Il contient différentes opérations fondamentales nécessaires à l'implémentation de Tree.

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

}
Shivam Verma
la source
11
C'est un arbre binaire, il échoue à la première exigence de l'OP ...
PhiLho