一篇学好如何实现Trie

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

创新互联公司是一家集网站建设,蓝山企业网站建设,蓝山品牌网站建设,网站定制,蓝山网站建设报价,网络营销,网络优化,蓝山网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

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

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

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

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

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

代码实现

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

当前文章：一篇学好如何实现Trie
URL地址：http://www.csdahua.cn/qtweb/news10/531160.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

电子商务知识

各行业网站

混凝土搅拌罐车　　 　宜宾冠赛网站　　 　门户网站建设方案　　 　成都网站制作　　 　重庆网站制作　　 　草坪音箱　　 　雅安电信机房　　 　成都标志设计　　 　佑馨产后护理　　 　装饰公司网站建设方案　　 　四川广汉锦华　　 　店面门头广告　　 　重庆服务器托管　　 　成都租用服务器　　 　网站SEO优化　　 　眉山做网站　　 　成都广告招牌　　 　重庆网站建设网络公司　　 　云主机　　 　移动手机网站制作