从字符串路径列表构建树结构 [英] Construct a tree structure from list of string paths

问题描述

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

 x1/x5 x2/x3 x4

有什么想法/建议吗?我相信可以首先通过处理字符串列表来解决问题选择的正确答案是一个优雅的实现，其他建议也很好.

解决方案

遵循可访问树的naive实现:

class Tree实现 Visitable{//注意:LinkedHashSet 保留插入顺序私有最终集<树>children = new LinkedHashSet();私人最终 T 数据；树(T数据){this.data = 数据；}无效接受(访问者访问者){访问者.visitData(这个，数据)；对于(树孩子:孩子){访客<T>childVisitor =visitor.visitTree(child);child.accept(childVisitor);}}树子(T数据){对于(树孩子:孩子){如果(child.data.equals(数据)){返回孩子；}}返回孩子(新树(数据))；}树子(树子){孩子.添加(孩子)；返回孩子；}}

访问者模式的接口:

interface Visitor;{访客<T>访问树(树树)；void visitData(Tree<T> parent, T data);}界面可访问<T>{void accept(Visitorvisitor);}

访问者模式的示例实现:

class PrintIndentedVisitor 实现了 Visitor;{私有最终整数缩进；PrintIndentedVisitor(int indent) {this.indent = 缩进；}访问者<字符串>访问树(树<字符串>树){返回新的 IndentVisitor(indent + 2);}无效访问数据(树<字符串>父级，字符串数据){for (int i = 0; i < indent; i++) {//TODO: 幼稚的实现System.out.print(" ");}System.out.println(数据);}}

最后(！！！)一个简单的测试用例:

 树<字符串>Forest = new Tree("forest");树<字符串>当前 = 森林；对于(字符串树:Arrays.asList(x1/x2/x3"，x1/x2/x4"，x1/x5")){树<字符串>根 = 当前；for(字符串数据:tree.split(/")){当前 = current.child(data);}当前 = 根；}森林.接受(新的 PrintIndentedVisitor(0))；

输出:

<前>森林x1×2x3x4x5

I have a collection of string paths like ["x1/x2/x3","x1/x2/x4","x1/x5"] in a list. I need to construct a tree-like structure from this list which can be iterated to get a pretty printed tree. like this

     x1
    /  
   x5   x2
       /  
      x3  x4

Any ideas/suggestions? I believe that the problem can be attacked first by processing the list of strings EDIT: The correct answer chosen was an elegant implementation, other suggestions were good too.

解决方案

Follow an implementation of naive implementation of a visitable tree:

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

sample implementation for Visitor Pattern:

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

and finally (!!!) a simple test case:

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

output:

forest
  x1
    x2
      x3
      x4
    x5

这篇关于从字符串路径列表构建树结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！