Получение списка слов от Trie

Самое простое решение - использовать поиск в глубину.

Вы проходите по тройке, подбирая букву за буквой из входных данных. Затем, когда у вас больше не осталось букв, все, что находится под этим узлом, - это строки, которые вам нужны. Рекурсивно исследуйте всю подтрию, строя строки по мере продвижения к ее узлам.

После цикла for добавьте вызов printAllStringsInTrie(current, s);

void printAllStringsInTrie(Node t, String prefix) {
  if (t.current_marker) System.out.println(prefix);
  for (int i = 0; i < t.child.length; i++) {
    if (t.child[i] != null) {
      printAllStringsInTrie(t.child[i], prefix + ('a' + i));  // does + work on (String, char)?
    }
  }
}

Я однажды построил дерево для одной из ITA головоломок

public class WordTree {


class Node {

    private final char ch;

    /**
     * Flag indicates that this node is the end of the string.
     */
    private boolean end;

    private LinkedList<Node> children;

    public Node(char ch) {
        this.ch = ch;
    }

    public void addChild(Node node) {
        if (children == null) {
            children = new LinkedList<Node>();
        }
        children.add(node);
    }

    public Node getNode(char ch) {
        if (children == null) {
            return null;
        }
        for (Node child : children) {
            if (child.getChar() == ch) {
                return child;
            }
        }
        return null;
    }

    public char getChar() {
        return ch;
    }

    public List<Node> getChildren() {
        if (this.children == null) {
            return Collections.emptyList();
        }
        return children;
    }

    public boolean isEnd() {
        return end;
    }

    public void setEnd(boolean end) {
        this.end = end;
    }
}


Node root = new Node(' ');

public WordTree() {
}

/**
 * Searches for a strings that match the prefix.
 *
 * @param prefix - prefix
 * @return - list of strings that match the prefix, or empty list of no matches are found.
 */
public List<String> getWordsForPrefix(String prefix) {
    if (prefix.length() == 0) {
        return Collections.emptyList();
    }
    Node node = getNodeForPrefix(root, prefix);
    if (node == null) {
        return Collections.emptyList();
    }
    List<LinkedList<Character>> chars = collectChars(node);
    List<String> words = new ArrayList<String>(chars.size());
    for (LinkedList<Character> charList : chars) {
        words.add(combine(prefix.substring(0, prefix.length() - 1), charList));
    }
    return words;
}


private String combine(String prefix, List<Character> charList) {
    StringBuilder sb = new StringBuilder(prefix);
    for (Character character : charList) {
        sb.append(character);
    }
    return sb.toString();
}


private Node getNodeForPrefix(Node node, String prefix) {
    if (prefix.length() == 0) {
        return node;
    }
    Node next = node.getNode(prefix.charAt(0));
    if (next == null) {
        return null;
    }
    return getNodeForPrefix(next, prefix.substring(1, prefix.length()));
}


private List<LinkedList<Character>> collectChars(Node node) {
    List<LinkedList<Character>> chars = new ArrayList<LinkedList<Character>>();

    if (node.getChildren().size() == 0) {
        chars.add(new LinkedList<Character>(Collections.singletonList(node.getChar())));
    } else {
        if (node.isEnd()) {
            chars.add(new LinkedList<Character> 
            Collections.singletonList(node.getChar())));
        }
        List<Node> children = node.getChildren();
        for (Node child : children) {
            List<LinkedList<Character>> childList = collectChars(child);
            for (LinkedList<Character> characters : childList) {
                characters.push(node.getChar());
                chars.add(characters);
            }
        }
    }
    return chars;
}


public void addWord(String word) {
    addWord(root, word);
}

private void addWord(Node parent, String word) {
    if (word.trim().length() == 0) {
        return;
    }
    Node child = parent.getNode(word.charAt(0));
    if (child == null) {
        child = new Node(word.charAt(0));
        parent.addChild(child);
    } if (word.length() == 1) {
        child.setEnd(true);
    } else {
        addWord(child, word.substring(1, word.length()));
    }
}


public static void main(String[] args) {
    WordTree tree = new WordTree();
    tree.addWord("world");
    tree.addWord("work");
    tree.addWord("wolf");
    tree.addWord("life");
    tree.addWord("love");
    System.out.println(tree.getWordsForPrefix("wo"));
}

}

Вам нужно будет использовать List
List myList = new ArrayList ();
if (matchingStringFound)
myList.add (stringToAdd);

На мой взгляд, это проще решить рекурсивно. Это будет выглядеть примерно так:

1. Напишите рекурсивную функцию Print, которая печатает все узлы в тройке, корень которой находится в узле, заданном в качестве параметра. Wiki расскажет вам, как это сделать (посмотрите на сортировку).
2. Найдите последний символ вашего префикса и узел, который помечен этим символом, идите вниз от корня в вашей тройке. Вызовите функцию Print с этим узлом в качестве параметра. Затем убедитесь, что вы также выводите префикс перед каждым словом, так как это даст вам все слова без префикса.

Если вас не очень заботит эффективность, вы можете просто запустить Print с главным корневым узлом и вывести только те слова, которые начинаются с интересующего вас префикса. Это проще в реализации, но медленнее.

Вам нужно обойти поддерево, начиная с узла, который вы нашли для префикса.

Начните аналогичным образом, т.е. с поиска нужного узла. Затем, вместо проверки его маркера, пройдите по этому дереву (т.е. просмотрите всех его потомков; DFS - хороший способ сделать это), сохраняя подстроку, использованную для достижения "текущего" узла от первого узла.

Если текущий узел помечен как слово, выведите* префикс + достигнутую подстроку.

* или добавить его в список или что-то еще.