Java 从字符串路径列表构建树结构
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1005551/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Construct a tree structure from list of string paths
提问by sushant
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/x2/x3","x1/x2/x4","x1/x5"] 。我需要从这个列表中构建一个树状结构，它可以被迭代以获得一个漂亮的打印树。像这样
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.
任何想法/建议？我相信可以首先通过处理字符串列表来解决问题 编辑：选择的正确答案是一个优雅的实现，其他建议也很好。
采纳答案by dfa
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
回答by David Johnstone
I'd make the tree one string at a time.
我会一次把树做成一根绳子。
Make an empty tree (which has a root node - I assume there could be a path like "x7/x8/x9").
制作一个空树（它有一个根节点 - 我假设可能有一个像“x7/x8/x9”这样的路径）。
Take the first string, add x1 to the root node, then x2 to x1, then x3 to x2.
取第一个字符串，将x1添加到根节点，然后将x2添加到x1，然后将x3添加到x2。
Take the second string, see that x1 and x2 are already there, add x4 to x2.
取第二个字符串，看到 x1 和 x2 已经存在，将 x4 添加到 x2。
Do this for every path you have.
对您拥有的每条路径执行此操作。
回答by Roland Ewald
Just split each path by its delimiter and then add them to a tree structure one by one.
i.e. if 'x1'does not exist create this node, if it does exist go to it and check if there is a child 'x2'and so on...
只需按其分隔符分割每条路径，然后将它们一一添加到树结构中。
即如果'x1'不存在创建这个节点，如果它确实存在去它并检查是否有一个孩子'x2'等等......
回答by Markus Lausberg
Create an Object Node which contains a parent (Node) and a List of children (Node).
创建一个对象节点，其中包含一个父节点（节点）和一个子节点列表（节点）。
First split the string using ",". For every splitted string you split the string using "/". Search for the first node identifier (e.g x1) in the root list. If you can find it, use the node to find the next node identifier (e.g. x2).
首先使用“,”分割字符串。对于每个拆分的字符串，您使用“/”拆分字符串。在根列表中搜索第一个节点标识符（例如 x1）。如果可以找到，则使用该节点查找下一个节点标识符（例如 x2）。
If you can not find a node, add the node to the last node you was able to find in the existing lists.
如果找不到节点，请将该节点添加到您能够在现有列表中找到的最后一个节点。
After you have created the list structure, you can print the list to the screen. I would make it recursive.
创建列表结构后，您可以将列表打印到屏幕上。我会让它递归。
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);
}
}
回答by Mr_Hmp
Make your tree for every string in array. Just split path for '/' , check whether the node exists in your tree or not, if it exists then move on... otherwise create a new node and add this node in childrens of parent node.
为数组中的每个字符串制作树。只需拆分 '/' 的路径，检查该节点是否存在于您的树中，如果存在则继续...否则创建一个新节点并将此节点添加到父节点的子节点中。
Iterate using recursion.
使用递归进行迭代。
Following is model for tree's node.
以下是树节点的模型。
Class Node{
string name;
List<Node> childrens;
Node(string name){
this.name = name;
this.childrens = new List<Node>();
}
}
回答by Peter Kapralcik
This is way how I am doing tree from path (folders) structure. Maybe should help someone with basic logic.
这就是我从路径（文件夹）结构做树的方式。也许应该帮助有基本逻辑的人。
Node:
节点：
public class Node {
private String path;
private List<Node> children;
public Node(String path) {
this.path = path;
children = new ArrayList<>();
}
public String getName() {
return getName(path);
}
private String getName(String path) {
String[] split = path.split("\\");
return split[split.length - 1];
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
public String getPath() {
return path;
}
}
FilesTree:
文件树：
public class FilesTree {
private static final Logger log = Logger.getLogger(FilesTree.class.getName());
private FilesTree() {}
private static void createTree(Node root, List<String> paths) {
for (String path : paths) {
addNode(root, Arrays.asList(path.split("\\")), "");
}
}
private static void addNode(Node node, List<String> path, String nodePath) {
if (!path.isEmpty()) {
nodePath = nodePath.equals("") ? path.get(0) : String.format("%s\%s", nodePath, path.get(0));
}
if (node.getChildren().isEmpty() && path.size() == 1) {
node.addChild(new Node(nodePath));
} else if (!node.getChildren().isEmpty()) {
for (Node actual : node.getChildren()) {
if (actual.getName().equals(path.get(0))) {
addNode(actual, path.subList(1, path.size()), nodePath);
return;
}
}
node.addChild(new Node(nodePath));
} else {
log.info("Without children but with size: " + path.size());
}
}
}
