Menu

Structure Arbres Java [Résolu]

- - Dernière réponse :  Tir02 - 25 févr. 2019 à 12:40
Bonjour à tous,

Je cherche une structure en Java pour les structures d'arbres n-aires.
Dans la JavaDoc j'ai trouvé TreeMap qui a l'air le plus abstrait des arbres, avec différentes classes qui en proviennent (TreeSet etc.).
https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

Mais à chaque fois ça a l'air très orienté accès par clefs style HashMap, plutôt que d'avoir des méthodes pour obtenir les children ou les ancestor pour les différents nœuds (c'est en fait ce dont j'aurais besoin pour naviguer dans mon contexte). J'ai l'impression qu'on ne peut accéder que par clefs et par valeurs...
Dans ce genre de cas, quelle structure utilisez-vous pour avoir un arbre avec des accès directs aux fils et parents etc. ? (c'est simple à faire soi-même mais il existe forcément déjà qqch en Java quand même non ?)
Un grand merci pour votre aide !
Afficher la suite 

1 réponse

Messages postés
16004
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
4 juillet 2019
2382
0
Merci
Bonjour,

Comme son nom l'indique TreeMap est un arbre, certes, mais c'est surtout une Map, donc forcément avec le même système de clé/valeur que la HashMap ou toutes les autres Map.

De même pour le TreeSet, qui avant tout un Set, mais implémenté à partir d'un arbre.

Il faut distinguer, la structure de données d'une part et son utilisation d'autre part. Par exemple une ArrayList fonctionne comme une liste, même si sa structure de donnée est basée sur un tableau.

De ce que je comprends ce que tu veux c'est une utilisation de données arborescente (type arbre généalogique), mais la structure optimisée des arbres bicolores (comme le TreeMap) n'est pas faite pour ça car lorsque l'arbre s'équilibre (à chaque ajout/suppression), la hiérarchie parent/enfant est modifiée.

Dans l'API standard de Java, ce qui s'en rapprocherait le plus c'est JTree
https://docs.oracle.com/javase/tutorial/uiswing/components/tree.html
Mais ça peut être un peu lourd de travailler avec des éléments graphiques de Swing juste pour faire de la manipulation de données...

Éventuellement, tu peux utiliser une bibliothèque tierce de manipulation de graphes (un arbre est un cas particulier de graphe), par exemple GraphStream :
http://graphstream-project.org/doc/Tutorials/Getting-Started/
Merci beaucoup de ta réponse.

Oui en effet c'est un arbre de type généalogique que je souhaites utiliser. J'ai pour l'instant écrit mes propres classes, mais la manière d'accéder aux parents est un peu redondante car je stocke les parents et les enfants, et de plus il est possible de faire des cycles, ce que je souhaite éviter.

J'ai regardé les 2 liens, et en effet le 1er a l'air très orienté visualisation graphique des arbres (je n'ai pas de partie graphique en l’occurrence pour ces arbres) que manipulation de données.

Je me penche sur GraphStream mais de ce que j'en voie il n'y a pas vraiment de "hiérarchie" père/fils, et la spécificité de ce que je voudrais faire est descendante (c'est des éléments accessibles en fonction de l'état des parents).
Cela doit probablement exister dans des implantations sur Internet mais je pensais trouver déjà qqch dans la Java doc....
KX
Messages postés
16004
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
4 juillet 2019
2382 > Tir02 -
Dans l'API standard il n'y a rien qui fait ça.

Pour GraphStream tu peux travailler avec des graphes orientés, les arcs représenteront donc ta hiérarchie.

Exemple :

import org.graphstream.graph.Graph;
import org.graphstream.graph.implementations.SingleGraph;

public class Main {
    public static void main(String[] args) {
        Graph graph = new SingleGraph("Arbre", false, true);
        graph.addEdge("père -> fils", "père", "fils", true);
        System.out.println(graph.getId()); // Arbre
        System.out.println(graph.getEdge(0).getId()); // père -> fils
        System.out.println(graph.getEdge(0).getNode0().getId()); // père
        System.out.println(graph.getEdge(0).getNode1().getId()); // fils
    }
}

Tu peux bien sûr faire ta propre classe d'arbre qui utilise GraphStream en interne mais avec des méthodes utilitaires qui font ce que tu veux.

Exemple :

public static List<Node> getEnfants(Graph graph, Node parent) {
    List<Node> result = new ArrayList<Node>();
    for (Edge edge : parent.getLeavingEdgeSet()) {
        result.add(edge.getNode1());
    }
    return result;
}

public static List<Node> getParents(Graph graph, Node enfant) {
    List<Node> result = new ArrayList<Node>();
    for (Edge edge : enfant.getEnteringEdgeSet()) {
        result.add(edge.getNode0());
    }
    return result;
}
C'est noté, merci beaucoup d'avoir pris le temps pour cette réponse complète :)
Commenter la réponse de KX