Construir uma estrutura de árvore da lista de caminhos de cordas

Question

Eu tenho uma coleção de caminhos de corda como [ "x1 / x2 / x3", "x1 / x2 / x4", "x1 / x5"] em uma lista. Eu preciso construir uma árvore-como estrutura a partir desta lista que pode ser repetido para obter uma árvore bonita impressa. como esta

     x1
    /  \
   x5   x2
       /  \
      x3  x4

Qualquer ideias / sugestões? Eu acredito que o problema pode ser atacado pela primeira vez pelo processamento da lista de strings EDIT:. A resposta correta escolhido foi uma implementação elegante, outras sugestões foram muito bons também

Answer 1

Siga uma implementação de implementação ingênua de uma árvore visitável:

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 para padrão do visitante:

interface Visitor<T> {

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

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

interface Visitable<T> {

    void accept(Visitor<T> visitor);
}

implementação de exemplo para padrão do visitante:

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, finalmente, (!!!) um caso de teste simples:

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

saída:

forest
  x1
    x2
      x3
      x4
    x5

Answer 2

Apenas dividir cada caminho por seu delimitador e, em seguida, adicioná-los a uma estrutura de árvore, um por um.
ou seja, se 'x1' não existe criar este nó, se ela existe Vá para ele e cheque se há um 'x2' criança e assim por diante ...

Answer 3

Eu faria a árvore uma corda de cada vez.

Faça uma árvore vazia (que tem um nó raiz - Presumo que poderia haver um caminho como "x7 / x8 / x9").

Tome a primeira corda, adicione x1 para o nó raiz, então x2 para x1, então x3 para x2.

Tome a segunda corda, ver que X1 e X2 já estão lá, adicione x4 para x2.

Faça isso para cada caminho que você tem.

Answer 4

Criar um nó de objeto que contém um pai (Node) e uma lista de crianças (Node).

Primeiro dividir a string usando "". Para cada corda splitted você dividir a string usando "/". Procurar o identificador primeiro nó (por exemplo, x1) na lista de raiz. Se você pode encontrá-lo, use o nó para encontrar o identificador próximo nó (por exemplo, x2).

Se você não consegue encontrar um nó, adicione o nó para o último nó que você foi capaz de encontrar nas listas existentes.

Depois de ter criado a estrutura de lista, você pode imprimir a lista para a tela. Eu faria recursiva.

NÃO TESTADO, apenas uma animação

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

Faça sua árvore para cada string no array. caminho apenas de divisão para '/', verifique se o nó existe na sua árvore ou não, se ele existir, em seguida, seguir em frente ... caso contrário criar um novo nó e adicionar este nó em crianças de nó pai.

Iterate usando recursão.

A seguir é o modelo para o nó de árvore.

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

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