1

我已经实现了一个能够存储数据的通用 trie，但我的问题集中在从 trie 中提取它。这是我的 Trie 和 TrieNode 类，以及我的 getWords() 方法：

public class Trie<T extends Comparable<T>> 
{
    private TrieNode root;
    List<String> wordList = new ArrayList<String>();
    StringBuilder word = new StringBuilder();

    public Trie()
    {
        root = new TrieNode((T) " ");
    }

    private class TrieNode implements Comparable 
    {
        private T data;
        private int count;
        private boolean end;
        private List<TrieNode> children; //subnodes

        private TrieNode(T data)
        {
            this.data = data;
            count = 0;
            end = false;
            children = new ArrayList<TrieNode>();
        }
        }

    public List<String> getWords(Trie<T> t) throws Exception
    {
        List<String> words = getWords(t.root);
        return words;
    }

    private List<String> getWords(TrieNode node) throws Exception
    {
        if(node.data.equals(" "))
        {
            if(node.children.size() > 0)
            {
                for(TrieNode x : node.children)
                    return getWords(x);

                return wordList;
            }
            else
                throw new Exception("Root has no children");
        }
        else if(node.children.size() > 0 && node.end == false)
        {
            word.append(node.data);

            for(TrieNode x : node.children)
                return getWords(x);
        }
        else if(node.children.size() == 0 && node.end == true)
        {
            word.append(node.data);
            wordList.add(word.toString());
        }

        return null;
    }
}

我正在我的主类中使用以下代码进行测试：

    Trie<String> a = new Trie<String>();
    String[] word = "Steve".split("");
    a.insert(word);

    System.out.println(a.search(word)); //it can find the word in the trie
    System.out.println(a.getWords(a)); //but returns null when traversing through it

输出是：

    true
    null

我的代码有什么问题，它无法正确遍历 trie 以提取存储在其中的单词？

4

1 回答 1

1

您的getWords(TrieNode)实施将提前返回：

// ...
else if(node.children.size() > 0 && node.end == false)
{
    word.append(node.data);

    for(TrieNode x : node.children)
        return getWords(x); // here
}
// ...

该行在第一次迭代时通过返回第一个是什么来return打破for循环。一个可能的解决方法（我不确定我是否完全理解返回的逻辑含义）：getWords(x)xgetWords

// ...
else if(node.children.size() > 0 && node.end == false)
{
    word.append(node.data);

    List<String> toReturn = new ArrayList<String>();
    for(TrieNode x : node.children) {
        toReturn.addAll(getWords(x));
    }

    return toReturn;
}
// ...
于 2012-10-31T03:48:06.913 回答