Konstrukt eine Baumstruktur von der Liste von Pfaden String

Question

Ich habe eine Sammlung von String-Pfaden wie [ "x1 / x2 / x3", "x1 / x2 / x4", "x1 / x5"] in einer Liste. Ich brauche eine baumartige Struktur aus dieser Liste zu konstruieren, die durchlaufen werden können ziemlich gedruckt Baum zu erhalten. wie diese

     x1
    /  \
   x5   x2
       /  \
      x3  x4

Irgendwelche Ideen / Anregungen? Ich glaube, dass das Problem durch die Verarbeitung die Liste von Strings EDIT zuerst angegriffen werden kann: Die richtige Antwort gewählt war eine elegante Implementierung, andere Vorschläge waren gut zu

.

Answer 1

eine Implementierung der naiven Implementierung eines besuchbar Baum wie folgt vor:

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

Schnittstellen für Besucher Muster:

interface Visitor<T> {

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

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

interface Visitable<T> {

    void accept(Visitor<T> visitor);
}

Beispielimplementierung für Besucher Muster:

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

und schließlich (!!!) ein einfacher Testfall:

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

Ausgabe:

forest
  x1
    x2
      x3
      x4
    x5

Answer 2

aufgeteilt nur jeden Pfad durch seinen Begrenzer und dann fügen Sie sie in einer Baumstruktur einer nach dem anderen.
das heißt, wenn 'x1' existiert nicht diesen Knoten erstellen, wenn es vorhanden ist, um es geht und ob es ein Kind 'x2' ist und so weiter ...

Answer 3

würde ich den Baum eine Saite auf einmal machen.

Machen Sie einen leeren Baum (die einen Stammknoten hat - ich nehme an, es könnte ein Weg wie "X7 / X8 / X9" sein).

Nehmen Sie

den ersten String, fügen x1 zu dem Wurzelknoten, dann x2 auf x1, dann x3 x2.

Nehmen Sie die zweite Saite, dass x1 und x2 sind schon da, fügen x4 x2.

Tun Sie dies für jeden Pfad, den Sie haben.

Answer 4

Ein Objekt Knoten erstellen, das enthält einen Elternteil (Knoten) und eine Liste der Kinder (Node).

Split zuerst die Zeichenfolge mit "". Für jede gespaltet Zeichenfolge geteilt Sie die Zeichenfolge mit „/“. Suchen nach der ersten Knotenkennung (z.B. X1) in der Wurzelliste. Wenn Sie es finden können, verwenden Sie den Knoten der nächsten Knotenkennung (z x2) zu finden.

Wenn Sie nicht einen Knoten finden, fügen Sie den Knoten der letzte Knoten Sie in der Lage war, in den bestehenden Listen zu finden.

Nachdem Sie die Listenstruktur erstellt haben, können Sie die Liste auf dem Bildschirm drucken. Ich würde es rekursiv machen.

nicht getestet, nur eine 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

Machen Sie Ihren Baum für jeden String in Array. aufgeteilt Pfad nur für ‚/‘, zu überprüfen, ob der Knoten in Ihrem Baum vorhanden ist oder nicht, wenn es auf dann bewegen existiert ... schafft sonst einen neuen Knoten und fügen Sie diesen Knoten in den Kindern von Eltern-Knoten.

Iterate mit Rekursion.

Im Anschluss ist das Modell für Baum des Knotens.

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

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