[[403657]]

本文轉(zhuǎn)載自微信公眾號(hào)「我好困啊」，作者mengxin。轉(zhuǎn)載本文請(qǐng)聯(lián)系我好困啊公眾號(hào)。

Trie又稱(chēng)為字典樹(shù)，主要用于單詞的查找得名。如將一個(gè)單詞 Hello存放在字典樹(shù)中的數(shù)據(jù)結(jié)構(gòu)為:

當(dāng)再次加入help時(shí)，此時(shí)的字典樹(shù)為：

當(dāng)添加hero時(shí)，此時(shí)的字典樹(shù)為：

可以看到樹(shù)以每個(gè)單詞的字符為一個(gè)節(jié)點(diǎn)，直到字符添加完畢后設(shè)置上flag，標(biāo)記當(dāng)前節(jié)點(diǎn)結(jié)束為一個(gè)單詞(即從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)為一個(gè)單詞)。

當(dāng)有新的單詞進(jìn)來(lái)時(shí)，只需要添加到樹(shù)中即可，查找時(shí)，從根節(jié)點(diǎn)出發(fā)，遍歷整棵樹(shù)(其實(shí)總是遍歷樹(shù)的某個(gè)分支)。如果其中一個(gè)字符不在樹(shù)中，則說(shuō)明查找失敗，否則所有的word按每個(gè)字符的順序都能查找到，最后判斷結(jié)束節(jié)點(diǎn)是否為一個(gè)單詞，是，則查找成功。

代碼實(shí)現(xiàn)

//葉子節(jié)點(diǎn) 
type Node struct { 
    isWord bool   //是否為一個(gè)單詞 
    next map[uint8]*Node //葉子節(jié)點(diǎn)對(duì)應(yīng)的單個(gè)字符及其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 
} 
 
 
/**查找對(duì)應(yīng)前綴 */ 
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 
}