对于字典树/前缀树可能大部分情况很难直观或者有接触的体验，尤其是对前缀这个玩意没啥概念，可能做题遇到前缀问题也是使用暴力匹配蒙混过关，如果字符串比较少使用哈希表等结构可能也能蒙混过关，但如果字符串比较长、相同前缀较多那么使用字典树可以大大减少内存的使用和效率。
一个字典树的应用场景：在搜索框输入部分单词下面会有一些神关联的搜索内容，你有时候都很神奇是怎么做到的，这其实就是字典树的一个思想。
一、字典树trie树
Trie树，又叫字典树、前缀树（PrefixTree）、单词查找树，是一种多叉树结构。
二、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节点才有)
classTrie(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:判断前缀是否存在
①增
definsert(self,word):""":typeword:str:rtype:None"""trie=selfforj,iinenumerate(word):#如果是不是最后一个字母就遍历(或添加)ifj!=len(word)-1:ifinotintrie.dict:trie.dict[i]=Trie(root=i)trie=trie.dict[i]else:#是最后一个字母且flag为true就加计数ifiintrie.dictandtrie.dict[i].flag:trie=trie.dict[i]trie.count+=1#是最后一个字母但flag为false就修改flag将计数改为1elifiintrie.dictandnottrie.dict[i].flag:trie=trie.dict[i]trie.flag=Truetrie.count=1trie.value=word#如果trie.dict中没有就新增else:trie.dict[i]=Trie(root=i,flag=True,count=1,value=word)②查
defsearch(self,word):""":typeword:str:rtype:bool"""trie=selfforiinword:ifiintrie.dict:trie=trie.dict[i]else:returnFalsereturntrie.flag③删
defstartsWith(self,prefix):""":typeprefix:str:rtype:bool"""trie=selfforiinprefix:ifiintrie.dict:trie=trie.dict[i]else:returnFalsereturnTrue（4）遍历操作
遍历操作就首选DFS深度优先搜索,参数中加入prefix的目的是为了后面的联想操作，如果只做遍历可以不加；值得一提的是，我对子节点的储存采用的是字典的形式，遍历出来的结果排序刚刚好就是字典序，也就实现了前面说的字符串字典序的处理（其实真要排字典序，直接sorted就好了，没必要用trie树）
def__iter__(self):self.list={}#重置self.listself.dfs([],self)returniter(self.list)（5）联想操作
联想业务应该是这样的：用户输入前几个字母，然后匹配出完整的单词，使用频率越高的单词理应放在最前面；
所以整体思路是这样的：根据前缀找到前缀最后一个字母所在的trie树节点，从那个节点开始进行DFS遍历，然后在遍历结果前加上一个前缀，最后将结果按照count进行排序最后以列表形式输出结果；
先实现排序算法，这里用的是快速排序,注意比较的值是count，最后留下的是单词；
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：