一篇学好如何实现 Trie

本文转载自微信公众号「我好困啊」，篇学作者mengxin。好何转载本文请联系我好困啊公众号。实现

Trie又称为字典树，篇学主要用于单词的好何查找得名。如将一个单词 Hello存放在字典树中的实现数据结构为:

当再次加入help时，此时的篇学字典树为：

当添加hero时，此时的好何字典树为：

可以看到树以每个单词的字符为一个节点，服务器租用直到字符添加完毕后设置上flag，实现标记当前节点结束为一个单词(即从根节点到当前节点为一个单词)。篇学

当有新的好何单词进来时，只需要添加到树中即可，实现查找时，篇学从根节点出发，好何遍历整棵树(其实总是实现遍历树的某个分支)。如果其中一个字符不在树中，则说明查找失败，亿华云否则所有的word按每个字符的顺序都能查找到，最后判断结束节点是否为一个单词，是，则查找成功。

代码实现

//叶子节点 type Node struct {      isWord bool   //是否为一个单词     next map[uint8]*Node //叶子节点对应的单个字符及其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 }