一、定义
Trie树，又叫前缀树、字典树
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计
特点：额外构造一颗Trie树，后续查询以O(len) (len为字符串长度) 时间复杂度完成查找和统计，以空间换时间
Trie树的基本性质：
（1）根节点不包含字符，除根节点意外每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。
二、构造过程
给出字符串"abc","ab","bd","dda"，根据该字符串序列构建一棵Trie树。则构建的树如下:
红色表示从根节点到此节点 能构成一个单词
三、使用场景
1、统计
如统计哪些单词不在常用词频中，用常用词频构造Trie树，统计给定单词是否能匹配Trie树
2、排序
应该构建树的过程中，满足左小右大的特点，采用中序遍历即可得到排序后的结果
3、公共前缀
统计哪些单词是以给定前缀开头的 ，我们搜索引擎 当输入关键字时，会自动提示以此关键字开头的依次常用搜索。
原文：https://www.cnblogs.com/yangfei629/p/13057651.html