2

ここで同じ質問を見つけましたTraversing a try to get all words、しかしそれはPerl用であり、私はJavaしか知りません。私のトライ構造は単純な整数配列で、最初の 26 個の int がルートであり、各整数には、子配列要素のインデックス (最大 25 の最上位ビット) である firstChild インデックス、End-of-List ビット フラグ、End-of-Word があります。ビット フラグ、1 から 26 までの文字インデックス (下位 5 ビット)。CAGEパラメーターとして 2 (文字 c のルート インデックス) を渡すと、1 つの単語を再帰的に出力でき ます。

private void oneWord(int node) {
        System.out.print(getChar(Trie[node]));
        if (getEOL(Trie[node]) != 1) {
            oneWord(getFirstChild(Trie[node]));
        }
    }

または単語 yard と yellow のような共通の始まりと明確な終わり YARDELLOW(パラメーターとして 24 を渡す)

private void DFTSearch(int node) {
    System.out.print(getChar(Trie[node]));
    if (getFirstChild(Trie[node]) != 0) {
        for (int i = 0; i < getSiblingsNum((getFirstChild(Trie[node])); i++) {
            DFTSearch(getFirstChild(Trie[node]) + i);
        }
    }
}

しかし、すべての単語でそれを行うことはできません((そして、文字列を返すようにこれとあれを試しましたが、成功しませんでした(文字列の最初の文字を取得しているだけです。メソッドを手伝ってください)私のトライからのすべての単語に対して再帰的に印刷する（そして何が良いか - 文字列配列を返す）それは宿題ではなく、私は独学です））

4

1 に答える 1

1

あなたがやろうとしていることをよりよく理解するために、あなたのコードと入力データをもう少し共有していただけませんか?

Java の Trie データ構造に関するこのスタック オーバーフロー ディスカッションが役立つ場合があります: Trie データ構造 - Java。次のリンク（回答の1つから）が非常に役立つことがわかりました：https://forums.oracle.com/forums/thread.jspa?messageID=8787521。

編集: https://forums.oracle.com/forums/thread.jspa?messageID=8787521およびJava ツリーのデータ構造の助けを借りて? 、次のコードを作成しました。

public Stack<List<Character>> createTreeAndGetAllWords() {
    // Create the tree.
    final Tree<Character> rootTree = new Tree<Character>('*');
    final Tree<Character> cTree = rootTree.addChild(new Tree<Character>('c'));
    final Tree<Character> aTree = cTree.addChild(new Tree<Character>('a'));
    aTree.addChild(new Tree<Character>('r'));
    aTree.addChild(new Tree<Character>('t'));
    final Tree<Character> dTree = rootTree.addChild(new Tree<Character>('d'));
    final Tree<Character> oTree = dTree.addChild(new Tree<Character>('o'));
    oTree.addChild(new Tree<Character>('g'));
    // Traverse the tree.
    return getAllWords(rootTree);
}

private Stack<List<Character>> getAllWords(final Tree<Character> tree) {
    final Stack<List<Character>> listStack = new Stack<List<Character>>();
    for (final Tree<Character> child : tree.getChildren()) {
        listStack.push(new ArrayList<Character>());
        traverseSubtree(child, listStack);
    }
    return listStack;
}

private void traverseSubtree(final Tree<Character> tree, final Stack<List<Character>> listStack) {
    final List<Character> currentWord = listStack.pop();
    if (tree.hasChildren()) {
        for (final Tree<Character> child : tree.getChildren()) {
            final List<Character> extendedWord = new ArrayList<Character>(currentWord);
            extendedWord.add(tree.getValue());
            listStack.push(extendedWord);
            traverseSubtree(child, listStack);
        }
    } else {
        currentWord.add(tree.getValue());
        listStack.push(currentWord);
    }
}



public class Tree<T> {
    private T value;
    private List<Tree<T>> children;

    public Tree(T value) {
        this.value = value;
        this.children = new ArrayList<Tree<T>>();
    }

    public T getValue() {
        return value;
    }

    public boolean hasChildren() {
        return children.size() > 0;
    }

    public Tree<T> addChild(Tree<T> child) {
        children.add(child);
        return child;
    }

    public List<Tree<T>> getChildren() {
        return children;
    }
}

createTreeAndGetAllWords を呼び出すと、[c, a, r]、[c, a, t]、および [d, o, g] の 3 つの文字リストとして予期した単語が返されます。

for (final List<Character> word : createTreeAndGetAllWords()) {
    System.out.println("word = " + word);
}

乾杯、フリーク

于 2013-01-18T10:20:26.833 に答える