字典树
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。（From baike）
它有三个基本性质：
(1)根节点不存储字符
(2)除根节点外每一个节点都只存储一个字符
(3)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串，每个节点的所有子节点包含的字符都不相同。
Java实现代码(注释详细):
package com.wxisme.trietree; /**
*Trie树的实现
*@author wxisme
*@time 2015-10-13 下午9:48:30
*/
public class TrieTree { private final int SIZE = 26;//字符出现的种类数,以所有的小写字母为例 private int nodeNumber;//子节点的个数 private int depth;//树的深度 private TrieNode root;//树根 public TrieTree() {
this.nodeNumber = 0;
this.depth = 0;
this.root = new TrieNode();
} /**
* 节点结构
* @author wxisme
*
*/
private class TrieNode {
private char val;//节点值 private TrieNode son[];//子节点数组 private boolean isEnd;//是否有以此节点为结束字符的单词 private int pearNumber;//节点出现的次数 public TrieNode() {
this.isEnd = false;
this.pearNumber = 0;
this.son = new TrieNode[SIZE];
}
} /**
* 向Trie中插入一个word
* @param word
*/
public void insert(String word) {
char[] wordChars = word.toCharArray(); TrieNode node = this.root; for(char ch : wordChars) {
int pos = ch - 'a';
//如果相应位置为空则创建
if(node.son[pos] == null) {
node.son[pos] = new TrieNode();
node.son[pos].val = ch;
node.pearNumber = 1;//第一次出现
this.nodeNumber ++;
}
else {//已经有该字符
node.pearNumber ++;
}
node = node.son[pos];
}
node.isEnd = true;
this.depth = Math.max(this.depth, word.length());
} /**
* 查找是否存在单词word
* @param word
* @return 结果
*/
public boolean search(String word) {
char[] wordChars = word.toCharArray(); TrieNode node = this.root; for(char ch : wordChars) {
int pos = ch - 'a';
if(node.son[pos] != null) {
node = node.son[pos];//继续向下查找
}
else {
return false;
}
} return node.isEnd;
} /**
* 查找是否存在以word为前缀的单词，和search()类似，只是不用判断边界。
* @param word
* @return 结果
*/
public boolean searchPrefix(String word) {
char[] wordChars = word.toCharArray(); TrieNode node = this.root; for(char ch : wordChars) {
int pos = ch - 'a';
if(node.son[pos] != null) {
node = node.son[pos];//继续向下查找
}
else {
return false;
}
} return true;
} /**
* 统计单词出现的次数
* @param word
* @return 结果
*/
public int wordCount(String word) {
char[] wordChars = word.toCharArray(); TrieNode node = this.root; for(char ch : wordChars) {
int pos = ch - 'a';
if(node.son[pos] == null) {
return 0;
}
else {
node = node.son[pos];
}
} return node.isEnd?node.pearNumber:0;
} /**
* 统计以word为前缀的单词个数
* @param word
* @return 结果
*/
public int wordPrefixCount(String word) {
char[] wordChars = word.toCharArray(); TrieNode node = this.root; for(char ch : wordChars) {
int pos = ch - 'a';
if(node.son[pos] == null) {
return 0;
}
else {
node = node.son[pos];
}
} return node.pearNumber;
} /**
* 深度优先遍历Trie树
* @param root
*/
public void traversal(TrieNode root) {
if(root == null) {
return;
}
for(TrieNode node : root.son) {
System.out.println(node.val);
traversal(node);
}
} public int getNodeNumber() {
return nodeNumber;
} public int getDepth() {
return depth;
} public TrieNode getRoot() {
return root;
} }
Leetcode应用：http://www.cnblogs.com/wxisme/p/4875309.html http://www.cnblogs.com/wxisme/p/4876980.html
