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

问题描述 投票：0回答：5

我有一个这样的路径列表

/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

因此，从这个路径列表（Stings）中，我需要创建一个 Java 树结构，其中文件夹作为节点，文件作为叶子（不会有空文件夹作为叶子）。

我认为我需要的是添加方法，我向它们传递一个字符串（文件的路径）并将其添加到树中的正确位置，创建正确的节点（文件夹）（如果它们尚不存在）

当我位于节点和叶子列表上时，此树结构将需要我获取节点列表（但我认为这将是树的正常功能）

我将始终将字符串作为路径，而不是真正的文件或文件夹。 有可以使用的东西或者可以启动的源代码吗？

非常感谢。

java data-structures tree filesystems
5个回答
25
投票

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

正如我所说，我需要的是一个允许我对 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;
    }


}

Test.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();
    }

}

如果您对改进有什么好的建议，请告诉我:)

3
投票

我自己实施了应对挑战的解决方案。 我在 DirectoryNode 中代表文件系统层次结构的每个节点。辅助方法 createDirectoryTree(String... filePaths) 创建目录树。

这是使用示例：

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 -输出为：

  {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=[]}]}]}

Java源码：

// DirectoriesHelper.java
import java.util.Optional;

public final class DirectoriesHelper {

  private DirectoriesHelper() {}

  public static Optional<DirectoryNode> createDirectoryTree(String... filePaths) {

    DirectoryNode treeRootNode = null;
    for (final String childPath : filePaths) {
      final String path = childPath == null ? "" : childPath;
      final String[] pathElements = path.split("/");
      DirectoryNode movingNode = null;
      for (final String pathElement : pathElements) {
        movingNode = new DirectoryNode(movingNode, pathElement);
      }

      if (treeRootNode == null) {
        treeRootNode = movingNode.getRoot();
      } else {
        treeRootNode.merge(movingNode.getRoot());
      }
    }

    return Optional.ofNullable(treeRootNode);
  }
}


// DirectoryNode.java
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

public class DirectoryNode implements Comparable<DirectoryNode> {

  private final Set<DirectoryNode> children = new LinkedHashSet<>();

  private final String value;

  private final DirectoryNode parent;

  public DirectoryNode(final DirectoryNode parent, final String value) {
    this.parent = parent;
    if (this.parent != null) {
      this.parent.children.add(this);
    }

    this.value = value;
  }

  private static void appendDirectoryNode(
      final Set<DirectoryNode> directoryNodes, final DirectoryNode node) {
    if (node.isLeaf()) {
      return;
    }

    directoryNodes.add(node);
    node.getChildren().parallelStream()
        .forEach(childNode -> appendDirectoryNode(directoryNodes, childNode));
  }

  public Set<DirectoryNode> getChildren() {
    return children;
  }

  public String getValue() {
    return value;
  }

  public DirectoryNode getParent() {
    return parent;
  }

  public String getPath() {
    if (getParent() == null) {
      return value;
    }

    return parent.getPath() + "/" + value;
  }

  public int getLeafCount() {
    int leafCount = isLeaf() ? 1 : 0;
    for (final DirectoryNode child : children) {
      leafCount += child.getLeafCount();
    }

    return leafCount;
  }

  public boolean isLeaf() {
    return children.isEmpty();
  }

  /**
   * @return Subnodes of this node, which are directory (non-leaf / no-children) nodes
   */
  public Set<DirectoryNode> getDirectoryNodes() {
    final Set<DirectoryNode> directoryNodes = Collections.synchronizedSortedSet(new TreeSet<>());
    appendDirectoryNode(directoryNodes, this);

    return directoryNodes;
  }

  public DirectoryNode getRoot() {
    return parent == null ? this : parent.getRoot();
  }

  public boolean isRootNode() {
    return equals(getRoot());
  }

  public void merge(final DirectoryNode that) {
    if (!value.equals(that.value)) {
      return;
    } else if (children.isEmpty()) {
      children.addAll(that.children);
      return;
    }

    final DirectoryNode[] thisChildren = children.toArray(new DirectoryNode[children.size()]);
    for (final DirectoryNode thisChild : thisChildren) {
      for (final DirectoryNode thatChild : that.children) {
        if (thisChild.value.equals(thatChild.value)) {
          thisChild.merge(thatChild);
        } else {
          children.add(thatChild);
        }
      }
    }
  }

  @Override
  public boolean equals(final Object o) {
    if (this == o) {
      return true;
    }
    if (o == null || getClass() != o.getClass()) {
      return false;
    }
    final DirectoryNode that = (DirectoryNode) o;
    return Objects.equals(value, that.value) && Objects.equals(parent, that.parent);
  }

  @Override
  public int hashCode() {
    return Objects.hash(value, parent);
  }

  @Override
  public String toString() {
    return "{" + "value='" + value + '\'' + ", children=" + children + '}';
  }

  @Override
  public int compareTo(final DirectoryNode o) {
    return getPath().compareTo(o.getPath());
  }
}
2
投票

似乎您可以采用 Trie / Radix Trie 或 二叉搜索树 在任何一种情况下工作。您可以增强 Trie 以将“文件夹”存储为内部节点（而不是像常规 Trie 中的字符），或者您可以增强二叉搜索树以将“文件夹”存储为内部节点（只要它们实现类似的接口）和“文件”作为叶节点。

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

1
投票

我建议阅读数据结构，特别是树。在 Java 中，您可以通过创建一个引用其他节点的节点类来表示这些。例如：

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

显然，您可以按照自己喜欢的方式存储节点引用 - 数组或集合将与非二叉树一起使用。

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

-1
投票

看看新的 Java 7 - nio2 包。您需要的一切都在里面。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.