Java的树从路径列表代表的文件系统（文件/目录）

Question

我有这样的

/mnt/sdcard/folder1/a/b/file1 
/mnt/sdcard/folder1/a/b/file2 
/mnt/sdcard/folder1/a/b/file3 
/mnt/sdcard/folder1/a/b/file4 
/mnt/sdcard/folder1/a/b/file5 
/mnt/sdcard/folder1/e/c/file6 
/mnt/sdcard/folder2/d/file7 
/mnt/sdcard/folder2/d/file8 
/mnt/sdcard/file9 

从路径（蜇伤）这个名单

所以路径列表，我需要克里特岛一个Java树结构有文件夹作为叶节点和文件（不会是空的文件夹叶）。

我需要的是我添加的方法，我传递给他们一个字符串（文件的路径），并将它添加到树的正确位置创建正确的节点（文件夹），如果他们不在那里

这种树形结构需要我获得节点列表，当我在节点和叶子的名单（但我认为这将是树木正常功能）

我会永远字符串作为路径，而不是真实的文件或文件夹。 是否有东西准备好使用或源代码开始？

非常感谢。

Answer 1

谢谢你所有的答案。我做了我的工作实施。 我认为我需要改进它，以便在向树结构添加元素时使用更多缓存更好地工作。

正如我所说的，我所需要的是一种结构，它允许我对FS进行“虚拟”表示。

MXMTree.java

public class MXMTree { 

    MXMNode root; 
    MXMNode commonRoot; 

    public MXMTree(MXMNode root) { 
     this.root = root; 
     commonRoot = null; 
    } 

    public void addElement(String elementValue) { 
     String[] list = elementValue.split("/"); 

     // latest element of the list is the filename.extrension 
     root.addElement(root.incrementalPath, list); 

    } 

    public void printTree() { 
     //I move the tree common root to the current common root because I don't mind about initial folder 
     //that has only 1 child (and no leaf) 
     getCommonRoot(); 
     commonRoot.printNode(0); 
    } 

    public MXMNode getCommonRoot() { 
     if (commonRoot != null) 
      return commonRoot; 
     else { 
      MXMNode current = root; 
      while (current.leafs.size() <= 0) { 
       current = current.childs.get(0); 
      } 
      commonRoot = current; 
      return commonRoot; 
     } 

    } 


} 

MXMNode.java

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 


public class MXMNode { 

    List<MXMNode> childs; 
    List<MXMNode> leafs; 
    String data; 
    String incrementalPath; 

    public MXMNode(String nodeValue, String incrementalPath) { 
     childs = new ArrayList<MXMNode>(); 
     leafs = new ArrayList<MXMNode>(); 
     data = nodeValue; 
     this. incrementalPath = incrementalPath; 
    } 

    public boolean isLeaf() { 
     return childs.isEmpty() && leafs.isEmpty(); 
    } 

    public void addElement(String currentPath, String[] list) { 

     //Avoid first element that can be an empty string if you split a string that has a starting slash as /sd/card/ 
     while(list[0] == null || list[0].equals("")) 
      list = Arrays.copyOfRange(list, 1, list.length); 

     MXMNode currentChild = new MXMNode(list[0], currentPath+"/"+list[0]); 
     if (list.length == 1) { 
      leafs.add(currentChild); 
      return; 
     } else { 
      int index = childs.indexOf(currentChild); 
      if (index == -1) { 
       childs.add(currentChild); 
       currentChild.addElement(currentChild.incrementalPath, Arrays.copyOfRange(list, 1, list.length)); 
      } else { 
       MXMNode nextChild = childs.get(index); 
       nextChild.addElement(currentChild.incrementalPath, Arrays.copyOfRange(list, 1, list.length)); 
      } 
     } 
    } 

    @Override 
    public boolean equals(Object obj) { 
     MXMNode cmpObj = (MXMNode)obj; 
     return incrementalPath.equals(cmpObj.incrementalPath) && data.equals(cmpObj.data); 
    } 

