0

我正在实现一个trie，它将子字符串及其出现次数存储在一个字符串中。我的 trie 中的每个节点都有一个名为 children 的 Map，它将存储主节点的任何子节点。

我的问题是，最终，这些子节点将拥有自己的子节点，我不知道如何能够从“地图中的地图中的地图......”可以这么说。

这是我到目前为止所拥有的：

private class TrieNode
{
    private T data; //will hold the substring
    int count; //how many occurrences of it were in the string
    private Map<TrieNode, Integer> children; //will hold subnodes
    private boolean isWord; //marks the end of a word if a substring is the last substring of a String

    private TrieNode(T data)
    {
        this.data = data;
        count = 1;
        children = new HashMap<TrieNode, Integer>();
        isWord = false;
    }
}

我如何从子节点中检索数据，这些子节点下可能有其他子节点？

PS如果我不能清楚地解释它，我很抱歉 - 我遇到了递归问题。谢谢。

4

2 回答 2

1

我不明白为什么要将字符串存储在名为 T 的类型中。这听起来像是泛型类型，但您还没有在类中声明它。

无论如何，我认为您需要一个Map<T, TrieNode>将每个子字符串保存为键的子字符串。这样，您会再次出现另一个TrieNode，它又具有另一张相同类型的地图。

于 2012-10-28T21:40:30.077 回答
1

你需要一些东西。首先，您想要Map<T, TrieNode>因为您正在将一条数据映射到一个子 Trie。

其次，您需要知道如何将数据拆分为头尾，以及稍后如何重新组合它们。在字符串的标准情况下，您使用子字符串和连接。例如：

private TrieNode(String currChar, String rest) {
   this.data = currChar;
   this.children = new HashMap<String, TrieNode>();
   if(rest.isEmpty()) {
      this.isWord = true;
   } else {
      String head = rest.substring(0, 1);
      String tail = rest.substring(1, rest.length());
      this.children.add(head, new TrieNode(head, tail);
   }
}

您T需要能够做类似的事情，或者首先使用 Trie 是没有意义的。

此外，您很少需要从 Trie 重新编译字符串。通常，您只是检查 Trie 中是否存在字符串，或者某个字符串是多少个字符串的子字符串。

于 2012-10-28T22:23:24.790 回答