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).
Réponses:
Ici:
Il s'agit d'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 sont des méthodes d'ajout, de suppression, de traversée et de constructeurs. Le
Node
est le bloc de construction de base duTree
.la source
Tree
classe n'est pas nécessaire, car chacunNode
peut en soi être considéré comme un arbre.Encore une autre structure arborescente:
Exemple d'utilisation:
BONUS
Voir l'arbre à part entière avec:
https://github.com/gt4dev/yet-another-tree-structure
la source
hasNext()
avant chaque appelnext()
pour obtenir des résultats valides. Cela ne fait pas partie de laIterator
spécification.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
JTreePanel
mais 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» .
la source
Et ça?
la source
setAsParent
ougetHead
font 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.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.
la source
Évidemment, vous pouvez ajouter des méthodes utilitaires pour ajouter / supprimer des enfants.
la source
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
TreeModel
est exempt de classes de nœuds (neDefaultTreeModel
fait usage que deTreeNode
), car elles ne sont pas vraiment nécessaires.Structure arborescente mutable (permet d'ajouter et de supprimer des nœuds):
É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
Exemple: arborescence générique (basée sur les relations parent / enfant):
la source
Aucune réponse ne mentionne un code trop simplifié mais fonctionnel, alors voici:
la source
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
la source
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 à: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:
Ou si vous vouliez un trie:
Maintenant tu as dit que tu voulais
Cela ressemble à vos devoirs.
Mais comme je suis raisonnablement sûr que tout délai est maintenant passé…
Cela vous permet d'utiliser comme:
la source
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?
la source
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
la source
Comme la question demande une structure de données disponible, un arbre peut être construit à partir de listes ou de tableaux:
instanceof
peut être utilisé pour déterminer si un élément est un sous-arbre ou un nœud terminal.la source
Object
s serait soit les objets feuilles (par exemple,String
s) soit les branches (représentées par des tableaux). Et cela fonctionne: ce code sera compilé, et il crée un petit arbre deString
s.Aussi simple que possible et très facile à utiliser. Pour l'utiliser, étendez-le:
la source
Par exemple :
la source
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.
la source
J'ai écrit une petite classe "TreeMap" basée sur "HashMap" qui supporte l'ajout de chemins:
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:
Ensuite, vous pouvez en faire un arbre en exécutant:
Et vous obtiendrez un bel arbre. Il devrait être facile de s'adapter à vos besoins.
la source
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.
la source
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:
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}
la source
la source
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!
la source
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
la source
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.
Vous pouvez vérifier, Java Doc et quelques autres .
la source
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.
la source