Trie树，又称字典树，关于它的结构就不详细介绍了。Trie树在单词统计、前缀匹配等很多方面有很大用处。它的主要特点如下：
根节点不包含字符，除根节点外的每一个节点都只包含一个字符。从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。
我自己用java实现了一个最基本的Trie树，功能有：插入单词，查找单词，删除单词，以字典序遍历打印出所有出现过的单词及频数。另有几点说明如下：
每个结点存储子结点时不使用固定长度的数组，而使用Map<Character, TrieNode>结构，这样可以处理任意字符集。当然，你还得准备一个char型数组，以字典序存储要处理的所有字符，遍历的时候回用到。顺便提一下，如果你确定处理的只涉及26个英文字母，用一个26个大小的数组来存储子结点是个不错的选择，且比较简单。Node结点中存储哪些值要看实际情况，在本例中存储的是单词的出现次数。你也可以增加一个字段prefixNum，用于存储当前前缀出现次数（即含有当前前缀的单词数）。这个参数是很有用的，而且在删除操作时，只需要从根结点往下判断第一个prefixNum==1的删除即可。自己试一下就明白了。我之所以没采用，主要想练习一下递归算法，好久没用了。前一点说结点中的数据根据实际情况而定，再举个例子。“题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。”对于这个题目，显然结点中就存储单词第一次出现的位置（假如当前结点是单词结尾）。import java.util.*;
/** * Tries数据结构（字典树） * 这里只是最基本的实现，可判断某个单词是否出现过，单词出现频数等，根据需要可做其它扩展 * @author * */ public class Trie { private TrieNode root; private char[] characterTable= {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', // 遍历的时候使用 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; public Trie() { root = new TrieNode(); } /** * 插入字符串 * @param word */ public void insert(String word) { TrieNode node = root; word = word.trim(); for (int i = 0; i < word.length(); i++) { if (!(node.children.containsKey(word.charAt(i)))) { node.children.put(word.charAt(i), new TrieNode()); } node = node.children.get(word.charAt(i)); } node.terminable = true; node.count ++; }
/** * 查找某个字符串 * @param word * @return */ public boolean find(String word) { TrieNode node = root; for(int i = 0; i < word.length(); i++) { if(!(node.children.containsKey(word.charAt(i)))) { return false; } else { node = node.children.get(word.charAt(i)); } } return node.terminable; // 即便该字符串在Trie路径中，也不能说明该单词已存在，因为它有可能是某个子串 }
/** * 删除某个字符串（必须是个单词，而不是前缀） * * @param word */ public void delete(String word) { if(!find(word)) { System.out.println("no this word."); return; } TrieNode node = root; deleteStr(node, word); } public boolean deleteStr(TrieNode node, String word) { if(word.length() == 0) { node.terminable = false; // 不要忘了这里信息的更新 return node.children.isEmpty(); } if (deleteStr(node.children.get(word.charAt(0)), word.substring(1))) { node.children.remove(word.charAt(0)); if (node.children.isEmpty() && node.terminable == false) { // 注意第二个条件，假如有"abcd"与"abc",删除abcd时，要判断中间路径上是不是另一个子串的结束 return true; } } return false; } /** * 以字典序输出Tire中所有出现的单词及频数 */ public void traverse() { StringBuffer word = new StringBuffer(""); TrieNode node = root; traverseTrie(node, word); } public void traverseTrie(TrieNode node, StringBuffer word) { if(node.terminable) { System.out.println(word + "------" + node.count); if(node.children.isEmpty()) return; } for(int i=0; i<characterTable.length; i++) { if(!(node.children.containsKey(characterTable[i]))) continue; traverseTrie(node.children.get(characterTable[i]), word.append(characterTable[i])); word.deleteCharAt(word.length()-1); } }
}
/** * Trie结点类 * * @author * @param <T> */ class TrieNode { public boolean terminable; // 是不是单词结尾（即叶子节点） public int count; // 单词出现频数 public Map<Character, TrieNode> children = null; public TrieNode() { terminable = false; count = 0; children = new HashMap<Character, TrieNode>(); } }
