简介

Trie 树，一种高效的字符串匹配与查找的数据结构，它的本质是 N 叉树。
根据它的用途和特点，它又称为前缀树，字典树，键树等。

数据结构定义

从一个简单的例子来引出 Trie 树的数据结构，在日常生活中，我们会使用各种翻译软件，比如当我们要查询一个英文单词 synchronization 是什么意思时，当我们输入这个单词的一部分，便会出现许多的选项供我们选择，如下图所示：

不难发现，每个可以选择项都有一个共同特点：它们有公共的前缀 synchro。
那么这种功能是怎么实现的呢？雏形便是 Trie 树！
它的数据结构如下：

type trieNode struct {
    c        byte            // 存储的字符
    children []*trieNode    // 孩子节点
    isWord   bool            // 是否构成单词
}

Trie 树有几个特点：

根节点不包含任何字符。
每一个节点只存储 1 个字符。
每一个节点的所有孩子节点存储的字符互不相同。
从根结点到某一子节点路径上所有字符构成一个字符串。

以 ice, io, an, ant, as, bus, buff 为例，构建的 Trie 树如下：

可以看到，从根结点一直往左走到叶子节点 t，图中构成的字符串中 a, an, ant 都是合法的单词，而 bu, buf 却不是，但可以肯定的是，从根结点到叶子节点的路径上所有字符构成的字符串必然是一个单词。

基本操作

对于 Trie 树，基本操作有两个：插入和查找，删除用得较少。

查找的实现

查找比较简单，对于一个长度为 L 的单词 word，如果它在 Trie 树中，那么 word[i] 必然要出现第 i+1 层，其中
前缀树 - 图3 ，那么我们一层层地查下去就可以了。
以查找 buff 为例：

从根结点出发，查看它的所有孩子中是否有节点 b，有则继续从它往下查，否则说明该单词不在 Trie 树中。
节点 b 下有节点 u，节点 u 下有节点 f，节点 f 下有节点 f，查找完毕。

什么时候查找失败呢？

某一层没有匹配的节点（见定义）。
查到了叶子节点仍然没有匹配完整个单词。

什么时候查找成功呢？

单词中每个字符都被匹配了。

代码实现如下：

// 查找节点 root 的孩子节点是否有含有字符 x
// 找到则返回该节点
func match(root *trieNode, x byte) *trieNode {
    // 空 Trie 树
    if root == nil {
        return nil
    }
    // 尝试匹配
    for _, node := range root.children {
        if node.c == x {    // 匹配成功
            return node
        }
    }
    return nil                // 匹配失败
}

// Find 查找 Trie 树中是否有单词 word
func (root *trieNode) Find(word string) bool {
    // 递归出口
    if len(word) == 0 {
        return true
    } 
    // 尝试匹配
    node := match(root, word[0])
    if node == nil {            // 匹配失败
        return false
    }
    return node.Find(word[1:])    // 继续匹配
}

插入的实现

对于一个要插入的单词，我们只需要从它的非前缀部分即可，比如现在插入单词 and，我们可以发现前面一部分 an 已经存在树中，只需要给节点 n 增加一个孩子节点 d 即可。
算法思路：从左往右匹配单词的每个字符，直至匹配失败，此时在匹配失败的节点下依次插入剩余字符。

// 版本 1
func (root *trieNode) Insert(word string) {
    if len(word) == 0 {
        return
    }
    if node := match(root, word[0]); node != nil {
        node.Insert(word[1:])
    } else {
        root.children = append(root.children, &trieNode{c: word[0], children: nil, isWord: false})
        node = match(root, word[0])
        node.Insert(word[1:])
    }
}

// 版本 2
// Insert 插入一个单词 word
func (root *trieNode) Insert(word string) {
    if node := match(root, word[0]); node != nil {
        if len(word) == 1 {        
            node.isWord = true     
            return
        }
        node.Insert(word[1:])
    } else {
        newTrieNode := &trieNode{c: word[0], children: nil, isWord: false}
        if len(word) == 1 {
            newTrieNode.isWord = true
            root.children = append(root.children, newTrieNode)
            return
        }
        root.children = append(root.children, newTrieNode)
        newTrieNode.Insert(word[1:])
    }
}

