办公常用软件技术学习网

办公常用软件技术学习网、Excel技术学习、PPT技术学习、Word技术学习、AI技术学习、PS技术学习,开发技术,数据库开发,SEO教程

联系客服联系客服

您现在的位置是:首页>技术开发>一篇学好如何实现 Trie

一篇学好如何实现 Trie

2021-06-04 10:18 栏目:技术开发

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

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

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

可以看到树以每个单词的字符为一个节点,直到字符添加完毕后设置上flag,标记当前节点结束为一个单词(即从根节点到当前节点为一个单词)。

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

代码实现

  1. //叶子节点 
  2. type Node struct { 
  3.     isWord bool   //是否为一个单词 
  4.     next map[uint8]*Node //叶子节点对应的单个字符及其next指针 
  5.  
  6. type Trie struct { 
  7.     root *Node 
  8.     size int64 
  9.  
  10. func Constructor() Trie { 
  11.     return Trie{&Node{ 
  12.         isWord: false
  13.         next:  make(map[uint8]*Node), 
  14.     },0} 
  15.  
  16. /** 添加单词到字典中 */ 
  17. func (this *Trie) Insert(word string)  { 
  18.     if  word ==""
  19.         return 
  20.     } 
  21.     cur := this.root 
  22.  
  23.     for i:= 0;i< len(word);i++ { 
  24.         r := word[i] 
  25.         if  cur.next[r]== nil{ 
  26.             cur.next[r] = &Node{false, make(map[uint8]*Node)} 
  27.         } 
  28.         cur = cur.next[r] 
  29.     } 
  30.     if !cur.isWord { 
  31.         cur.isWord = true 
  32.     } 
  33.  
  34.  
  35.  
  36. /** 查找单词 */ 
  37. func (this *Trie) Search(word string) bool { 
  38.     if  word ==""
  39.         return false 
  40.     } 
  41.     cur := this.root 
  42.  
  43.     for i:= 0;i< len(word);i++ { 
  44.         r := word[i] 
  45.         if  cur.next[r]== nil{ 
  46.             return false 
  47.         } 
  48.         cur = cur.next[r] 
  49.     } 
  50.     return cur.isWord 
  51.  
  52.  
  53. /**查找对应前缀 */ 
  54. func (this *Trie) StartsWith(prefix string) bool { 
  55.     if  prefix ==""
  56.         return false 
  57.     } 
  58.     cur := this.root 
  59.  
  60.     for i:= 0;i< len(prefix);i++ { 
  61.         r := prefix[i] 
  62.         if  cur.next[r]== nil{ 
  63.             return false 
  64.         } 
  65.         cur = cur.next[r] 
  66.     } 
  67.     return true 

【编辑推荐】

  1. 鸿蒙官方战略合作共建——HarmonyOS技术社区
  2. CIO如何做到并保持数据驱动
  3. 数据库:MySQL、HBase、ElasticSearch三者对比
  4. 基于Flink CDC打通业务数据实时入湖
  5. MySQL 一棵 B+ 树能存多少条数据?
  6. 与黑客讨价还价,勒索攻击企业数据是关键

上一篇:Java 程序员常犯的 10 个 SQL 错误!

下一篇:5月份Github上Java开源项目排行