阅读量:6
字典树（Trie，也称前缀树）是一种用于存储字符串的树形数据结构。它将字符串中的字符作为树的边，每个节点代表一个可能的前缀。字典树非常适合处理大量字符串的搜索、插入和删除操作，尤其是在查找具有相同前缀的字符串时非常高效。
基本概念：
- 根节点：通常不包含任何数据，它的子节点包含字符串的第一个字符。
- 内部节点：代表字符串的中间字符。
- 叶子节点：代表字符串的结束字符，通常会附加一个标志表示该路径是一个完整的单词。
案例分析与实现：
假设我们要实现一个简单的字典树来存储英文单词，比如 “cat”, “cattle”, “dog”, “dodge” 和 “do”。
步骤1: 定义节点类
class TrieNode { private final int ALPHABET_SIZE = 26; TrieNode[] children = new TrieNode[ALPHABET_SIZE]; boolean isEndOfWord; public TrieNode() { isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++) { children[i] = null; } } } 步骤2: 实现字典树类
public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // 插入单词到字典树中 public void insert(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { int index = word.charAt(i) - 'a'; if (current.children[index] == null) { current.children[index] = new TrieNode(); } current = current.children[index]; } current.isEndOfWord = true; } // 搜索单词是否存在于字典树中 public boolean search(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { int index = word.charAt(i) - 'a'; if (current.children[index] == null) { return false; } current = current.children[index]; } return current != null && current.isEndOfWord; } } 步骤3: 使用字典树
public class Main { public static void main(String[] args) { Trie trie = new Trie(); trie.insert("cat"); trie.insert("cattle"); trie.insert("dog"); trie.insert("dodge"); trie.insert("do"); System.out.println("Search cat: " + trie.search("cat")); // 应输出 true System.out.println("Search dog: " + trie.search("dog")); // 应输出 true System.out.println("Search do: " + trie.search("do")); // 应输出 true System.out.println("Search dodge: " + trie.search("dodge")); // 应输出 true System.out.println("Search dodger: " + trie.search("dodger")); // 应输出 false } } 这个简单的字典树实现了插入和搜索功能。在实际应用中，你可能还需要实现删除、获取所有前缀单词等功能。字典树在拼写检查、自动完成、IP路由选择等领域有着广泛的应用。
当然，我们可以继续扩展字典树的功能，添加删除操作以及遍历字典树以列出所有单词或特定前缀下的单词。以下是完善后的代码：
步骤4: 添加删除功能
为了正确地删除一个单词，我们需要从字典树中移除该单词的路径，但要注意不要移除其他单词的公共前缀。这需要我们递归地检查并删除空闲的节点。
// 删除单词 public boolean delete(String key) { return delete(root, key, 0); } private boolean delete(TrieNode node, String key, int depth) { if (node == null) return false; if (depth == key.length()) { if (!node.isEndOfWord) return false; node.isEndOfWord = false; // 如果当前节点没有孩子，则可以删除 if (isEmpty(node)) { node = null; return true; } return false; } int index = key.charAt(depth) - 'a'; boolean shouldDeleteCurrentNode = delete(node.children[index], key, depth + 1); if (shouldDeleteCurrentNode) { node.children[index] = null; // 如果当前节点没有任何孩子并且不是单词的结尾，那么删除它 if (isEmpty(node) && !node.isEndOfWord) { return true; } } return false; } private boolean isEmpty(TrieNode node) { for (int i = 0; i < node.children.length; i++) { if (node.children[i] != null) return false; } return true; } 步骤5: 遍历字典树
遍历字典树可以让我们打印出所有的单词，或者找到具有特定前缀的所有单词。
// 打印具有给定前缀的所有单词 public void printWordsWithPrefix(String prefix) { TrieNode node = get(prefix); if (node == null) { System.out.println("No words found with the given prefix."); return; } printWords(node, prefix); } private void printWords(TrieNode node, String currentString) { if (node.isEndOfWord) { System.out.println(currentString); } for (int i = 0; i < node.children.length; i++) { if (node.children[i] != null) { printWords(node.children[i], currentString + (char)(i + 'a')); } } } // 查找具有给定前缀的节点 private TrieNode get(String key) { TrieNode current = root; for (int i = 0; i < key.length(); i++) { int index = key.charAt(i) - 'a'; if (current.children[index] == null) { return null; } current = current.children[index]; } return current; } 现在，我们可以在主函数中使用这些方法：
public static void main(String[] args) { Trie trie = new Trie(); trie.insert("cat"); trie.insert("cattle"); trie.insert("dog"); trie.insert("dodge"); trie.insert("do"); System.out.println("Search cat: " + trie.search("cat")); System.out.println("Search dog: " + trie.search("dog")); System.out.println("Search do: " + trie.search("do")); System.out.println("Search dodge: " + trie.search("dodge")); System.out.println("Search dodger: " + trie.search("dodger")); trie.printWordsWithPrefix("d"); trie.delete("cat"); System.out.println("After deleting 'cat': Search cat: " + trie.search("cat")); } 这样，我们就有了一个更完整的字典树实现，包括插入、搜索、删除和遍历功能。
在学生成绩管理系统中使用字典树（Trie）来实现增删改查（CRUD）操作是一种创新的方法，尤其是当需要对大量以文本形式存储的数据（如学生姓名）进行快速前缀搜索时。但是，传统的字典树并不直接支持数据的删除或修改操作，因为这些操作可能会影响树的结构。为了简化说明，我们将使用字典树来存储学生姓名，并使用一个额外的数据结构（如HashMap）来关联姓名与成绩，以便于更新和删除操作。
下面是一个使用Java实现的简化版学生成绩管理系统，其中使用字典树来存储学生姓名，并使用HashMap来存储姓名和成绩之间的对应关系。
首先，我们定义字典树的节点类TrieNode：
class TrieNode { private final int ALPHABET_SIZE = 26; TrieNode[] children = new TrieNode[ALPHABET_SIZE]; boolean isEndOfWord; public TrieNode() { isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++) { children[i] = null; } } } 然后，定义字典树类Trie：
public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String key) { TrieNode current = root; for (int i = 0; i < key.length(); i++) { int index = key.charAt(i) - 'a'; if (current.children[index] == null) { current.children[index] = new TrieNode(); } current = current.children[index]; } current.isEndOfWord = true; } public boolean search(String key) { TrieNode current = root; for (int i = 0; i < key.length(); i++) { int index = key.charAt(i) - 'a'; if (current.children[index] == null) { return false; } current = current.children[index]; } return current != null && current.isEndOfWord; } } 接下来，创建StudentScoreManager类，用于管理学生姓名和成绩：
import java.util.HashMap; public class StudentScoreManager { private Trie studentNames; private HashMap<String, Integer> scores; public StudentScoreManager() { studentNames = new Trie(); scores = new HashMap<>(); } public void addScore(String name, int score) { studentNames.insert(name); scores.put(name, score); } public void updateScore(String name, int score) { if (scores.containsKey(name)) { scores.put(name, score); } else { throw new IllegalArgumentException("Student not found."); } } public void deleteScore(String name) { if (scores.containsKey(name)) { scores.remove(name); // 删除字典树中的条目（这里简化处理，不实际删除） } else { throw new IllegalArgumentException("Student not found."); } } public int getScore(String name) { if (scores.containsKey(name)) { return scores.get(name); } else { throw new IllegalArgumentException("Student not found."); } } public boolean checkName(String name) { return studentNames.search(name); } } 最后，在main方法中使用StudentScoreManager：
public static void main(String[] args) { StudentScoreManager manager = new StudentScoreManager(); manager.addScore("Alice", 90); manager.addScore("Bob", 85); manager.addScore("Charlie", 92); System.out.println(manager.checkName("Alice")); // 输出 true System.out.println(manager.getScore("Bob")); // 输出 85 manager.updateScore("Charlie", 95); System.out.println(manager.getScore("Charlie")); // 输出 95 manager.deleteScore("Bob"); System.out.println(manager.checkName("Bob")); // 输出 false } 在这个示例中，addScore方法同时在字典树和HashMap中添加学生姓名和成绩；updateScore和deleteScore仅更新或删除HashMap中的成绩，而字典树保持不变（为了简单起见，没有实现在字典树中删除节点的功能）。getScore和checkName分别用于获取成绩和检查姓名是否存在。
需要注意的是，这种方法在删除操作上可能会导致字典树中存在“孤儿”节点，如果需要维护一个完全一致的字典树，那么删除操作需要更复杂的逻辑来重构树的结构。
