从字符串路径列表构造树结构

Question

我在列表中有一组字符串路径,如["x1/x2/x3","x1/x2/x4","x1/x5"].我需要从这个列表中构造一个树状结构,可以迭代得到一个漂亮的打印树.像这样

     x1
    /  \
   x5   x2
       /  \
      x3  x4

有什么想法/建议吗？我相信通过处理字符串列表可以首先攻击问题EDIT:选择的正确答案是优雅的实现,其他建议也很好.

Answer 1

遵循可访问树的天真实现的实现:

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

Answer 2

只需通过分隔符拆分每个路径,然后逐个将它们添加到树结构中.
即如果'x1'不存在则创建此节点,如果它存在则转到它并检查是否有子节点'x2'等等...

Answer 3

我会一次把树做成一根绳子。

制作一个空树（它有一个根节点 - 我假设可能有一个像“x7/x8/x9”这样的路径）。

取第一个字符串，将x1添加到根节点，然后将x2添加到x1，然后将x3添加到x2。

取第二个字符串，看到 x1 和 x2 已经存在，将 x4 添加到 x2。

对您拥有的每条路径执行此操作。