本文参考资源：

详谈树结构（传统树、字典树、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/

算法竞赛常用数据结构-字典树Trie

概述

Trie树结构

算法题示例

发表回复

算法竞赛常用数据结构-字典树Trie

概述

Trie树结构

算法题示例

相关推荐

发表回复