从字符串路径列表中构建一个树形结构

我有一个像列表中的[“x1/x2/x3”，“x1/x2/x4”，“x1/x5”]这样的字符串路径的集合。我需要从这个列表中构建一个树状结构，可以迭代获得漂亮的打印树。这样的从字符串路径列表中构建一个树形结构

x1 
| 
|-x2 
| | 
| |-x3 
| | 
| |-x4 
| 
|-x5

任何意见/建议吗？我相信这个问题首先可以通过处理字符串列表来进行攻击编辑：选择正确的答案是一个优雅的实现，其他建议也很好。

来源

2009-06-17 sushant

也许你会有兴趣看我的，将解决你的（和我）的问题当前工作落实:)看看：HTTP：/ /stackoverflow.com/a/10935115/737636 – StErMi 2012-06-07 15:39:20

按照幼稚实施的Visitable树的实现：

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

来源

2009-06-17 09:15:08 dfa

感谢代码dfa;它的作用就像一种魅力。访客模式实施是整洁的。 – sushant 2009-06-17 09:39:19

我会让树一次一个字符串。

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

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

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

为每条路径都做到这一点。

来源

2009-06-17 07:21:12

只需用分隔符分割每条路径，然后将它们逐个添加到树结构中。
即如果'x1'不存在创建这个节点，如果它确实存在去，并检查是否有孩子'x2'等等...

来源

2009-06-17 07:22:28

创建一个包含父（节点）和对象节点子节点列表（节点）。

首先使用“，”分割字符串。对于每个分割的字符串，使用“/”分割字符串。搜索根列表中的第一个节点标识符（例如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); 
    } 
}

来源

2009-06-17 07:52:51

从字符串路径列表中构建一个树形结构

回答

相关问题