本文参考资源:
详谈树结构(传统树、字典树、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/