本文共 4176 字，大约阅读时间需要 13 分钟。

字典树（Java 实现）

一、概念

Trie树（字典树）是一种树形数据结构，常用于解决字符串的统计、排序及查找问题。它通过空间换时间的原则，最大限度地减少无谓的字符串比较，显著提高查询效率。

Trie的核心思想在于利用字符串的公共前缀来降低查询时间开销。通过共享前缀，Trie能够高效地存储和检索大量字符串数据。

二、Trie 核心性质

三、Trie 树构建

Trie树的构建过程如下：

四、查询操作

五、复杂度分析

Trie树的时间复杂度为 O(长度)，插入和查询效率显著高于哈希表。

六、Java 实现代码

import java.util.HashMap;public class TrieTree {    private class Node {        private int prefixNum;  // 前缀数目        private int duplicateNum; // 重复数目        private Node[] children; // 子节点数组        private boolean isLeaf; // 是否为叶节点        Node() {            prefixNum = 0;            duplicateNum = 0;            isLeaf = false;            children = new Node[26];        }    }    private Node root;    public TrieTree() {        root = new Node();    }    public void insert(String word) {        insert(root, word.toLowerCase());    }    private void insert(Node root, String word) {        char[] chars = word.toCharArray();        for (int i = 0; i < chars.length; i++) {            char c = chars[i];            int index = c - 'a';            if (root.children[index] != null) {                root = root.children[index];            } else {                Node newNode = new Node();                root.children[index] = newNode;                root = newNode;                if (i == chars.length - 1) {                    newNode.isLeaf = true;                }            }        }    }    public HashMap
   
     getAllWords() {        return preTraversal(root, "");    }    private HashMap
    
      preTraversal(Node root, String prefix) {        HashMap
     
       map = new HashMap<>();        if (root != null) {            if (root.isLeaf) {                map.put(prefix, root.duplicateNum);            }            for (int i = 0; i < root.children.length; i++) {                if (root.children[i] != null) {                    String nextPrefix = prefix + (char) ('a' + i);                    map.putAll(preTraversal(root.children[i], nextPrefix));                }            }        }        return map;    }    public boolean isExist(String word) {        return search(root, word.toLowerCase());    }    private boolean search(Node root, String word) {        if (root == null) {            return false;        }        if (word.isEmpty()) {            return true; // 根节点代表空字符串        }        char c = word.charAt(0);        int index = c - 'a';        if (root.children[index] == null) {            return false;        }        return search(root.children[index], word.substring(1));    }    public HashMap
      
        getWordsForPrefix(String prefix) {        return getWordsForPrefix(root, prefix.toLowerCase());    }    private HashMap
       
         getWordsForPrefix(Node root, String prefix) {        HashMap
        
          map = new HashMap<>(); if (root == null) { return map; } char[] chars = prefix.toCharArray(); for (int i = 0; i < chars.length; i++) { char c = chars[i]; int index = c - 'a'; if (root.children[index] == null) { return map; } root = root.children[index]; } String currentPrefix = prefix; return preTraversal(root, currentPrefix); } public static void main(String[] args) { TrieTree trie = new TrieTree(); trie.insert("i"); trie.insert("love"); trie.insert("china"); trie.insert("xiaoliang"); trie.insert("man"); trie.insert("handsome"); trie.insert("love"); trie.insert("chinaha"); trie.insert("her"); trie.insert("know"); HashMap
         
           allWords = trie.getAllWords(); System.out.println("所有单词及出现次数:"); for (String word : allWords.keySet()) { System.out.println(word + " 出现: " + allWords.get(word) + "次"); } HashMap
          
            chinWords = trie.getWordsForPrefix("chin"); System.out.println("\n包含 chin（包括本身）前缀的单词及出现次数:"); for (String word : chinWords.keySet()) { System.out.println(word + " 出现: " + chinWords.get(word) + "次"); } System.out.println("\n字典树中不存在：" + (trie.isExist("xiaoming") ? "" : "不存在")); }}
          
         
        
       
      
     
    
   

七、总结

Trie树通过共享前缀优化存储和查询效率，适用于大规模字符串数据处理。Java实现代码展示了其核心逻辑和应用场景。