代码解释如下：
以插入 ant 为例，版本 1 有一个缺陷：不能实现 isWord 功能，全都节点的 isWord 都是 false。
而理论上至少每个叶子节点的 isWord 都肯定是 true，非叶子节点也可以有 true，比如插入 ant 时，a, an, ant 都是一个完整的单词，因此节点 a, n, t 的 isWord 都应该为 true。
版本 2 虽然能够再插入时完成叶子节点的 isWord 为 true，即 t.isWord = true，但是 a.isWord = false, n.isWord = false 而且代码难看= =！
对比来看，版本 2 更满足要求，因此采用它。
出现上述缺陷的根本原因是，一个单词的前缀部分有可能也是一个完整的单词！
因此如果要在插入时实时确定每个节点的 isWord 字段取值，需要一个算法，来确定当前字符串是否为一个完整的单词，但不可能存在这样的算法。
所以，最终的决定权交给的用户，我们选择相信用户，用户插入任何字符串，我们都认为是一个完整的单词，此时如果用户先后插入 ant 和 an，版本 2 能在插入 an 时让 n.isWord = true，有兴趣的朋友可以试试，下面完整的代码中提供了层次遍历，打印结果验证即可。

完整代码

package mytrie

import (
    "fmt"
    "container/list"
)

type trieNode struct {
    c        byte            // 存储的字符
    children []*trieNode    // 孩子节点
    isWord   bool            // 是否构成单词
}

// 构造函数
func MyTrie() *trieNode {
    return &trieNode{
        c: '/',
        children: nil,
        isWord: false,
    }
} 

// 查找节点 root 的孩子节点是否有含有字符 x
// 找到则返回该节点
func match(root *trieNode, x byte) *trieNode {
    // 空 Trie 树
    if root == nil {
        return nil
    }
    // 尝试匹配
    for _, node := range root.children {
        if node.c == x {    // 匹配成功
            return node
        }
    }
    return nil                // 匹配失败
}

// Find 查找 Trie 树中是否有单词 word
func (root *trieNode) Find(word string) bool {
    // 递归出口
    if len(word) == 0 {
        return true
    } 
    // 尝试匹配
    node := match(root, word[0])
    if node == nil {            // 匹配失败
        return false
    }
    return node.Find(word[1:])    // 继续匹配
}

// Insert 插入一个单词 word
func (root *trieNode) Insert(word string) {
    if node := match(root, word[0]); node != nil {
        if len(word) == 1 {        
            node.isWord = true     
            return
        }
        node.Insert(word[1:])
    } else {
        newTrieNode := &trieNode{c: word[0], children: nil, isWord: false}
        if len(word) == 1 {
            newTrieNode.isWord = true
            root.children = append(root.children, newTrieNode)
            return
        }
        root.children = append(root.children, newTrieNode)
        newTrieNode.Insert(word[1:])
    }
}

// 层次遍历
func Travel(root *trieNode) {
    queue := list.New()
    queue.PushBack(root)

    for queue.Len() > 0 {
        node := queue.Front().Value.(*trieNode)
        queue.Remove(queue.Front())
        for i := 0; i < len(node.children); i++ {
            fmt.Printf("[%c %v %t] ", node.children[i].c, node.children[i].children, node.children[i].isWord)
            if node.children[i].children != nil {
                queue.PushBack(node.children[i])
            }
        }
        fmt.Println()
    }
}

应用

最广泛的应用大概是统计以 xxx 为前缀的所有单词个数，或其变种。
我大概的解题思路是：先查找该前缀是否存在，若存在则相当于遍历以最后一个字符为根的子树从根节点到叶子节点的路径（一条路径上可能有多个单词，还记得 ant 和 an 吗？）

小结

在实际应用中，灵活调整 Trie 的数据结构，可以适应不同需求，Trie 树的各种别名就是这么来的。