4

有人可以给我一些指示吗？我想要一个文件路径列表（只是字符串）并转换成一个分层树状结构。因此有两个任务，解析字符串以创建树，以及创建树或某种映射结构以实际将结果放入其中。（然后第三个任务是解析树以在 html 中显示为树）

我正在使用 Java 7，所以我假设我可以使用 Paths 来完成第一部分，但努力获得一个清晰的算法。

C:\Music\Blur\Leisure
C:\Music\KateBush\WholeStory\Disc1
C:\Music\KateBush\WholeStory\Disc2
C:\Music\KateBush\The Kick Inside   
C:\Music\KateBush\The Dreaming
C:\MusicUnprocessed\Blue\ParkLife

所以它给

C:\
   Music
      Blur 
          Leisure
      Kate Bush
          Whole Story
               Disc 1
               Disc 2
          The Kick Inside
          The Dreaming
    MusicProcessing
      Blur
         ParkLife
4

2 回答 2

6

这是一个非常简单的实现，它会让您知道从哪里开始。:-)

import java.io.PrintStream;
import java.util.Collections;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.regex.Pattern;

public class PathWalker {
    public static class Node {
        private final Map<String, Node> children = new TreeMap<>();

        public Node getChild(String name) {
            if (children.containsKey(name))
                return children.get(name);
            Node result = new Node();
            children.put(name, result);
            return result;
        }

        public Map<String, Node> getChildren() {
            return Collections.unmodifiableMap(children);
        }
    }

    private final Node root = new Node();

    private static final Pattern PATH_SEPARATOR = Pattern.compile("\\\\");
    public void addPath(String path) {
        String[] names = PATH_SEPARATOR.split(path);
        Node node = root;
        for (String name : names)
            node = node.getChild(name);
    }

    private static void printHtml(Node node, PrintStream out) {
        Map<String, Node> children = node.getChildren();
        if (children.isEmpty())
            return;
        out.println("<ul>");
        for (Map.Entry<String, Node> child : children.entrySet()) {
            out.print("<li>");
            out.print(child.getKey());
            printHtml(child.getValue(), out);
            out.println("</li>");
        }
        out.println("</ul>");
    }

    public void printHtml(PrintStream out) {
        printHtml(root, out);
    }

    public static void main(String[] args) {
        PathWalker self = new PathWalker();
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine())
            self.addPath(scanner.nextLine());
        self.printHtml(System.out);
    }
}

最初，我考虑为目录和常规文件创建单独的类，但我觉得在这种情况下，由于您要做的只是打印名称，因此使用统一的节点类可以使代码更易于使用，尤其是因为您可以避免实现访问者模式。

输出没有以任何特别好的方式格式化。因此，如果您愿意，您可以调整代码；或者，如果你想要更好看的东西，你可以通过 HTML Tidy 运行输出。

我选择使用TreeMap，所以目录条目是按字典顺序排列的。如果您想改用插入顺序，只需更改为使用LinkedHashMap.

于 2013-09-03T13:01:53.780 回答
0

您能否更具体地说明您正在努力解决的问题？在我看来，您已经设法将任务分成很好的块（解析、创建树并显示它）。

如果你想了解更多关于树的知识，那么我推荐斯坦福优秀的 CS 库 ( http://cslibrary.stanford.edu/ )，这是我学习链表和二叉树的方法。我认为提出我自己的二叉树 lisp 实现以及插入新元素和解析它的函数，确实帮助我解决了这些问题。

请注意，在您的示例中，二叉树足以表示数据，因为每个父母最多有两个孩子，但我本以为您可能会遇到情况并非如此。

但是，一旦您了解了二叉树，就应该不难理解具有任意数量子节点的树。

至于解析，我不确定你真的需要路径。由于您已经获得了一个文件，其中每一行都是具有完全限定路径名的文件，因此自己编写一个简单的解析函数应该不会太难。

我的意思是，基本上你想在斜线“\”上分割，所以每次你看到一个斜线，你都会创建一个新节点，前一个节点作为它的父节点。如果节点已经存在，您只需附加到它。对于每一行，您都从树的根部开始。

将树输出为 html 本质上是树遍历。

于 2013-09-03T11:26:48.703 回答