17

Вопрос по java – Построить древовидную структуру из списка строковых путей

У меня есть набор строковых путей, таких как [& lt; x1 / x2 / x3 & quot ;, & quot; x1 / x2 / x4 & quot; & quot; x1 / x5 & quot;] в списке. Мне нужно построить древовидную структуру из этого списка, которую можно повторять, чтобы получить красивое печатное дерево. как это

     x1
    /  \
   x5   x2
       /  \
      x3  x4

Есть идеи / предложения? Я считаю, что проблему можно сперва решить, обработав список строк. РЕДАКТИРОВАТЬ: правильный ответ был элегантной реализацией, другие предложения тоже были хорошими.

  • Что & APOS; sIndentVisitor реализация?

    от
  • Спасибо за код dfa; Отлично работает. Реализация шаблона посетителя аккуратна.

    от sushant
  • @Feeco вы можете использоватьPrintIndentedVisitor и это работает как шарм

    от
  • Как мне это реализовать? Любой пример GitHub?

    от
  • Выходи за меня! Спасибо за очень полезный ответ.

    от
  • Может быть, вам будет интересно прочитать мою текущую рабочую реализацию, которая решит вашу (и мою) проблему :) Посмотрите:stackoverflow.com/a/10935115/737636

    от StErMi
5 ответов
  • 32

    Следуйте за реализацией наивной реализации доступного дерева:

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

    интерфейсы для шаблона посетителя:

    interface Visitor<T> {
    
        Visitor<T> visitTree(Tree<T> tree);
    
        void visitData(Tree<T> parent, T data);
    }
    
    interface Visitable<T> {
    
        void accept(Visitor<T> visitor);
    }
    

    Пример реализации шаблона посетителя:

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

    и наконец (!!!) простой тестовый пример:

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

    выход:

    forest
      x1
        x2
          x3
          x4
        x5
    

  • 11

    Просто разделите каждый путь по его разделителю

    а затем добавьте их в древовидную структуру один за другим.
    т.е. если'x1' не существует, создайте этот узел, если он существует, перейдите к нему и проверьте, есть ли дочерний элемент'x2' и так далее...

  • 2

    Создайте объектный узел

    который содержит родительский элемент (узел) и список дочерних элементов (узел).

    Сначала разбейте строку, используя & quot;, & quot ;. Для каждой разбитой строки вы разбиваете строку с помощью & quot; / & quot ;. Найдите идентификатор первого узла (например, x1) в корневом списке. Если вы можете найти его, используйте этот узел, чтобы найти идентификатор следующего узла (например, x2).

    Если вы не можете найти узел, добавьте его к последнему узлу, который вы смогли найти в существующих списках.

    После того, как вы создали структуру списка, вы можете распечатать список на экране. Я бы сделал это рекурсивным.

    NOT TESTED, just an 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);
        }
    }
    

  • 4

    Я бы сделал дерево по одной строке за раз.

    Создайте пустое дерево (у которого есть корневой узел - я предполагаю, что мог бы быть путь как & quot; x7 / x8 / x9 & quot;).

    Возьмите первую строку, добавьте x1 к корневому узлу, затем от x2 до x1, затем от x3 до x2.

    Возьмите вторую строку, посмотрите, что x1 и x2 уже есть, добавьте x4 к x2.

    Делайте это для каждого пути, который у вас есть.

  • 0

    Создайте свое дерево для каждой строки в массиве.

    Просто разделите путь для «/»; , проверьте, существует ли узел в вашем дереве или нет, затем перейдите ... в противном случае создайте новый узел и добавьте этот узел в дочерний узел родительского узла.

    Итерация с использованием рекурсии.

    Ниже приведена модель для узла дерева.

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