Construire une arborescence à partir de la liste des chemins de chaîne

Question

J'ai une collection de chemins de chaînes tels que ["x1 / x2 / x3", "x1 / x2 / x4", "x1 / x5"] dans une liste. J'ai besoin de construire une structure arborescente à partir de cette liste, qui peut être itérée pour obtenir un joli arbre imprimé. comme ça

     x1
    /  \
   x5   x2
       /  \
      x3  x4

Des idées / suggestions? Je pense que le problème peut être attaqué d’abord en traitant la liste des chaînes. EDIT: la bonne réponse choisie était une mise en œuvre élégante, les autres suggestions étaient bonnes aussi.

Answer 1

Suivez une implémentation naïve d'un arbre visitable:

class Tree<T> implements Visitable<T> {

    // NB: LinkedHashSet preserves insertion order
    private final Set<Tree> children = new LinkedHashSet<Tree>();
    private final T data;

    Tree(T data) {
        this.data = data;
    }

    void accept(Visitor<T> visitor) {
        visitor.visitData(this, data);

        for (Tree child : children) {
            Visitor<T> childVisitor = visitor.visitTree(child);
            child.accept(childVisitor);
        }
    }

    Tree child(T data) {
        for (Tree child: children ) {
            if (child.data.equals(data)) {
                return child;
            }
        }

        return child(new Tree(data));
    }

    Tree child(Tree<T> child) {
        children.add(child);
        return child;
    }
}

interfaces pour le modèle de visiteur:

interface Visitor<T> {

    Visitor<T> visitTree(Tree<T> tree);

    void visitData(Tree<T> parent, T data);
}

interface Visitable<T> {

    void accept(Visitor<T> visitor);
}

exemple d'implémentation pour le modèle de visiteur:

class PrintIndentedVisitor implements Visitor<String> {

    private final int indent;

    PrintIndentedVisitor(int indent) {
        this.indent = indent;
    }

    Visitor<String> visitTree(Tree<String> tree) {
        return new IndentVisitor(indent + 2);
    }

    void visitData(Tree<String> parent, String data) {
        for (int i = 0; i < indent; i++) { // TODO: naive implementation
            System.out.print(" ");
        }

        System.out.println(data);
    }
}

et enfin (!!!) un cas de test simple:

    Tree<String> forest = new Tree<String>("forest");
    Tree<String> current = forest;

    for (String tree : Arrays.asList("x1/x2/x3", "x1/x2/x4", "x1/x5")) {
        Tree<String> root = current;

        for (String data : tree.split("/")) {
            current = current.child(data);
        }

        current = root;
    }

    forest.accept(new PrintIndentedVisitor(0));

sortie:

forest
  x1
    x2
      x3
      x4
    x5

Answer 2

Il suffit de scinder chaque chemin par son délimiteur, puis de les ajouter un par un à une arborescence.
c'est-à-dire que si 'x1' n'existe pas, créez ce nœud, s'il existe, accédez-y et vérifiez s'il existe un enfant 'x2' et ainsi de suite ...

Answer 3

Je ferais l'arbre une chaîne à la fois.

Créez un arbre vide (qui a un nœud racine - je suppose qu'il pourrait y avoir un chemin comme "x7 / x8 / x9").

Prenez la première chaîne, ajoutez x1 au nœud racine, puis x2 à x1, puis x3 à x2.

Prenez la deuxième chaîne, voyez que x1 et x2 sont déjà là, ajoutez x4 à x2.

Faites cela pour chaque chemin que vous avez.

Answer 4

Créez un nœud d'objet contenant un parent (Node) et une liste d'enfants (Node).

Commencez par scinder la chaîne en utilisant ",". Pour chaque chaîne scindée, vous scindez la chaîne en utilisant "/". Recherchez le premier identifiant de noeud (par exemple x1) dans la liste racine. Si vous pouvez le trouver, utilisez le nœud pour rechercher le prochain identifiant de nœud (par exemple x2).

Si vous ne trouvez pas de nœud, ajoutez-le au dernier nœud que vous avez pu trouver dans les listes existantes.

Après avoir créé la structure de la liste, vous pouvez imprimer la liste à l'écran. Je voudrais le rendre récursif.

NON TESTE, juste une animation

public void print(List nodes, int deep) {
    if (nodes == null || nodes.isEmpty()) {
        return;
    }

    StringBuffer buffer = new StringBuffer();
    for (int i = 0; i < deep; i++) {
        buffer.append("---");
    }

    for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
        Node node = (Node)iterator.next();

        System.out.println(buffer.toString() + " " + node.getIdentifier());

        print(node.getChildren(), deep + 1);
    }
}

Answer 5

Créez votre arbre pour chaque chaîne du tableau. Juste diviser le chemin pour '/', vérifier si le nœud existe ou non dans votre arborescence, s'il existe, passez à autre chose ... sinon, créez un nouveau nœud et ajoutez ce nœud dans le numéro de l'en-tête du parent.

Itérer en utilisant la récursivité.

Le modèle suivant correspond au noeud de l’arbre.

Class Node{
    string name;
    List<Node> childrens;

    Node(string name){
        this.name = name;
        this.childrens = new List<Node>();
    }
}