Construir una estructura de árbol a partir de la lista de rutas de cadena

Question

Tengo una colección de rutas de cadena como [" x1 / x2 / x3 ', " x1 / x2 / x4 ", " x1 / x5 "] en una lista. Necesito construir una estructura similar a un árbol a partir de esta lista que se puede iterar para obtener un árbol bastante impreso. como este

     x1
    /  \
   x5   x2
       /  \
      x3  x4

¿Alguna idea / sugerencia? Creo que el problema se puede atacar primero al procesar la lista de cadenas EDITAR: La respuesta correcta elegida fue una implementación elegante, otras sugerencias también fueron buenas.

Answer 1

Siga una implementación de la implementación ingenua de un árbol 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 para el patrón de 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);
}

ejemplo de implementación para el patrón de 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);
    }
}

y finalmente (!!!) un caso de prueba 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));

salida:

forest
  x1
    x2
      x3
      x4
    x5

Answer 2

Simplemente divida cada ruta por su delimitador y luego agréguelas una por una a la estructura de árbol.
es decir, si 'x1' no existe cree este nodo, si existe, vaya a él y compruebe si hay un 'x2' secundario y así sucesivamente ...

Answer 3

Haría del árbol una cadena a la vez.

Haz un árbol vacío (que tiene un nodo raíz; supongo que podría haber una ruta como " x7 / x8 / x9 ").

Toma la primera cadena, agrega x1 al nodo raíz, luego x2 a x1, luego x3 a x2.

Toma la segunda cadena, observa que x1 y x2 ya están allí, agrega x4 a x2.

Haz esto para cada ruta que tengas.

Answer 4

Cree un nodo de objeto que contenga un padre (nodo) y una lista de hijos (nodo).

Primero divide la cadena usando ", " ;. Por cada cadena dividida, se divide la cadena usando " / " ;. Busque el primer identificador de nodo (por ejemplo, x1) en la lista raíz. Si puede encontrarlo, use el nodo para encontrar el siguiente identificador de nodo (por ejemplo, x2).

Si no puede encontrar un nodo, agregue el nodo al último nodo que pudo encontrar en las listas existentes.

Una vez que haya creado la estructura de la lista, puede imprimir la lista en la pantalla. Lo haría recursivo.

NO PROBADO, solo una animación

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

Haz tu árbol para cada cadena en la matriz. Simplemente divida la ruta para '/', verifique si el nodo existe en su árbol o no, si existe, continúe ... de lo contrario, cree un nuevo nodo y agregue este nodo en los niños del nodo principal.

Iterar usando la recursión.

El siguiente es el modelo para el nodo del árbol.

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

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