Go语言中字典树的实现_go 实现字典树

写在前面

字典树在存储、查询方面应用广泛。所以特总结一下，利用GO语言实现字典树。

具体实现

字典树的实现主要还是基于树形结构，如果只是小写字母的话，那其实字典树是一个26叉树，每个节点最多都可以有26个子节点。从而可以利用一个长度为26的数组来记录某个节点的子节点情况。并且每个节点可以使用一个布尔标志位来划定是否是一个单词，这是关键所在，具体代码见下：

type Trie struct {
    children [26]*Trie
    isEnd    bool
}

func Constructor() Trie {
    return Trie{}
}

func (t *Trie) Insert(word string) {
    node := t
    for _, ch := range word {
        ch -= 'a'
        if node.children[ch] == nil {
            node.children[ch] = &Trie{}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *Trie) SearchPrefix(prefix string) *Trie {
    node := t
    for _, ch := range prefix {
        ch -= 'a'
        if node.children[ch] == nil {
            return nil
        }
        node = node.children[ch]
    }
    return node
}

func (t *Trie) Search(word string) bool {
    node := t.SearchPrefix(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.SearchPrefix(prefix) != nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

供自己之后复习查询。