前綴樹又稱字典樹，每顆節點結構與一般樹有一點不同，
一般樹節點
struct TreeNode
{
valueType val;
vector<TreeNode*> next;//個數不固定，個數代表一個節點有多少個子節點
}
本題前綴樹節點
struct TrieNode
{
bool isEnd;//記錄這個節點是不是已經存進來的某個單詞的最后一個字母
vector<TrieNode*> next;//個數為26個，分別代表26個字母，
}
下圖為前綴樹的樣子（隱藏了next中為nullptr的節點）
建構式：Trie()
Trie():isEnd(false) ,next(26,nullptr)
{
}
注意，這里我用的vector，記憶體將由vector默認的allocater開辟，如果用的語言自帶的原生陣列(如：TrieNode* next[26]),需要自己手動開辟陣列memset(next,0,sizeof(next))，
插入函式：void insert(String word)
分析：我們需要遍歷這個單詞的每一個字符c，并查看當前這個節點的next[c-'a']是不是空，如果空，我們需要創建一個節點，并讓next[c-'a']指向它，如果不為空，就將node移動到它的next[c-'a']繼續查下去，如此下去，直至遍歷word結束，結束時，將當前節點的isEnd置為true，表示這是一個單詞的結尾，
void insert(string word) {
Trie* node = this;
for(char c : word)
{
if(node->next[c-'a']==nullptr)
{
node->next[c-'a'] = new Trie();
}
node = node->next[c-'a'];
}
node->isEnd = true;
}
查詢函式：boolean search(String word)
分析：這里需要查詢是否已經存有這個單詞，我們只需遍歷word，判斷當前節點的next[c-'a']是不是為空，空，就說明沒有這個單詞，非空，就節點下移，直至word掃描完畢，掃描完畢后，只能確定有這個前綴，所以還需要判斷當前節點的isEnd標記，如果isEnd為true，表示確實有這個單詞被存進來了，否則無，
bool search(string word) {
Trie* node = this;
for(char c : word)
{
if(node->next[c-'a']==nullptr)
{
return false;
}
else
{
node = node->next[c - 'a'];
}
}
return node->isEnd;
}
查詢前綴函式：boolean startsWith(String prefix)
分析：這個和前面的查詢邏輯差不多，唯一的區別在于，不需要檢查isEnd標記，只要遍歷word都能找到對于的節點，就行，
bool startsWith(string prefix) {
Trie* node = this;
for(char c : prefix)
{
if(node->next[c - 'a']==nullptr)
{
return false;
}
else
{
node = node ->next[c-'a'];
}
}
return true;
}
又學到一個新東西，前綴樹
另外，寫著寫著，突然發現我寫的是“節點”，看見有人是“結點”，我就查了下，發現都可以的哈！：）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276108.html
標籤：其他