本文参考资源：
详谈树结构（传统树、字典树、hash 树、Merkle Patricia Tree）_C/C++_smilejiasmile的博客-CSDN博客
概述
Tire树称为字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。（高效查找的数据结构-HashTree（哈希树））典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
Trie树的缺点是它非常消耗空间。
Trie树的三个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符都不相同。
Trie树结构
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
Trie树的应用有：
- 维护字符串集合（即字典）。
- 向字符串集合中插入字符串（即建树）。
- 查询字符串集合中是否有某个字符串（即查询）。
- 统计字符串在集合中出现的个数（即统计）。
- 将字符串集合按字典序排序（即字典序排序）。
- 求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即求最长公共前缀）。
大多数时候，我们是要维护一个key-value对，key就是这个从根节点到叶子节点形成的字符串，而value信息就存储在叶子节点，例如汉英字典去查一个单词的中文翻译。
java代码实现：（根据不同的应用可以设计不同的实现）
class Node{
int num;//有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
Node[] children = new Node[26];//所有的子节点
Object data;// 如果是叶子节点可以存储数据。
}
算法题示例
你考入大城市沙坪坝的学校， 但是沙坪坝的当地人说着一种很难懂的方言， 你完全听不懂。 幸好你手中有本字典可以帮你。 现在你有若干个听不懂的方言需要查询字典。
输入格式：
第一行，两个整数n和m。
接下来有n行表示字典的内容，每行表示一条字典的记录。每条记录包含两个空格间隔的单词，第一个单词为英文单词，第二个单词为对应的沙坪坝方言。
接下来有m行，每行一个单词，表示你要查询的沙坪坝方言。
输出格式：
输出m行，每行一个英文单词，表示翻译后的结果。
如果某个单词字典查不到，输出"eh"
样例输入：
5 3
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
样例输出：
cat
eh
loops
注：所有单词都用小写字母表示， 且长度不超过10。
解答：
static class Node{
Node[] children = new Node[26];//所有的子节点
String data;// 如果是叶子节点可以存储数据。
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int referCount = scanner.nextInt();
int targetCount = scanner.nextInt();
Node root = new Node();
for(int i = 0;i<referCount;i++){
String origin = scanner.next();
char[] refer = scanner.next().toCharArray();
Node node = root;
for(int n = 0;n<refer.length;n++){
if(node.children[refer[n]-'a'] != null) {
node = node.children[refer[n]-'a'];
continue;
}
node = (node.children[refer[n]-'a'] = new Node());
if(n == refer.length-1) node.data = origin;
}
}
for(int i = 0;i<targetCount;i++){
char[] toFind = scanner.next().toCharArray();
Node node = root;
boolean isFind = true;
for(int n = 0;n<toFind.length;n++){
if((node = node.children[toFind[n]-'a'])!=null) continue;
isFind = false;
break;
}
System.out.println(isFind?node.data:"eh");
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e7%ae%97%e6%b3%95%e7%ab%9e%e8%b5%9b%e5%b8%b8%e7%94%a8%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e5%ad%97%e5%85%b8%e6%a0%91trie/
