recursive word trie traversal

Question

I've found the same question here Traversing a trie to get all words , but it's for Perl, and I'm familiar only with Java. my trie structure is the plain integer array, where the first 26 ints are the roots, each integer has firstChild index which is child array element's index (up to 25 highest bits), End-of-List bit flag, End-of-Word bit flag, letter index from 1 to 26(lowest 5 bits). I can recursively print one word CAGE if I pass the 2(root index for letter c) as a parameter

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

or a common beginning and distinct endings like YARDELLOW for words yard and yellow(passing 24 as parameter)

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);
        }
    }
}

but can't do that with all words(( and I've tried this and that to make it return a string, and haven't got any success(just was getting a very first letter of a string. Please help with the method to print recursively(and what is better - return String array) for all words from my trie. It's not a homework, I'm self-educating))

Answer 1

Could you maybe share some more of your code and your input data, to get a better understanding of what you are trying to do?

This Stack Overflow discussion on Trie data structures in Java might be helpful: Trie data structures - Java. I found the following link (from one of the answers) quite useful: https://forums.oracle.com/forums/thread.jspa?messageID=8787521.

EDIT: with help from https://forums.oracle.com/forums/thread.jspa?messageID=8787521 and Java tree data-structure?, I created the following code:

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;
    }
}

When I call createTreeAndGetAllWords, it returns the words I expected as three lists of characters: [c, a, r], [c, a, t] and [d, o, g].

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

Cheers, Freek