Trie树的java实现

public class Trie {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("app"));     // returns false
        System.out.println(trie.startsWith("app")); // returns true
        trie.insert("app");
        System.out.println(trie.search("app"));     // returns true
    }

    TrieNode root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        root = new TrieNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        insert(word, root, 0);
    }

    /**
     * 将从index处开始的字串插入到root的子节点中，即将index对应的字符插入到root的子节点中
     * @param word
     * @param root
     * @param index
     */
    private void insert(String word, TrieNode root, int index) {
        assert index  -1;
        char cur = word.charAt(index);
        TreeMap children = root.children;
        if (null == children) {
            children = new TreeMap();
            root.children = children;
        }
        if (!children.containsKey(cur)) {
            children.put(cur, new TrieNode(cur));
        }
        if (index == word.length() - 1) {
            children.get(cur).occurency++;
            return;
        }
        insert(word, children.get(cur), index + 1);
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        return search(word, root, 0);
    }

    /**
     * 在root的子节点中搜索从index开始的字串
     * @param word
     * @param root
     * @param index
     * @return
     */
    private boolean search(String word, TrieNode root, int index) {
        assert index > -1 && index  word.length();
        char cur = word.charAt(index);
        if (root.children == null ||
                !root.children.containsKey(cur)) {
            return false;
        }
        if (index == word.length() - 1) {
            return root.children.get(cur).occurency > 0;
        }
        return search(word, root.children.get(cur), index + 1);
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        return startsWith(prefix, root, 0);
    }

    /**
     * 在root的子节点中搜索从index开始字串对应的前缀
     * @param prefix
     * @param root
     * @param index
     * @return
     */
    private boolean startsWith(String prefix, TrieNode root, int index) {
        assert index > -1 && index  prefix.length();
        char cur = prefix.charAt(index);
        if (root.children == null ||
                !root.children.containsKey(cur)) {
            return false;
        }
        if (index == prefix.length() - 1) {
            return true;
        }
        return startsWith(prefix, root.children.get(cur), index + 1);
    }

    static class TrieNode {
        char c;
        int occurency = 0;
        TreeMap children;

        public TrieNode() {
        }

        public TrieNode(char c) {
            this.c = c;
        }
    }
}