从字符串路径列表构造树结构

  • Z时代
  • 2024-01-10
  • 分类：问答

我在列表中有一个字符串路径集合，例如[“ x1 / x2 / x3”，“ x1 / x2 / x4”，“ x1 /

x5”]。我需要从该列表构造一个树状结构，可以对其进行迭代以获得漂亮的打印树。像这样

     x1
    /  \
   x5   x2
       /  \
      x3  x4

有什么想法/建议吗？我认为可以通过处理字符串列表来首先解决该问题。编辑：选择的正确答案是一种优雅的实现，其他建议也很好。

回答：

遵循可访问树的幼稚实现的实现：

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));

输出：

森林
  x1
    2倍
      3倍
      4倍
    5倍

以上是 从字符串路径列表构造树结构 的全部内容， 来源链接： utcz.com/qa/399044.html

回到顶部