怎么實(shí)現(xiàn)Trie

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

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

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

當(dāng)再次加入help時(shí)，此時(shí)的字典樹(shù)為：

當(dāng)添加hero時(shí)，此時(shí)的字典樹(shù)為：

可以看到樹(shù)以每個(gè)單詞的字符為一個(gè)節(jié)點(diǎn)，直到字符添加完畢后設(shè)置上flag，標(biāo)記當(dāng)前節(jié)點(diǎn)結(jié)束為一個(gè)單詞(即從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)為一個(gè)單詞)。

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

代碼實(shí)現(xiàn)

//葉子節(jié)點(diǎn) type Node struct {     isWord bool   //是否為一個(gè)單詞     next map[uint8]*Node //葉子節(jié)點(diǎn)對(duì)應(yīng)的單個(gè)字符及其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 }   /**查找對(duì)應(yīng)前綴 */ 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 }

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

網(wǎng)頁(yè)標(biāo)題：怎么實(shí)現(xiàn)Trie
瀏覽路徑：http://muchs.cn/article14/gphoge.html

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

廣告

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