[AIGC] 字典树Trie树详解及其Java实现

字典树，也称为Trie树或前缀树，是一种常见的搜索数据结构，广泛应用于字符串查询的场景中，比如网络词典的实现，或者是搜索引擎中词语的自动补全。

---

Trie树的概念

Trie树是一种特别的n叉树模型，它的主要应用是用于统计和排序大量的字符串，经常被搜索引擎系统用于文本词频统计。

Trie树特性

1. 根节点代表空字符串；
2. 从根节点到每一个节点，路径上经过的字符连起来，为该节点对应的字符串；
3. 每个节点的所有子节点路径代表的字符都不相同。

Trie树的操作

Trie树的主要有两个基本操作：插入和查询。

插入操作

从根节点开始，依次遍历要插入的单词中的每一个字符，如果此字符对应的子节点存在，就向下继续遍历；如果不存在，就创建一个新的节点。

查询操作

和插入操作类似，从根节点开始，依次遍历要查询的单词中的每一个字符，如果此字符对应的子节点存在，就继续向下遍历；如果不存在，说明字典树中不存在此单词。

Java实现Trie树

下面我们使用Java语言，实现一个基础的Trie树结构：

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }
    // search a prefix or whole key in trie and
    // returns the node where search ends
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter)) {
                node = node.get(curLetter);
            } else {
                return null;
            }
        }
        return node;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}

class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch -'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch -'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
    }
    public void setEnd() {
        isEnd = true;
    }
    public boolean isEnd() {
        return isEnd;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

上述示例代码实现了一个基本的 Trie 树，包括了插入单词，查找单词以及查找指定的前缀等功能。TrieNode 代表了 Trie 树的每一个节点，每个节点包含26个链接，分别对应26个小写英文字母。

以上就是我对字典树Trie的简单解释以及如何使用Java语言实现字典树。希望对你有所帮助。任何关于数据结构或其他编程相关的问题，都欢迎向我提问。