這篇文章主要為大家展示了“怎么實現(xiàn)Trie”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學習一下“怎么實現(xiàn)Trie”這篇文章吧。

創(chuàng)新互聯(lián)建站網(wǎng)站建設公司，提供成都網(wǎng)站設計、網(wǎng)站建設，網(wǎng)頁設計，建網(wǎng)站，PHP網(wǎng)站建設等專業(yè)做網(wǎng)站服務;可快速的進行網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展；專業(yè)做搜索引擎喜愛的網(wǎng)站，是專業(yè)的做網(wǎng)站團隊，希望更多企業(yè)前來合作!

Trie又稱為字典樹，主要用于單詞的查找得名。如將一個單詞 Hello存放在字典樹中的數(shù)據(jù)結(jié)構(gòu)為:

當再次加入help時，此時的字典樹為：

當添加hero時，此時的字典樹為：

可以看到樹以每個單詞的字符為一個節(jié)點，直到字符添加完畢后設置上flag，標記當前節(jié)點結(jié)束為一個單詞(即從根節(jié)點到當前節(jié)點為一個單詞)。

當有新的單詞進來時，只需要添加到樹中即可，查找時，從根節(jié)點出發(fā)，遍歷整棵樹(其實總是遍歷樹的某個分支)。如果其中一個字符不在樹中，則說明查找失敗，否則所有的word按每個字符的順序都能查找到，最后判斷結(jié)束節(jié)點是否為一個單詞，是，則查找成功。

代碼實現(xiàn)

//葉子節(jié)點 type Node struct {     isWord bool   //是否為一個單詞     next map[uint8]*Node //葉子節(jié)點對應的單個字符及其next指針 }  type Trie struct {     root *Node     size int64 }  func Constructor() Trie {     return Trie{&Node{         isWord: false,         next:  make(map[uint8]*Node),     },0} }  /** 添加單詞到字典中 */ func (this *Trie) Insert(word string)  {     if  word ==""{         return     }     cur := this.root      for i:= 0;i< len(word);i++ {         r := word[i]         if  cur.next[r]== nil{             cur.next[r] = &Node{false, make(map[uint8]*Node)}         }         cur = cur.next[r]     }     if !cur.isWord {         cur.isWord = true     }  }   /** 查找單詞 */ func (this *Trie) Search(word string) bool {     if  word ==""{         return false     }     cur := this.root      for i:= 0;i< len(word);i++ {         r := word[i]         if  cur.next[r]== nil{             return false         }         cur = cur.next[r]     }     return cur.isWord }   /**查找對應前綴 */ func (this *Trie) StartsWith(prefix string) bool {     if  prefix ==""{         return false     }     cur := this.root      for i:= 0;i< len(prefix);i++ {         r := prefix[i]         if  cur.next[r]== nil{             return false         }         cur = cur.next[r]     }     return true }

以上是“怎么實現(xiàn)Trie”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)頁標題：怎么實現(xiàn)Trie
瀏覽路徑：http://chinadenli.net/article14/gphoge.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供手機網(wǎng)站建設、商城網(wǎng)站、用戶體驗、品牌網(wǎng)站建設、定制開發(fā)、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)