前言
字典树又称单词查找树，它是一种树形结构，是一种哈希树的变种，典型应用是用于统计，保存大量的字符串（但不仅限于字符串），统计以是否有以某字符串最为前缀的字符串，有的话有多少，某字符串出现了多少次等，所以经常被搜索引擎系统用于文本词频统计。
它有三个基本性质：(1)根节点不存储字符(2)除根节点外每一个节点都只存储一个字符(3)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串，每个节点的所有子节点包含的字符都不相同。
下边我将把我实现的代码和大家分享一下，代码几乎每行都有详细注释，大家一看就清除明了了，时间原因，就不再用多余的文字再追加详述了。
创建字典树package Trie;import org.apache.commons.lang3.StringUtils;import com.google.common.base.CharMatcher;/** * 字典树类 * * @author chenleixing */public class Trie {//各个节点的子树数目即字符串中的字符出现的最多种类private final int SIZE = 26;//除根节点外其他所有子节点的数目private int numNode;//树的深度即最长字符串的长度private int depth;//字典树的根private TrieNode root;/** * 初始化字典树 */public Trie() {this.numNode=0;this.depth=0;this.root = new TrieNode();}/** * 字典树节点类，为私有内部类 */private class TrieNode {// 所有的儿子节点或者一级子节点private TrieNode[] son;// 有多少字符串经过或到达这个节点,即节点字符出现的次数private int numPass;// 有多少字符串通过这个节点并到此结束的数量private int numEnd;// 是否有结束节点private boolean isEnd;// 节点的值private char value;/** * 初始化节点类 */public TrieNode() {this.numPass=0;this.numEnd=0;this.son = new TrieNode[SIZE];this.isEnd = false;}}
首先各种方法操作方法的字符串验证或非法判断
一般字典树常用存储单词类字符串，当然也可以存储数字或者其他字符只是一个耗费内存较多的问题，不管怎么最好在操作方法之前做个验证和判断，以更加的提高操作效率，代码健壮性更强，如插入，查找是否存在等，如果字符串中存在“非法”的字符，那么可以直接返回false来结束操作。代码如下边所示：
/** * 对操作的字符串进行一个非法的判断，是否为字母构成的字符串 */private boolean isStrOfLetter(String str){//null或者空白字符串，则插入失败if (StringUtils.isBlank(str)){return false;}//如果字符串中有非字母字符，则插入失败if(!CharMatcher.JAVA_LETTER.matchesAllOf(str)){return false;}return true;}
其中代码中我用到了common-lang工具包里的StringUtils工具类和Guava里的CharMatcher，当然大家可以用循环啊用正则表达式或者其他工具来实现相同的功能，这里就不再一一详述了，如果有想深入了解它们用法的话或jar包下载，可参考我的以下博文：commons-lang中常用方法，StringUtils方法全集介绍，JavaScript、Java正则表达式详解，打了兴奋剂的CharMatcher，Strings字符串判断工具。
字典树存储字符串方法实现/** * 插入方法，插入字符串，不区分大小写 */public boolean insertStr(String str) {//插入的字符为非法字符，则插入失败if(!isStrOfLetter(str)){return false;}//插入字符串str=str.toLowerCase();//不区分大小写，转为小写char[] letters = str.toCharArray();//转成字符数组TrieNode node=this.root;//先从父节点开始for (char c:letters) {int pos = c – 'a';//得到应存son[]中的索引if (node.son[pos] == null) {//此字符不存在node.son[pos] = new TrieNode();node.son[pos].value = c;node.son[pos].numPass=1;this.numNode++;} else {//此字符已经存入node.son[pos].numPass++;}node = node.son[pos];//继续为下一下字符做准备}node.isEnd = true;//标记：有字符串到了此节点已结束node.numEnd++;//这个字符串重复次数if(letters.length>this.depth){//记录树的深度this.depth=letters.length;}return true;//插入成功}
查找是否存以某前缀开头的字符串方法实现/** * 在字典树中查找是否存在某字符串为前缀开头的字符串(包括前缀字符串本身)，不区分大小写 */public boolean isContainPrefix(String str) {//查找的字符是否非法字符，则失败if(!isStrOfLetter(str)){return false;}//查找字符串str=str.toLowerCase();//不区分大小写，转为小写char[] letters = str.toCharArray();//转成字符数组TrieNode node=this.root;//先从父节点开始for (char c:letters) {int pos = c – 'a';//得到应存son[]中的索引if (node.son[pos] != null) {node=node.son[pos];//此字符存在继续查找下一个字符} else {//此字符不存在return false;}}return true;}
查找是否存在某字符串(不为前缀)方法实现/** * 在字典树中查找是否存在某字符串(不为前缀)，不区分大小写 */public boolean isContainStr(String str) {//查找的字符是否非法字符，则失败if(!isStrOfLetter(str)){return false;}//查找字符串str=str.toLowerCase();//不区分大小写，转为小写char[] letters = str.toCharArray();//转成字符数组TrieNode node=this.root;//先从父节点开始for (char c:letters) {int pos = c – 'a';//得到应存son[]中的索引if (node.son[pos] != null) {node=node.son[pos];//此字符存在继续查找下一个字符} else {//此字符不存在return false;}}return node.isEnd;}统计以指定字符串为前缀的字符串数量方法实现/** * 统计以指定字符串为前缀的字符串数量，，不区分大小写 */public int countPrefix(String str) {//统计的字符是否非法字符，则返回0if(!isStrOfLetter(str)){return 0;}//查找字符串str=str.toLowerCase();//不区分大小写，转为小写char[] letters = str.toCharArray();//转成字符数组TrieNode node=this.root;//先从父节点开始for (char c:letters) {int pos = c – 'a';//得到应存son[]中的索引if (node.son[pos] == null) {return 0;//没有以此字符串为前缀开头} else {//此字符存在,继续遍历node=node.son[pos];}}return node.numPass;}我不敢说我明天便可以做一个快乐的人，面朝大海春暖花开。
