Постройте древовидную структуру из списка путей к строкам
Вопрос
У меня есть набор строковых путей, таких как ["x1 / x2 / x3", "x1 / x2 / x4", "x1 / x5"] в списке.Мне нужно построить древовидную структуру из этого списка, которую можно повторять, чтобы получить красивое печатное дерево.вот так
x1
/ \
x5 x2
/ \
x3 x4
Есть какие-нибудь идеи / предложения?Я считаю , что проблему можно устранить в первую очередь , обработав список строк ПРАВИТЬ:Выбранным правильным ответом была элегантная реализация, другие предложения тоже были хороши.
Решение
Следуйте реализации наивной реализации дерева, доступного для посещения:
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
Другие советы
Просто разделите каждый путь по его разделителю, а затем добавьте их в древовидную структуру один за другим.
т.е. если 'x1'
не существует, создайте этот узел, если он существует, перейдите к нему и проверьте, есть ли дочерний элемент 'x2'
и т. д. ... р>
Я бы сделал дерево по одной строке за раз.
Создайте пустое дерево (в котором есть корневой узел - я предполагаю, что может быть путь, подобный " x7 / x8 / x9 ").
Возьмите первую строку, добавьте x1 к корневому узлу, затем от x2 до x1, затем от x3 до x2.
Возьмите вторую строку, посмотрите, что x1 и x2 уже есть, добавьте x4 к x2.
Делайте это для каждого вашего пути.
Создайте объектный узел, который содержит родительский элемент (узел) и список дочерних элементов (узел).
Сначала разбейте строку, используя ", " ;. Для каждой разбитой строки вы разбиваете строку с помощью " / " ;. Найдите идентификатор первого узла (например, x1) в корневом списке. Если вы можете найти его, используйте этот узел, чтобы найти идентификатор следующего узла (например, x2).
Если вы не можете найти узел, добавьте его к последнему узлу, который вы смогли найти в существующих списках.
После того как вы создали структуру списка, вы можете распечатать список на экране. Я бы сделал это рекурсивным.
НЕ ИСПЫТАНО, просто анимация
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);
}
}
Создайте свое дерево для каждой строки в массиве. Просто разделите путь на «/», проверьте, существует ли узел в вашем дереве или нет, если он существует, перейдите ... в противном случае создайте новый узел и добавьте этот узел в потомки родительского узла.
Итерация с использованием рекурсии.
Ниже приведена модель для узла дерева.
Class Node{
string name;
List<Node> childrens;
Node(string name){
this.name = name;
this.childrens = new List<Node>();
}
}