0

我写了以下前缀特里：

class TrieNode {
    char letter;
    HashMap<Character,TrieNode> children;
    boolean fullWord;

    TrieNode(char letter) {
        this.letter = letter;
        children = new  HashMap<Character, TrieNode>();
        this.fullWord = false;
    }
}

class Tree{
    static TrieNode createTree() {
         return (new TrieNode('\0'));
    }

    static void insertWord(TrieNode root, String word) {
        int l = word.length();
        char[] letters = word.toCharArray();
        TrieNode curNode = root;
        for (int i = 0; i < l; i++) {
            if (!curNode.children.containsKey(letters[i]))
                curNode.children.put(letters[i], new TrieNode(letters[i]));
            curNode = curNode.children.get(letters[i]);
        }
        curNode.fullWord = true;
    }
}

我想添加 DFS 方法以查找具有多个子节点的第一个节点（因此它会显示最长的公共前缀）。

我写了这段代码：

static void DFS(TrieNode node) {
    for (TrieNode tn: node.children.values()){
       DFS(tn);
        if (node.children.size()>2)
        System.out.println("found the first vertex");
    }
}

但它不起作用。我究竟做错了什么？

4

2 回答 2

1

您的前缀树代码似乎不错。至少这对我来说是有意义的，但我还没有检查所有极端情况。问题是你的 DFS 方法。假设我们有以下由您的前缀树组成的字符串：

- "abcd"
- "abcg"
- "abckk"
- "abf"

所以前缀树应该是这样的：

              root
               |
               a
               |
               b
              / \
             c   f
            /|\
           d g k
                \
                 k

我认为您期望的是我们可以在节点b处输出“找到第一个顶点” （因为显然“ab”是上述四个字符串中最长的公共前缀），但是，您的 DFS 不能这样工作。它会一路走来

root->a->b->c->d then back to c, finding that c.children.size() >1 , then output.

请注意，“ 2 或更多”是 >=2 或 >1，在您的程序中是 >2。我认为这应该是一个错字。 要更正您的 DFS，只需对其进行修改以首先检查节点的子节点大小即可：

static boolean DFS(TrieNode node) {
    if (node.children.size()>1){
        System.out.println("found the first vertex on node:"+node.letter);
        return true;
    }
    for (TrieNode tn: node.children.values()){
        if(DFS(tn))
            return true;
    }
    return false;
}

注意为了让程序在找到我们的节点时停止，我修改了你的 DFS 的返回类型。此外，关于查找最长公共前缀，DFS 可能不是这里的最佳选择，以下代码在运行时复杂度方面优于 DFS：

static void lcp(TrieNode node){
    TrieNode first = node;
    while(first.children.size()==1)
        first = first.children.values().iterator().next();
    System.out.println("found the first vertex on node:"+first.letter);
}
于 2013-05-05T08:01:08.837 回答
1

好吧，首先我们需要澄清一下，这里的最长公共前缀是指 trie 树中任意两个或多个字符串的最长公共前缀。

因此，您的 DFS 方法将无法正常工作，因为它只是遍历整个树并在访问其 children.size() > 2 的任何节点时输出“找到第一个顶点”（这里应该 >=2）

我们在这里想要的是只找到最长的公共前缀。所以我们需要一些关于哪个是最长的额外信息。在我上面的例子中很容易看出：

          root      --depth: 0
           |
           a        --depth: 1
           |
           b        --depth: 2
          / \
         c   f      --depth: 3
        /|\
       d g k        --depth: 4
            \
             k      --depth: 5

最长的公共前缀节点有 children.size()>1并且有最大深度。在这种情况下，它是节点c

所以这是一种可能的正确 DFS：

static int max=-1;
static TrieNode maxNode=null;

static void dfs(TrieNode node, int depth){
    if(node.children.size()>1 && depth>max){
        max=depth;
        maxNode=node;
    }
    for (TrieNode tn: node.children.values())
        dfs(tn,depth+1);
}

public static void test(){
    TrieNode root = Tree.createTree();
    Tree.insertWord(root, "abcd");
    Tree.insertWord(root, "abcg");
    Tree.insertWord(root, "abckk");
    Tree.insertWord(root, "abf");
    dfs(root,0);
    System.out.println("Max node:"+maxNode.letter);
}

dfs 运行后，maxNode将保存最长公共前缀停止的节点。在这种情况下，它是节点 c。

于 2013-05-05T18:52:30.587 回答