字首樹Trie

​

字首樹（字典樹） 是一種多叉樹結構，用于高效地存儲和檢索字元串資料集中的鍵。這一資料結構有相當多的應用情景，例如自動補完和拼寫檢查

每個節點存放兩個資訊：

• chidren 是一個大小為 26 的一維數組，分别對應了26個英文字元 'a' ~ 'z'，也就是說形成了一棵 26叉樹
• isEnd 判斷樹的根節點到目前節點是否構成了一個單詞

class Trie {
        private Trie[] children;
        private boolean isEnd;
        public Trie() {
            children = new Trie[26]; // 隻是定義了一下，沒有執行個體化，相當于樹枝在那兒，但是沒有連結節點
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for(int i=0; i<word.length(); i++){
                char ch = word.charAt(i);
                int index = ch - 'a';
                if(node.children[index] == null){
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;  //目前節點是最後一個
        }

        public boolean search(String word) {
            Trie node = this;   //建立一個Trie對象，即一個新的節點，給節點指向目前字典樹的根節點
            for(int i=0; i<word.length(); i++){
                char ch = word.charAt(i);
                int index = ch - 'a';
                if(node.children[index] == null){   //這個位置的節點是空的，那麼就要重新建立
                    return false;
                }
                node = node.children[index];   // 将節點下移
            }
            if(node.isEnd == true){
                return true;
            }else {
                return false;
            }
        }

        public boolean startsWith(String prefix) {  //判斷字首
            Trie node = this;
            for(int i=0; i<prefix.length(); i++){
                char ch = prefix.charAt(i);
                int index = ch-'a';
                if(node.children[index] == null){
                    return false;
                }
                node = node.children[index];
            }
            return true;
        }
    }