Konstruowanie struktury drzewa z listy ścieżek łańcuchowych

Mam kolekcję ścieżek łańcuchowych takich jak ["x1/x2/x3","x1/x2/x4","x1 / x5"] w liście. Muszę skonstruować strukturę podobną do drzewa z tej listy, która może być iteracją, aby uzyskać ładne wydrukowane drzewo. like this 

     x1
    /  \
   x5   x2
       /  \
      x3  x4

Jakieś pomysły/sugestie? Uważam, że problem można najpierw zaatakować, przetwarzając listę edycji łańcuchów: wybrana prawidłowa odpowiedź była elegancką implementacją, inne sugestie też były dobre.

 16
javatree
Author: Nativ, 2009-06-17
Source

5 answers

Podążaj za implementacją naiwnej implementacji drzewa widocznego: 

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

Przykładowa implementacja wzorca Odwiedzin: 

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

I wreszcie (!!!) prosty przypadek testowy: 

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

Wyjście: 

forest
  x1
    x2
      x3
      x4
    x5
 32
Author: dfa,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-06-17 12:26:15

Po prostu podziel każdą ścieżkę za pomocą ogranicznika, a następnie dodaj je do struktury drzewa jeden po drugim.
tzn. jeśli 'x1' nie istnieje utwórz ten węzeł, jeśli istnieje przejdź do niego i sprawdź, czy istnieje potomek 'x2' itd...

 11
Author: Roland Ewald,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-02-07 04:03:34

Zrobiłbym drzewo po jednym sznurku na raz.

Stwórz puste drzewo (które ma węzeł korzeniowy - zakładam, że może być ścieżka w stylu "x7/x8/x9").

Weź pierwszy ciąg, dodaj x1 do węzła głównego, następnie x2 do x1, a następnie x3 do x2.

Weź drugi ciąg, zobacz, że x1 i x2 już tam są, dodaj x4 do x2.

Zrób to dla każdej ścieżki, którą masz.

 4
Author: David Johnstone,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-06-17 07:21:12

Utwórz węzeł obiektu, który zawiera rodzica (węzeł) i listę dzieci (węzeł).

Najpierw podziel łańcuch za pomocą",". Dla każdego podzielonego ciągu można podzielić ciąg za pomocą"/". Wyszukaj pierwszy identyfikator węzła (np. x1) na liście głównej. Jeśli możesz go znaleźć, użyj węzła, aby znaleźć następny identyfikator węzła (np. x2).

Jeśli nie możesz znaleźć węzła, dodaj go do ostatniego węzła, który udało Ci się znaleźć na istniejących listach.

Po utworzeniu listy struktura, możesz wydrukować listę na ekranie. Zrobiłbym to rekurencyjnie.

Nie testowane, tylko animacja 

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);
    }
}
 2
Author: Markus Lausberg,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-06-17 08:08:00

Utwórz drzewo dla każdego ciągu w tablicy. Po prostu podziel ścieżkę dla'/', sprawdź, czy węzeł istnieje w twoim drzewie, czy nie, jeśli istnieje, a następnie przejdź dalej... w przeciwnym razie utwórz nowy węzeł i dodaj go do węzła nadrzędnego.

Iteracja przy użyciu rekurencji.

Poniżej znajduje się model węzła drzewa.

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

    Node(string name){
        this.name = name;
        this.childrens = new List<Node>();
    }
}
 0
Author: Mr_Hmp,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-07-05 15:30:48