1

データを保存できる一般的なトライを実装しましたが、問題はトライからの抽出に集中しています。以下は、私の getWords() メソッドとともに、私の Trie および TrieNode クラスです。

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

コード内に保存されている単語を抽出する試行を正しくトラバースできないというコードの何が問題になっていますか?

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中断します。考えられる修正（論理的に何が返されるかを完全に理解しているかどうかはわかりません）：forgetWords(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 に答える