    public void printNode(int increment) { 
     for (int i = 0; i < increment; i++) { 
      System.out.print(" "); 
     } 
     System.out.println(incrementalPath + (isLeaf() ? " -> " + data : "") ); 
     for(MXMNode n: childs) 
      n.printNode(increment+2); 
     for(MXMNode n: leafs) 
      n.printNode(increment+2); 
    } 

    @Override 
    public String toString() { 
     return data; 
    } 


} 

测试。Java进行测试代码

public class Test { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 

     String slist[] = new String[] { 
       "/mnt/sdcard/folder1/a/b/file1.file", 
       "/mnt/sdcard/folder1/a/b/file2.file", 
       "/mnt/sdcard/folder1/a/b/file3.file", 
       "/mnt/sdcard/folder1/a/b/file4.file", 
       "/mnt/sdcard/folder1/a/b/file5.file", 
       "/mnt/sdcard/folder1/e/c/file6.file", 
       "/mnt/sdcard/folder2/d/file7.file", 
       "/mnt/sdcard/folder2/d/file8.file", 
       "/mnt/sdcard/file9.file" 
     }; 

     MXMTree tree = new MXMTree(new MXMNode("root", "root")); 
     for (String data : slist) { 
      tree.addElement(data); 
     } 

     tree.printTree(); 
    } 

} 

请告诉我，如果你有关于改进措施一些好的建议:)

Answer 2

看看新的Java 7 - nio2 package。所有你需要的是在里面。

Answer 3

我会推荐阅读data structures，特别是trees。在Java中，您可以通过创建具有对其他节点的引用的节点类来表示这些节点。例如：

public class Node { 
    private Node[] children; 
    /* snip other fields */ 
    public boolean isFile() { 
     return children.count == 0; 
    } 
} 

显然，您可以随心所欲地存储您的节点引用 - 数组或集合将与非二进制树一起工作。

鉴于您的文件列表，您可以阅读这些文件并填充树结构。

Answer 4

好像你可以修改Trie/Radix Trie或Binary Search Tree在任何情况下工作。你可以增加一个Trie来存储“文件夹”作为内部节点（而不是像普通Trie中的字符），或者你可以增加一个二叉搜索树来将“文件夹”存储为内部节点（只要它们实现了可比较的接口）和“文件”作为叶节点。

我在上面的文本中链接了这些结构的实现。

Answer 5

我实现了一个解决方案来挑战自己，这是available as a GitHubGist。

我代表DirectoryNode中文件系统层次结构的每个节点。辅助方法createDirectoryTree（String [] filesystemList）创建一个direcotry-tree。

以下是使用示例，其中包含GitHubGist。

final String[] list = new String[]{ 
    "/mnt/sdcard/folder1/a/b/file1.file", 
    "/mnt/sdcard/folder1/a/b/file2.file", 
    "/mnt/sdcard/folder1/a/b/file3.file", 
    "/mnt/sdcard/folder1/a/b/file4.file", 
    "/mnt/sdcard/folder1/a/b/file5.file", 
    "/mnt/sdcard/folder1/e/c/file6.file", 
    "/mnt/sdcard/folder2/d/file7.file", 
    "/mnt/sdcard/folder2/d/file8.file", 
    "/mnt/sdcard/file9.file" 
}; 

final DirectoryNode directoryRootNode = createDirectoryTree(list); 

System.out.println(directoryRootNode); 

的的System.out.println -output是：

{value='mnt', children=[{value='sdcard', children=[{value='folder1', 
    children=[{value='a', children=[{value='b', children=[{value='file1.file', 
    children=[]}, {value='file2.file', children=[]}, {value='file3.file', 
    children=[]}, {value='file4.file', children=[]}, {value='file5.file', 
    children=[]}]}]}, {value='e', children=[{value='c', 
    children=[{value='file6.file', children=[]}]}]}]}, 
    {value='folder2', children=[{value='d', children=[{value='file7.file', 
    children=[]}, {value='file8.file', children=[]}]}]}, 
    {value='file9.file', children=[]}]}]}