概念
字典树，顾名思义，是关于“字典”的一棵树。即：它是对于字典的一种存储方式（所以是一种数据结构而不是算法）。这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径，路径中每条边的字母连起来就是一个单词。
标橙色的节点是“目标节点“，即根节点到这个目标节点的路径上的所有字母构成了一个单词。
从这张图我们可以看出，字典树就是一棵树（emm…有些废话的嫌疑），只不过，这棵树的每条边上都有一个字母，然后这棵树的一些节点被指定成了标记节点（目标节点）而已。
这就是字典树的概念。结合上面说的概念，上图所示的字典树包括的单词分别为：
a abc bac bbc ca
功能
根据字典树的概念，我们可以发现：字典树的本质是把很多字符串拆成单个字符的形式，以树的方式存储起来。所以我们说字典树维护的是”字典“。那么根据这个最基本的性质，我们可以由此延伸出字典树的很多妙用。简单总结起来大体如下：
1.维护字符串集合（即字典）。
2.向字符串集合中插入字符串（即建树）。
3.查询字符串集合中是否有某个字符串（即查询）。
4.统计字符串在集合中出现的个数（即统计）。
5.将字符串集合按字典序排序（即字典序排序）。
6.求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即求最长公共前缀）。
我们可以发现，以上列举出的功能都是建立在“字符串集合”的基础上的。再一次强调，字典树是“字典”的树，一切功能都是“字典”的功能。这也为我们使用字典树的时候提供了一个准则：看到一大堆字符串同时出现，就往哈希和Trie树那边想一下。
实现
基本树结构
其中count表示以当前单词结尾的单词数量。
prefix表示以该处节点之前的字符串为前缀的单词数量。
class TrieNode: def __init__(self): self.count = 0 self.prefix = 0 self.nextNode = [None] * 26
插入新节点
好比假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词,那我们创建trie树就得到
# 插入一个新单词 # root为根节点， s为要加入的字符串 def insert(self, root, s): # 预处理 if root is None or len(s) == 0: return # 将字符串转化为字符数组 temp = list(s) # 构建和维护树 for i in range(len(s)): # 如果没有该节点，新加一个节点 if root.nextNode[ord(temp[i]) - ord('a')] is None: root.nextNode[ord(temp[i]) - ord('a')] = TrieNode() root = root.nextNode[ord(temp[i]) - ord('a')] # 前缀数加1 root.prefix += 1 # 最后count加1 root.count += 1
创建和维护一个字典树就完成了，下面的操作大同小异了。
查找（统计）
# 查找该单词是否存在，如果存在返回数量，不存在返回-1 def search(self, root, s): if root is None or len(s) == 0: return -1 temp = list(s) for i in range(len(s)): if root.nextNode[ord(temp[i]) - ord('a')] is None: return -1 root = root.nextNode[ord(temp[i]) - ord('a')] if root.count == 0: return -1 return root.count
查询以str为前缀的单词数量
# 查询以str为前缀的单词数量 def searchPrefix(self, root, s): if root is None or len(s) == 0: return -1 temp = list(s) for i in range(len(s)): if root.nextNode[ord(temp[i]) - ord('a')] is None: return -1 root = root.nextNode[ord(temp[i]) - ord('a')] return root.prefix
主函数测试
if __name__ == '__main__': newNode = TrieNode() newNode.insert(newNode, 'hello') newNode.insert(newNode, 'hello') newNode.insert(newNode, 'helloword') print(newNode.search(newNode, 'hello')) print(newNode.searchPrefix(newNode, 'he'))
