对于字典树/前缀树可能大部分情况很难直观或者有接触的体验，尤其是对前缀这个玩意没啥概念，可能做题遇到前缀问题也是使用暴力匹配蒙混过关，如果字符串比较少使用哈希表等结构可能也能蒙混过关，但如果字符串比较长、相同前缀较多那么使用字典树可以大大减少内存的使用和效率。
一个字典树的应用场景：在搜索框输入部分单词下面会有一些神关联的搜索内容，你有时候都很神奇是怎么做到的，这其实就是字典树的一个思想。
一、字典树trie树
Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树，是一种多叉树结构。
二、trie树的作用
Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。
（1）核心应用
1. 字符串检索；
2. 词频统计；
3. 字符串排序；
4. 前缀匹配。
（2）trie树节点
每个字母都占用一个trie树节点，根节点与子节点没有本质的区别，主要有这几个属性：
1. root: 是否为根节点
2. dict: 装子节点的hash表
3. flag: 是否为一个单词的结尾
4. value: 该单词的完整内容（只有在flag为True时才有）
5. count: 该单词出现的次数（只有在flag为True时才有）
6. list: 是一个字典，用于遍历储存东西的(只有root节点才有)
class Trie(object):
def __init__(self, root=None,flag=False,count=None,value=None):
self.root = root # root 节点用于装内容
self.count = count # count 用于计数，可以统计词频
self.dict = {} # dict 用于装子节点，子节点还是trie树
self.flag = flag # flag用于判断是否结束
self.value = value # value就表示这个单词是什么
self.list = {}（3）常规操作
先来实现最基础的四个操作：
1. insert: 增,注意最后一个字母的判断以及处理即可
2. search: 查
3. delete: 删
4. startsWith: 判断前缀是否存在
①增
def insert(self, word): """ :type word: str :rtype: None """ trie = self for j,i in enumerate(word): # 如果是不是最后一个字母就遍历(或添加) if j != len(word) - 1: if i not in trie.dict: trie.dict[i] = Trie(root=i) trie = trie.dict[i] else: # 是最后一个字母且flag为true就加计数 if i in trie.dict and trie.dict[i].flag: trie = trie.dict[i] trie.count += 1 # 是最后一个字母但flag为false就修改flag将计数改为1 elif i in trie.dict and not trie.dict[i].flag: trie = trie.dict[i] trie.flag = True trie.count = 1 trie.value = word # 如果trie.dict中没有就新增 else: trie.dict[i] = Trie(root=i,flag=True,count=1,value=word)
②查
def search(self, word): """ :type word: str :rtype: bool """ trie = self for i in word: if i in trie.dict: trie = trie.dict[i] else: return False return trie.flag
③删
def delete(self, word):
'''
:type word: str
:rtype: None
'''
if self.search(word):
trie = self
for i in word:
if len(trie.dict) == 1:
trie.dict.pop(i)
break
else:
trie = trie.dict[i]
else:
print('该单词不在trie树中')④判断前缀是否存在
def startsWith(self, prefix): """ :type prefix: str :rtype: bool """ trie = self for i in prefix: if i in trie.dict: trie = trie.dict[i] else: return False return True
（4）遍历操作
遍历操作就首选DFS深度优先搜索,参数中加入prefix的目的是为了后面的联想操作，如果只做遍历可以不加；值得一提的是，我对子节点的储存采用的是字典的形式，遍历出来的结果排序刚刚好就是字典序，也就实现了前面说的字符串字典序的处理（其实真要排字典序，直接sorted就好了，没必要用trie树）
def dfs(self,path,trie,prefix=''):
# 如果为真说明走到了一个单词的结尾
if trie.flag:
self.list[prefix + ''.join(path)] = trie.count
if trie.dict == {}:
return
for i in trie.dict:
path.append(i)
self.dfs(path,trie.dict[i],prefix)
path.pop()给trie树创建可迭代方法
def __iter__(self):
self.list = {} # 重置self.list
self.dfs([],self)
return iter(self.list)（5）联想操作
联想业务应该是这样的： 用户输入前几个字母，然后匹配出完整的单词，使用频率越高的单词理应放在最前面；
所以整体思路是这样的： 根据前缀找到前缀最后一个字母所在的trie树节点，从那个节点开始进行DFS遍历，然后在遍历结果前加上一个前缀，最后将结果按照count进行排序最后以列表形式输出结果；
先实现排序算法，这里用的是快速排序,注意比较的值是count，最后留下的是单词；
def quick_sorted(self,dict):
'''
:type dict: dict
:rtype: list
'''
if len(dict) >= 2:
nums = list(dict.keys())
mid = nums[len(nums) // 2]
left, right = {}, {}
nums.remove(mid)
for d in nums:
if dict[d] < dict[mid]:
left[d] = dict[d]
else:
right[d] = dict[d]
return self.quick_sorted(right) + [mid] + self.quick_sorted(left)
return list(dict.keys())再实现联想操作
def dream(self,prefix):
'''
:type prefix: str
:rtype: list
'''
trie = self
for i in prefix:
if i in trie.dict:
trie = trie.dict[i]
elif dict[d] == dict[mid]:
if d > mid:
right[d] = dict[d]
else:
left[d] = dict[d]
else:
return []
self.list = {} # 重置self.list
self.dfs([],trie,prefix)
return self.quick_sorted(self.list)C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程