文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

一篇学好如何实现 Trie

2024-12-03 04:09

关注

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

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 

 

 

来源:我好困啊内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