一篇文章搞懂Trie樹 | C++實現以及實戰練習

05-16

來自專欄如何快速高效學習C++？

上圖，就是一棵Trie樹，廢話不多說，如何實現這樣的數據結構呢？

參考題目：
LeetCode：208. Implement Trie (Prefix Tree)
LeetCode：211. Add and Search Word - Data structure design
LeetCode：212. Word Search II

一、初步實現Trie樹結構

Implement Trie (Prefix Tree) - LeetCode?

leetcode.com

LeetCode上剛好有一道題，要求實現Trie樹的幾個操作：

Implement a trie with insert, search, and startsWith methods.

分別是Tire樹的插入，搜索以及查找是否存在以某個Prefix開頭的單詞。

別急著往下看，不妨自己先思考一下，嘗試著做一做。

考慮到題目要求插入的字元串中只包含小寫字母，那麼我們可以採取這樣的Trie樹節點：

class TrieNode{public: TrieNode* next[26]; bool isword; TrieNode(){ memset(next,NULL,sizeof(next)); isword=false; } ~TrieNode(){ for(int i=0;i<26;i++)if(next[i])delete next[i]; }};

是不是很像二叉樹？唯二的區別在於

I、二叉樹只有左右兩個孩子節點，而這個TrieNode有26個next孩子節點。

II、多了一個bool變數isword，如果為true，表示該節點表示的字元串（準確地說，是從根節點一直next到此節點表示的字元串）在Trie樹中存在，否則不存在。

好了，有了這樣一個基本點TrieNode結構，我們可以開始設計題目要求的三個API了。

別急，先把構造函數和析構函數寫好：

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

雖然不寫析構函數也能AC，甚至更快，但內存泄漏畢竟不是什麼好玩的東西，還是寫上吧。

1、插入：

void insert(string word) { TrieNode*p=root; for(int i=0;i<(int)word.size();i++){ if(p->next[word[i]-a]==NULL) p->next[word[i]-a]=new TrieNode(); p=p->next[word[i]-a]; } p->isword=true; }

遍歷需要插入的string，同時指針p從root一直往下next，如果對應字元的next為NULL，就創建一個新的TrieNode，遍歷完後，在最終那個TireNode標記為True，表示這個TrieNode對應的詞在這課Trie樹中存在。

2、查找：

和插入的思路類似，遍歷string，同時指針p從root節點一直往下next，如果碰到對應字元的next[]為NULL或者string已經遍歷完成，則退出循環。最後檢查p是否為不為NULL以及isword是否為true，兩者都滿足則說明這個詞存在於Trie樹。

bool search(string word) { TrieNode *p=root; for(int i=0;i<(int)word.size()&&p;i++){ p=p->next[word[i]-a]; } return p&&p->isword; }

3、前綴查找：

bool startsWith(string prefix) { TrieNode*p=root; for(int i=0;i<(int)prefix.size()&&p;i++){ p=p->next[prefix[i]-a]; } return p; }

實現上基本同查找，唯一的區別在於，無需檢查isword是否為true。

完整AC代碼：

class TrieNode{public: TrieNode* next[26]; bool isword; TrieNode(){ memset(next,NULL,sizeof(next)); isword=false; } ~TrieNode(){ for(int i=0;i<26;i++)if(next[i])delete next[i]; }};class Trie { TrieNode* root;public: /** Initialize your data structure here. */ Trie() { root=new TrieNode(); } /** Inserts a word into the Trie. */ void insert(string word) { TrieNode*p=root; for(int i=0;i<(int)word.size();i++){ if(p->next[word[i]-a]==NULL) p->next[word[i]-a]=new TrieNode(); p=p->next[word[i]-a]; } p->isword=true; } /** Returns if the word is in the Trie. */ bool search(string word) { TrieNode *p=root; for(int i=0;i<(int)word.size()&&p;i++){ p=p->next[word[i]-a]; } return p&&p->isword; } /** Returns if there is any word in the Trie that starts with the given prefix. */ bool startsWith(string prefix) { TrieNode*p=root; for(int i=0;i<(int)prefix.size()&&p;i++){ p=p->next[prefix[i]-a]; } return p; } ~Trie(){ delete root; }};/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * bool param_2 = obj.search(word); * bool param_3 = obj.startsWith(prefix); */

提交結果：

二、Trie樹的運用：Trie樹+回溯法

充分理解這道題後，就可以接著將這種數據結構投入運用了。

Add and Search Word - Data structure design - LeetCode?

leetcode.com

這一道題和上一題類似，需要你實現兩個API，一個插入，一個查找。插入和上一題相同，查找則需要實現「模糊查找」即：

For example:

addWord("bad")addWord("dad")addWord("mad")search("pad") -> falsesearch("bad") -> truesearch(".ad") -> truesearch("b..") -> true

看到這裡，不妨自己先想一想如何實現，有了思路再接著往下看：

1、數據結構（同上題）

class trienode{public: bool isword; trienode*next[26]; trienode(){ isword=false; memset(next,NULL,sizeof(next)); } ~trienode(){ for(int i=0;i<26;i++){ if(next[i])delete next[i]; } }};

2、構造函數、析構函數以及插入API（同上題）

