怎么实现Trie

这篇文章主要为大家展示了“怎么实现Trie”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“怎么实现Trie”这篇文章吧。

创新互联建站网站建设公司,提供成都网站设计、网站建设,网页设计,建网站,PHP网站建设等专业做网站服务;可快速的进行网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,是专业的做网站团队,希望更多企业前来合作!

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

怎么实现Trie

当再次加入help时,此时的字典树为:

怎么实现Trie

当添加hero时,此时的字典树为:

怎么实现Trie

可以看到树以每个单词的字符为一个节点,直到字符添加完毕后设置上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 }

以上是“怎么实现Trie”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!


分享文章:怎么实现Trie
分享网址:http://pwwzsj.com/article/gphoge.html