字典樹原理：

字典數(shù)將相同前綴的單詞做為共用的前綴，如果找不到這個前綴，則在另外一個結(jié)點上插入這個單詞。并且在這個單詞結(jié)尾的結(jié)點加上1。

class Trie { private:bool isEnd;Trie *next[26];public:Trie(){isEnd=false;memset(next,0,sizeof(next));}void Insert(string word){Trie* node=this;for(char ch:word){if(node->next[ch-'a']==NULL){node->next[ch-'a']=new Trie();}node=node->next[ch-'a'];}node->isEnd=true;}bool Search(string word){Trie* node=this;for(char ch:word){node=node->next[ch-'a'];if(node==NULL){return false;}}return node->isEnd;}bool StartsWith(string prefix){Trie* node=this;for(char ch:prefix){node=node->next[ch-'a'];if(node==NULL){return false;}}return true;} };

總結(jié)
通過以上介紹和代碼實現(xiàn)我們可以總結(jié)出 Trie 的幾點性質(zhì)：

Trie 的形狀和單詞的插入或刪除順序無關(guān)，也就是說對于任意給定的一組單詞，Trie 的形狀都是唯一的。

查找或插入一個長度為 L 的單詞，訪問 next 數(shù)組的次數(shù)最多為 L+1，和 Trie 中包含多少個單詞無關(guān)。

Trie 的每個結(jié)點中都保留著一個字母表，這是很耗費空間的。如果 Trie 的高度為 n，字母表的大小為 m，最壞的情況是 Trie 中還不存在前綴相同的單詞，那空間復(fù)雜度就為 O(m^n)O(m?
n
?)。

最后，關(guān)于 Trie 的應(yīng)用場景，希望你能記住 8 個字：一次建樹，多次查詢。(慢慢領(lǐng)悟叭~~)

?

總結(jié)

以上是生活随笔為你收集整理的C++图解前缀树（字典树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。