一篇学好如何实现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 
  
  
  
  
} 
 
 
 
 

分享题目：一篇学好如何实现Trie
文章路径：http://wtcwzsj.com/article/cdeeede.html