對字典樹的理解:

a.Trie字典樹又可以稱為前綴樹,是一種真正為字典設計的數(shù)據(jù)結構,其中的核心實現(xiàn)就包含了字典Map.
b.Trie專門用來處理字符串相關的問題,運行十分高效.其運算時的復雜度跟樹的規(guī)模無關,只跟用于操作的目標字符串W的長度L相關,即O(L).鑒于大部分的字符串長度一般都較短(10+的很少)即字典樹相對其他結構有著明顯更低的時間復雜度-->例如:一個100w規(guī)模的條目,即使使用樹結構,時間復雜度為logn級別,基本上為20,對比得到,在較大規(guī)模的數(shù)據(jù)背景下可以看出Trie字典樹的優(yōu)勢.
c.Trie樹的結構如圖1

圖1 Trie樹的結構原理

從結構圖中可以看出(1).Trie樹結構是由一個一個節(jié)點構成
(2).每個節(jié)點代表的是一個對應的字符
(3).每個節(jié)點上都掛載有子節(jié)點.

設計代碼:

設計思路:

從Trie樹的結構上看,Trie也是一個一個節(jié)點node相互掛接而成,并且每個節(jié)點都包含相應的變量var信息.到這里,可以發(fā)現(xiàn)Trie和鏈表LinkedList似乎是完全一樣.但進一步讀圖可以發(fā)現(xiàn)--->①Trie樹并非是二叉樹,而是多叉樹,并且不同的父親節(jié)點帶子節(jié)點的數(shù)量也是不定的,鏈表的父子節(jié)點則是一一鏈接的.②節(jié)點表達的信息是字符,每個節(jié)點Node和字符Chararter一一對應.
綜上所述的思路,可以將Trie設計為以Node節(jié)點為基本單元的數(shù)據(jù)結構,節(jié)點之間相互鏈接,節(jié)點相互多鏈接的屬性體現(xiàn)為節(jié)點掛載節(jié)點集合,又由于節(jié)點的字符和節(jié)點本身是一一對應,那么集合選擇為字典Map.

class Node{
                 public boolean isWord;
        public TreeMap<Character,Node> next;        
}

核心代碼實現(xiàn):

/**
 * class Trie
 * @author Administrator
 *
 */
import java.util.TreeMap;
public class Trie {
    /**
     * aim class --> connect each other
     * @author Administrator
     *
     */
    private class Node{
        public boolean isWord;
        // the TreeMap support generic
        public TreeMap<Character,Node> next;
        
        public Node(boolean isWord) {
            this.isWord = isWord;
            next = new TreeMap<>();
        }
        
        public Node() {
            this(false);
        }
    }
    private int size;
    private Node root;
    
    /**
     * constructor
     */
    public Trie() {
        size = 0;
        root = new Node();
    }
    
    public int getSize() {
        return size;
    }
    
    /**
     * add method-->add a new word into Trie tree
     * @param word
     */
    public void add(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c= word.charAt(i);
            if (cur.next.get(c) == null) {
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        
        if (!cur.isWord) {
            cur.isWord = true;
            size++;
        }   
    }
    
    /**
     * method contains --> determine whether the target String if in the Trie
     * @param word
     * @return
     */
    public boolean contains(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c)==null) {
                return false;
            }
            cur = cur.next.get(c);
        }
        if (!cur.isWord) {
            cur.isWord = true;
        }
        return true;
    }
    
    public boolean isPrefix(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (cur.next.get(c) == null) {
                return false;               
            }
            else {
                cur = cur.next.get(c);
            }
        }
        /**
         * determine if there are any words after the prefix
         */
        if (cur.next.keySet()!=null) {
            return true;    
        }
        else
            return false;
    }
}