class WordDictionary { trienode*root;public: /** Initialize your data structure here. */ WordDictionary() { root=new trienode(); } ~WordDictionary(){ delete root; } void addWord(string word) { trienode*p=root; for(char &ch:word){ if(p->next[ch-a]==NULL) p->next[ch-a]=new trienode(); p=p->next[ch-a]; } p->isword=true; }}；

3、模糊查找API（回溯法，詳見注釋）

bool search(string word) { trienode*p=find(root,word); return p&&p->isword;//如果p存在且isword為true，則模糊查找到匹配的字元串 }trienode*find(trienode*p,string word){ for(int i=0;i<(int)word.size()&&p;i++){ if(word[i]==.){ for(int j=0;j<26;j++){ if(p->next[j]){//用任何一個字元來匹配『.』 int len=(int)word.size()-i-1; if(len>=1){ trienode*res=find(p->next[j],word.substr(i+1,len)); if(res&&res->isword)return res; }else if(p->next[j]->isword)return p->next[j]; }//如果找到了匹配的字元，直接返回，若沒有，則繼續尋找。 } return NULL;//找遍所有的樹，也沒找到模糊匹配的，返回NULL }else{ p=p->next[word[i]-a]; } } return p; }

完整AC代碼：

class trienode{public: bool isword; trienode*next[26]; trienode(){ isword=false; memset(next,NULL,sizeof(next)); } ~trienode(){ for(int i=0;i<26;i++){ if(next[i])delete next[i]; } }};class WordDictionary { trienode*root;public: /** Initialize your data structure here. */ WordDictionary() { root=new trienode(); } /** Adds a word into the data structure. */ void addWord(string word) { trienode*p=root; for(char &ch:word){ if(p->next[ch-a]==NULL) p->next[ch-a]=new trienode(); p=p->next[ch-a]; } p->isword=true; } /** Returns if the word is in the data structure. A word could contain the dot character . to represent any one letter. */ bool search(string word) { trienode*p=find(root,word); return p&&p->isword; } ~WordDictionary(){ //delete root; }private: trienode*find(trienode*p,string word){ for(int i=0;i<(int)word.size()&&p;i++){ if(word[i]==.){ for(int j=0;j<26;j++){ if(p->next[j]){ int len=(int)word.size()-i-1; if(len>=1){ trienode*res=find(p->next[j],word.substr(i+1,len)); if(res&&res->isword)return res; }else if(p->next[j]->isword)return p->next[j]; //if(i==(int)word.size())return p->find(p->next[j],word.substr(i+1))) } } return NULL; }else{ p=p->next[word[i]-a]; } } return p; }};/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * bool param_2 = obj.search(word); */

提交結果：

三、Trie樹的運用：Trie樹+深度優先搜索

Word Search II - LeetCode?

leetcode.com

此題咋一看，很簡單嘛，把針對每個單詞進行一次深度優先搜索不就行了？這個思路是可行的，但十有八九會超時。因為深度優先搜索本身就是一種比較耗時間和內存的演算法。

但這道題似乎也只好用深度優先搜索，那麼，有沒有可能只進行一次搜索，就查明白所有的單詞是否存在於這個二維矩陣中？

是的，這個時候你需要Trie樹。

AC代碼：

class trienode{//樹節點結構public: trienode*next[26]; int isexist;//-1表示節點表示的單詞不存在，0及以上的數表示此單詞存在且與vector<string>>words的序號對應 trienode(){ memset(next,NULL,sizeof(next)); isexist=-1; } ~trienode(){ for(int i=0;i<26;i++){ if(next[i])delete next[i]; } }};class Solution {public: int arr[4][2]={{1,0},{-1,0},{0,-1},{0,1}};//搜索的四個方向 void insert(trienode*root,string& s,int&index){ for(int i=0;i<(int)s.size();i++){ if(!root->next[s[i]-a]){ root->next[s[i]-a]=new trienode(); } root=root->next[s[i]-a]; } root->isexist=index; } void dfs(int r,int c,trienode*root,unordered_set<int>&res,vector<vector<char>>b){ b[r][c]=0;//標記已經搜索過得地方為『0』 if(root&&root->isexist>=0){//如果isexist>=0表示word[isexist]存在於此節點。 res.insert(root->isexist); } for(int i=0;i<4;i++){//向上下左右四個方向搜索 int newr=r+arr[i][0],newc=c+arr[i][1]; if(newr>=0&&newc>=0&&newr<b.size()&&newc<b[0].size()&&b[newr][newc]!=0&&root->next[b[newr][newc]-a]){ dfs(newr,newc,root->next[b[newr][newc]-a],res,b); } } } vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { trienode* root=new trienode(); for(int i=0;i<(int)words.size();i++){ insert(root,words[i],i);//將所有的單詞插入Trie樹 } unordered_set<int>res;//用於保存在board中查找到的words的序號 for(int r=0;r<(int)board.size();r++){ for(int c=0;c<(int)board[r].size();c++){ if(root->next[board[r][c]-a])dfs(r,c,root->next[board[r][c]-a],res,board); } } vector<string>ress;//根據res中的序號製作string數組返回 for(auto it:res){ ress.push_back(words[it]); } return ress; }};

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：