Costruire una struttura ad albero dall'elenco dei percorsi delle stringhe

Question

Ho una raccolta di percorsi stringa come [" x1 / x2 / x3 ", " x1 / x2 / x4 ", " x1 / x5 "] in un elenco. Ho bisogno di costruire una struttura ad albero da questa lista che può essere ripetuta per ottenere un albero abbastanza stampato. come questo

     x1
    /  \
   x5   x2
       /  \
      x3  x4

Qualche idea / suggerimento? Credo che il problema possa essere prima attaccato elaborando l'elenco di stringhe EDIT: la risposta corretta scelta è stata un'implementazione elegante, anche altri suggerimenti erano buoni.

Answer 1

Segui un'implementazione di ingenua implementazione di un albero visitabile:

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

interfacce per Visitor Pattern:

interface Visitor<T> {

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

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

interface Visitable<T> {

    void accept(Visitor<T> visitor);
}

implementazione di esempio per il modello visitatore:

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

e infine (!!!) un semplice test case:

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

uscita:

forest
  x1
    x2
      x3
      x4
    x5

Answer 2

Basta dividere ogni percorso dal suo delimitatore e quindi aggiungerli a una struttura ad albero uno per uno.
cioè se 'x1' non esiste, crea questo nodo, se esiste, vai su di esso e controlla se c'è un 'x2' e così via ...

Answer 3

Renderei l'albero una stringa alla volta.

Crea un albero vuoto (che ha un nodo radice - suppongo che potrebbe esserci un percorso come " x7 / x8 / x9 ").

Prendi la prima stringa, aggiungi x1 al nodo radice, quindi da x2 a x1, quindi da x3 a x2.

Prendi la seconda stringa, vedi che x1 e x2 sono già lì, aggiungi x4 a x2.

Fallo per ogni percorso che hai.

Answer 4

Crea un nodo oggetto che contiene un genitore (nodo) e un elenco di figli (nodo).

Prima dividi la stringa usando ", " ;. Per ogni stringa divisa, dividi la stringa usando " / " ;. Cerca il primo identificativo del nodo (ad esempio x1) nell'elenco principale. Se riesci a trovarlo, utilizza il nodo per trovare l'identificatore del nodo successivo (ad esempio x2).

Se non riesci a trovare un nodo, aggiungi il nodo all'ultimo nodo che hai trovato negli elenchi esistenti.

Dopo aver creato la struttura dell'elenco, è possibile stampare l'elenco sullo schermo. Lo renderei ricorsivo.

NON TESTATO, solo un'animazione

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

Crea il tuo albero per ogni stringa nell'array. Basta dividere il percorso per '/', controllare se il nodo esiste o no nella tua struttura, se esiste, quindi andare avanti ... altrimenti creare un nuovo nodo e aggiungere questo nodo nei bambini del nodo padre.

Iterate usando la ricorsione.

Di seguito è riportato il modello per il nodo dell'albero.

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

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