2

我在这里找到了同样的问题Traversing a trie to get all words，但它是针对 Perl 的，我只熟悉 Java。我的 trie 结构是普通整数数组，其中前 26 个整数是根，每个整数都有 firstChild 索引，它是子数组元素的索引（最多 25 个最高位），列表结束位标志，字结束位标志，从 1 到 26（最低 5 位）的字母索引。CAGE如果我将 2（字母 c 的根索引）作为参数传递，我可以递归打印一个单词 

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

或一个共同的开头和不同的结尾，例如 YARDELLOW单词 yard 和 yellow（传递 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);
        }
    }
}

但不能用所有的词来做到这一点（（我已经尝试过这个和那个让它返回一个字符串，但没有取得任何成功（只是得到一个字符串的第一个字母。请帮助使用该方法为我的 trie 中的所有单词递归打印（更好的是 - 返回字符串数组）。这不是家庭作业，我是自学的））

4

1 回答 1

1

您能否分享更多代码和输入数据，以更好地了解您要做什么？

这个关于Java 中的 Trie 数据结构的Stack Overflow 讨论可能会有所帮助：Trie 数据结构 - Java。我发现以下链接（来自答案之一）非常有用：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]。

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

干杯，弗里克

于 2013-01-18T10:20:26.833 回答